I’m a bit at a loss with an issue I have when trying to warmstart HiGHS on my model.
EDIT: I originally did not manage to build a minimal reproducer, so I made a relatively messy post (kept below for posterity). But I just managed to get a MNWE, so I’m rewriting most of this post, sorry!
Here is a (non-)working example demonstrating my problem (based on the knapsack example in the JuMP documentation).
I’m writing a function that builds and optimizes a model. It takes an optional init_x argument which, when provided, is used to set start values for (some of) the binary variables:
function solve_knapsack_problem(;
profit::Vector{Float64},
weight::Vector{Float64},
capacity::Float64,
init_x = [],
)
n = length(weight)
@assert length(profit) == n
model = Model(HiGHS.Optimizer)
@variable(model, x[1:n], Bin)
for i in init_x
@info "Set start value: x[$i] = 1"
set_start_value(x[i], 1)
# or, to check that the provided values are indeed feasible
# @constraint(model, x[i] == 1)
end
# another binary variable
# (comment these two lines and the problem goes away)
@variable(model, y, Bin)
@constraint(model, y >= x[1])
@objective(model, Max, profit' * x)
@constraint(model, weight' * x <= capacity)
optimize!(model)
@assert termination_status(model) == OPTIMAL
@assert primal_status(model) == FEASIBLE_POINT
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
chosen_items = [i for i in 1:n if value(x[i]) > 0.5]
return return chosen_items
end
When no initial values are provided, it behaves like in the doc example:
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_knapsack_problem(; profit = profit, weight = weight, capacity = capacity) # [1, 4, 5]
Now let’s try and warmstart the solver, telling it that item #4 should be chosen
julia> solve_knapsack_problem(; profit = profit, weight = weight, capacity = capacity, init_x=[4])
[ Info: Set start value: x[4] = 1
Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms
Solution has num max sum
Col infeasibilities 0 0 0
Integer infeasibilities 0 0 0
Row infeasibilities 0 0 0
Row residuals 0 0 0
Presolving model
2 rows, 5 cols, 6 nonzeros
1 rows, 4 cols, 4 nonzeros
MIP start solution is feasible, objective value is 7
Objective function is integral with scale 1
...
This looks as expected: the solver finds that the provided solution is feasible, and uses it to shorten the optimization process.
Now my issue happens when I try to warmstart the solver, telling it to choose item #1:
julia> solve_knapsack_problem(; profit = profit, weight = weight, capacity = capacity, init_x=[1])
[ Info: Set start value: x[1] = 1
Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms
WARNING: Row 0 has infeasibility of 1 from [lower, value, upper] = [ 0; -1; inf]
Solution has num max sum
Col infeasibilities 0 0 0
Integer infeasibilities 0 0 0
Row infeasibilities 1 1 1
Row residuals 0 0 0
Attempting to find feasible solution for (partial) user-supplied values of discrete variables
Presolving model
Problem status detected on presolve: Infeasible
Model status : Infeasible
Objective value : 0.0000000000e+00
HiGHS run time : 0.00
...
Now (I understand that) the solver tells me that the provided start value leads to an infeasible problem. It discards my solution and starts the optimization from scratch.
I find this hard to believe, because I know that there are solutions with x[1] = 1. I can even prove this by turning the start values into constraints (cf. the comment in the code above), in which case the optimization works well, as expected.
Everything disappears when I remove variable y from the model.
Can someone explain to me what’s happening here? Do I have wrong expectations here? Is there something more I should do to set start values to some (but not all) binary variables?
---
Original post
Part of my problem is that I haven’t (yet) manage to build a minimal non-working example. But I’ll try and describe what I’m doing, in the hope that someone will recognize some known issue, or help me build a simpler reproducer:
Globally, my process is as follows: I have defined a function that builds and solves a model, optionally setting start values if some are provided:
function build_and_solve_model(data; init_x=nothing)
model = Model(HiGHS.Optimizer)
# not sure whether this has anything to do with the issue, but
# x has this form because it's "ragged" (not rectangular)
x = [[@variable(model, binary=true, lower_bound=0.0, upper_bound=1.0, base_name="x[$i][$j]")
for j ∈ 1:data.Nj[i]]
for i in 1:data.Ni]
if init_x !== nothing
for i in eachindex(init_x)
for j in eachindex(init_x[i])
val = init_x[i][j] > 0.5 ? 1 : 0
# set a start value for x[i][j]
set_start_value(x[i][j], val)
# or, in order to test the feasibility of init_x:
# @constraint(model, x[i][j] == val)
end
end
end
# add a bunch of other variables here
# as well as constraints and an objective
optimize!(model)
return [value.(xi) for xi in x]
end
I then call it once without setting any start value. The result of this first call is then used to warmstart a second call which is identical to the first (same model, the only difference being the start values):
my_data = something();
x1 = build_and_solve_model(my_data) # Solver status: Optimal
build_and_solve_model(my_data, init_x = x1)
The second call outputs something like:
Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms
WARNING: Row 113 has infeasibility of 4 from [lower, value, upper] = [ 0; -4; 0]
WARNING: Row 688 has infeasibility of 3.006e+04 from [lower, value, upper] = [ 0; -30060; 0]
WARNING: Row 1728 has infeasibility of 2.175e+07 from [lower, value, upper] = [ 21751220; 0; 21751220]
Solution has num max sum
Col infeasibilities 0 0 0
Integer infeasibilities 0 0 0
Row infeasibilities 1016 2.175e+07 3.021e+07
Row residuals 0 0 0
Attempting to find feasible solution for (partial) user-supplied values of discrete variables
Presolving model
Problem status detected on presolve: Infeasible
Model status : Infeasible
Objective value : 0.0000000000e+00
HiGHS run time : 0.00
and then it starts the optimization process from scratch, finding the same solution as the “cold start” call, in about the same time. I understand from the HiGHS output that the solver finds my model infeasible with the given start values, which I find hard to believe since the values come from the solution of the exact same model.
In order to make sure that my start values are indeed feasible, I turned the set_start_value calls into @constraints (cf. comment in the code above). Re-running the warm-started call this way now gives the expected output:
Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms
Presolving model
0 rows, 0 cols, 0 nonzeros
0 rows, 0 cols, 0 nonzeros
Presolve: Optimal
Solving report
Status Optimal
Primal bound 100613.400615
Dual bound 100613.400615
Gap 0% (tolerance: 0.01%)
Solution status feasible
Which I interpret to mean that my start values are indeed feasible (and completely specify the solution, so that the presolver is able to find it alone, without ever needing to actually optimize anything).
I’ll keep looking for a minimal (or at least shareable) reproducer, but in the meantime, does this look like a known behavior? Did I do something wrong, or are my expectations somehow incorrect?