Possibly disable crossover for dual calculation

[DillonJ]

The discussion on the solution status in issue #1296 got me to thinking...

Currently to get marginal values for a MIP problem, we solved a relaxed problem with MIP variables fixed to their solutions. I'm thinking, perhaps we can disable crossover for this so-called dual-solve to get a solution faster.

@datejada is this a viable approach? Will crossover impact the dual solution?

[datejada]

@DillonJ I am not sure about the quality of the dual solution if you fix the binary/integer variables and then solve the LP without crossover. I checked in the mini example below, and in that case, you get in both cases (with and without crossover) a value in the dual of the constraint. But! the status of the dual problem in the case without crossover is "INFEASIBLE_POINT", and even the sign of the "dual" value is different. So I wouldn't trust the dual-variable values if no crossover was run. In TNO, we disable the crossover only for the investment problem; for the dual calculation when having MIPs (as you described), we don't disable it.

@g-moralesespana any extra thoughts?

using JuMP
import HiGHS

function solve_knapsack_problem(;
    profit::Vector{Float64},
    weight::Vector{Float64},
    capacity::Float64,
    run_crossover::Bool,
)
    n = length(weight)
    # The profit and weight vectors must be of equal length.
    @assert length(profit) == n
    model = Model(HiGHS.Optimizer)
    @variable(model, x[1:n], Bin)
    @variable(model, slack >= 0)
    @objective(model, Max, profit' * x - 100 * slack)
    @constraint(model, c, weight' * x + slack == capacity)
    optimize!(model)
    @info dual_status(model)
    @info dual(c)
    assert_is_solved_and_feasible(model)
    println("Objective is: ", objective_value(model))
    println("Solution is:")
    for i in 1:n
        print("x[$i] = ", round(Int, value(x[i])))
        println(", c[$i] / w[$i] = ", profit[i] / weight[i])
    end
    print("slack = ", value(slack))
    chosen_items = [i for i in 1:n if value(x[i]) > 0.5]
    @info "resolving"
    fix_discrete_variables(model)
    @info is_fixed.(x)
    set_attribute(model, "solver", "ipm")
    if !run_crossover
        set_attribute(model, "run_crossover", "off")
    end
    optimize!(model)
    solution_summary(model)
    @info dual_status(model)
    @info dual(c)
    return chosen_items
end

# data
n = 5;
capacity = 10.0;
profit = [5.0, 3.0, 2.0, 7.0, 4.0];
weight = [2.0, 8.0, 4.0, 2.0, 5.0];

# solve with crossover
solve_knapsack_problem(; profit = profit, weight = weight, capacity = capacity, run_crossover = true)

# solve without crossover
solve_knapsack_problem(; profit = profit, weight = weight, capacity = capacity, run_crossover = false)

[DillonJ]

Nice one @datejada that comprehensively answers the question!

[nnhjy]

I've also encountered similar things recently. Just some lessons learnt in brief:
When using the barrier method to solve the root LPs of an MIP, crossover converts the obtained solution into a BFS, which is critical for calculating trustworthy duals, since, roughly speaking, only BFS can ensure stable shadow prices with valid ranges. In this case, crossover is needed if we want the model to derive the duals.

So, whether to disable crossover sounds more like a matter of case-specific solver configuration. When there is no need to calculate duals OR the MIP is solved by a simplex method that guarantees a basis solution, crossover may not be necessary. As another example, in the case where dual calculation is needed, this solver setup should work:

• mip_solver: [barrier method + crossover] OR [simplex method]
• lp_solver (to calculate the duals from the relaxed MIP solution): [barrier method w/o crossover] (suppose the fix() from JuMP used in SpineOpt can automatically enable the solver to retain the optimal basis from the MIP solution)