# Infeasible warmstart with JuMP & HiGHS

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?

1 Like

Thanks for the reproducible example. I was just starting to reply to your original comment, but now I have something a bit more concrete to go on.

The problem is slightly my fault. You may think that you have just provided a partial start for `x[1]`, but in the Julia wrapper we actually impute a starting value for all variables, which is 0 projected onto the bounds. Let me check if HiGHS supports us passing a subset of starting values.

1 Like

Perhaps you’ve already noticed, but setting the initial values to 0.9999 instead of 1 eases the problem also. This is against the Binary definition, but it doesn’t error.

1 Like

So my conclusion is that HiGHS does not attempt to repair a partial MIP solution.

If you pass a start value, you must pass a feasible start value for all discrete variables. HiGHS will then attempt to solve the continuous variables and find a better solution.

``````julia> using JuMP, HiGHS

julia> function solve_knapsack_problem(;
profit::Vector{Float64},
weight::Vector{Float64},
capacity::Float64,
init_x = [],
)
n = length(weight)
model = Model(HiGHS.Optimizer)
@variable(model, x[1:n], Bin) # Implicit starting solution of x = 0
set_start_value.(x[init_x], 1)
@variable(model, y)  # No starting solution for continuous
@constraint(model, y >= x[1])
@objective(model, Max, profit' * x - y)
@constraint(model, weight' * x <= capacity)
optimize!(model)
end
solve_knapsack_problem (generic function with 1 method)

julia> n = 5;

julia> capacity = 10.0;

julia> profit = [5.0, 3.0, 2.0, 7.0, 4.0];

julia> weight = [2.0, 8.0, 4.0, 2.0, 5.0];

julia> solve_knapsack_problem(; profit = profit, weight = weight, capacity = capacity) # [1, 4, 5]
Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms
Presolving model
1 rows, 5 cols, 5 nonzeros
1 rows, 4 cols, 4 nonzeros
Objective function is integral with scale 1

Solving MIP model with:
1 rows
4 cols (4 binary, 0 integer, 0 implied int., 0 continuous)
4 nonzeros

Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work
Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

0       0         0   0.00%   17              -inf                 inf        0      0      0         0     0.0s

Solving report
Status            Optimal
Primal bound      15
Dual bound        15
Gap               0% (tolerance: 0.01%)
Solution status   feasible
15 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing            0.00 (total)
0.00 (presolve)
0.00 (postsolve)
Nodes             1
LP iterations     1 (total)
0 (strong br.)
0 (separation)
0 (heuristics)

julia> solve_knapsack_problem(; profit = profit, weight = weight, capacity = capacity, init_x=[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
0 rows, 0 cols, 0 nonzeros
0 rows, 0 cols, 0 nonzeros
Presolve : Reductions: rows 0(-2); columns 0(-6); elements 0(-7) - Reduced to empty
Solving the original LP from the solution after postsolve
Model   status      : Optimal
Objective value     :  4.0000000000e+00
HiGHS run time      :          0.00
Presolving model
1 rows, 5 cols, 5 nonzeros
1 rows, 4 cols, 4 nonzeros

MIP start solution is feasible, objective value is 4
Objective function is integral with scale 1

Solving MIP model with:
1 rows
4 cols (4 binary, 0 integer, 0 implied int., 0 continuous)
4 nonzeros

Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work
Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

0       0         0   0.00%   17              4                325.00%        0      0      0         0     0.0s

Solving report
Status            Optimal
Primal bound      15
Dual bound        15
Gap               0% (tolerance: 0.01%)
Solution status   feasible
15 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing            0.00 (total)
0.00 (presolve)
0.00 (postsolve)
Nodes             1
LP iterations     1 (total)
0 (strong br.)
0 (separation)
0 (heuristics)
``````

Note the important block

``````Attempting to find feasible solution for (partial) user-supplied values of discrete variables
Presolving model
0 rows, 0 cols, 0 nonzeros
0 rows, 0 cols, 0 nonzeros
Presolve : Reductions: rows 0(-2); columns 0(-6); elements 0(-7) - Reduced to empty
Solving the original LP from the solution after postsolve
Model   status      : Optimal
Objective value     :  4.0000000000e+00
HiGHS run time      :          0.00
Presolving model
1 rows, 5 cols, 5 nonzeros
1 rows, 4 cols, 4 nonzeros

MIP start solution is feasible, objective value is 4
``````
2 Likes

Thanks, this is a nice observation, but it does not work in my real use case.

OK, I’ll try and do that. Many thanks!

1 Like

If anyone is interested, I adopted a 2-stage strategy:

1. Create a model with fixed “high-level” binary variables. This does not leave much room for optimization, so the (pre-)solver only has little work to do to compute a feasible solution (including values for all unspecified “low-level” binary variables

2. Use the full set of binary variables from the first stage to set start values in a second stage, where the optimizer now starts with a fully specified feasible starting point, and can try to optimize it more.

In the modified knapsack problem above, this looks like:

``````function solve_knapsack_problem(;
profit::Vector{Float64},
weight::Vector{Float64},
capacity::Float64,
chosen_items = nothing,
warmstart = nothing,
)
n = length(weight)
@assert length(profit) == n
model = Model(HiGHS.Optimizer)

@variable(model, x[1:n], Bin)

@variable(model, y, Bin)
@constraint(model, y >= x[1])

# First stage: constrain chosen items
# (y is not specified yet)
if !isnothing(chosen_items)
for i in 1:n
fix(x[i], i ∈ chosen_items)
end
end

# Second stage: set start values for all binary variables
# (including y)
if !isnothing(warmstart)
set_start_value.(x, warmstart.x)
set_start_value(y, warmstart.y)
end

@objective(model, Max, profit' * x - y)
@constraint(model, weight' * x <= capacity)
optimize!(model)

chosen_items = [i for i in 1:n if value(x[i]) > 0.5]
internal_vars = (x = value.(x),
y = value(y))

return (;
chosen_items,
internal_vars)
end
``````

The presolver alone finds a feasible solution in the first stage

``````julia> n = 5;
julia> capacity = 10.0;
julia> profit = [5.0, 3.0, 2.0, 7.0, 4.0];
julia> weight = [2.0, 8.0, 4.0, 2.0, 5.0];

julia> stage1 = solve_knapsack_problem(; profit, weight, capacity, chosen_items = [1, 4])
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
...
(chosen_items = [1, 4], internal_vars = (x = [1.0, 0.0, 0.0, 1.0, 0.0], y = 1.0))
``````

In the second stage, the start values actually form a valid feasible starting point:

``````julia> solve_knapsack_problem(; profit, weight, capacity, warmstart = stage1.internal_vars)
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, 6 cols, 7 nonzeros
2 rows, 5 cols, 6 nonzeros

MIP start solution is feasible, objective value is 11
Objective function is integral with scale 1
# More optimization

(chosen_items = [1, 4, 5], internal_vars = (x = [1.0, 0.0, -0.0, 1.0, 1.0], y = 1.0))
``````
4 Likes

HiGHS now allows a partial discrete assignment. It currently solves the MIP with the discrete assignment fixed to (try to) complete the assignment. This isn’t the best idea sometimes, as only a feasible assignment is needed and solving this MIP to optimality may not be efficient.

Improved treatment of partial discrete assignments is WIP

4 Likes