Add setBasis to highspy

[grjzwaan]

Description
I expected if I set an optimal solution the LP would be solved without iterations, but it seems to ignore the supplied solution.

In the script I do the following:

1. Solve an LP and get solution x
2. Solve the LP again, but set x as the solution

(1) and (2) take the same amount of time. Am I using setSolution wrong?

Environment
Windows,
Python
Running HiGHS 1.7.0 (git hash: 27ccfaa): Copyright (c) 2024 HiGHS under MIT licence terms

Script

import numpy as np
import highspy

n = 20_000
m = 10
q = 5

A = np.random.rand(n, m)
B = np.random.rand(n, m, q) - 0.5
b = np.random.rand(q) * -0.2 * n


def create_lp(h, A, B, b):
    inf = highspy.kHighsInf

    # Variables
    h.addCols(n * m, A.flatten(), np.zeros((n, m)).flatten(), np.ones((n, m)).flatten(), 0, 0, 0, 0)

    # Constraint per segment
    lower = np.full(n, -inf)
    upper = np.full(n, 1)
    num_nz = n * m
    start = np.arange(n * m, step=m)
    index = np.arange(n * m)
    value = np.ones(n * m)
    h.addRows(n, lower, upper, num_nz, start, index, value)

    # Contraints on the dimensions
    for k in range(q):
        h.addRow(-inf, b[k], n * m, np.arange(n * m), B[:, :, k].flatten())


# Options
def highs():
    h = highspy.Highs()
    options = h.getOptions()
    options.presolve = "off"
    options.solver = "simplex"
    options.time_limit = 120
    #options.output_flag = False
    #options.log_to_console = False
    # options.threads = 1  # Windows bug https://github.com/ERGO-Code/HiGHS/issues/1670
    #h.setOptionValue("log_to_console", False)

    h.passOptions(options)
    return h


h = highs()
# Run for the first time
create_lp(h, A, B, b)
h.changeObjectiveSense(highspy.ObjSense.kMaximize)
h.run()
print("Total HiGHS run time is ", h.getRunTime())

solution = h.getSolution()


h = highs()
# Run for the second time
create_lp(h, A, B, b)
h.setSolution(solution)
h.changeObjectiveSense(highspy.ObjSense.kMaximize)
h.run()
print("Total HiGHS run time is ", h.getRunTime())

Output:

Running HiGHS 1.7.0 (git hash: 27ccfaa): Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
  Matrix [1e-07, 1e+00]
  Cost   [8e-06, 1e+00]
  Bound  [1e+00, 1e+00]
  RHS    [1e+00, 4e+03]
Solving LP without presolve, or with basis, or unconstrained
Using EKK dual simplex solver - serial
  Iteration        Objective     Infeasibilities num(sum)
          0     0.0000000000e+00 Ph1: 0(0) 0s
      11404     5.0386738115e+04 Pr: 8795(8408.25) 5s
      24926     1.5933593926e+04 Pr: 0(0) 8s
Model   status      : Optimal
Simplex   iterations: 24926
Objective value     :  1.5933593926e+04
HiGHS run time      :          8.49
Total HiGHS run time is  8.491375300101936
Running HiGHS 1.7.0 (git hash: 27ccfaa): Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
  Matrix [1e-07, 1e+00]
  Cost   [8e-06, 1e+00]
  Bound  [1e+00, 1e+00]
  RHS    [1e+00, 4e+03]
Solving LP without presolve, or with basis, or unconstrained
Using EKK dual simplex solver - serial
  Iteration        Objective     Infeasibilities num(sum)
          0     0.0000000000e+00 Ph1: 0(0) 0s
      16599     2.8528565947e+04 Pr: 4112(3022.18) 5s
      24926     1.5933593926e+04 Pr: 0(0) 8s
Model   status      : Optimal
Simplex   iterations: 24926
Objective value     :  1.5933593926e+04
HiGHS run time      :          7.86
Total HiGHS run time is  7.864553200080991

[jajhall]

I've reproduced this, and checked that h.setSolution(solution) is returning OK, but will have to re-create it in C++ in order to see what's going on.

[jajhall]

You're using h.setSolution(solution) correctly and, internally, HiGHS is doing what it can. The reason that it takes as long and performs the same number of simplex iterations is that your solution is massively degenerate, so the initial simplex basis generated from the solution is far from optimal.

For brevity, I dropped n from 20_000 to 200, so the LP has 2000 variables and 205 constraints, and got the same behaviour.

When the basis is created, only 10 of the variables and none of the constraints are off their bounds. If the solution were non-degenerate, there would be 205 variables/constraints off their bounds. So only 10 of the necessary 205 basic variables in the optimal solution can be identified. The rest are added so that the basis matrix is well-conditioned. It's unfortunate that this means that the simplex algorithm starts from the origin (again) but not surprising in the context of the degeneracy in your problem.

When re-starting an LP, it's much better to use a basis rather than a solution. I've done this in the C++ code and the second solve takes zero iterations - because it starts from the optimal basis:

Unfortunately, although getBasis is in highspy, setBasis is not, so this form of hot start cannot be used in highspy. Hence the change of name for this issue.

[grjzwaan]

Thanks for the answer - that explains the extra iterations.

--- aside ---

I'm very happy with the HiGHS solver, and feel free to not answer by question below! It's more me not understanding why my LP is degenerate than a question on the solver.

It's been awhile, but I link degeneracy to redundant constraints. Somehow I quite don't understand how this LP is degenerate.

The intention at least to make an LP where I have to pick 1 option from m alternatives for each of the n items, plus q extra constraints over all items. (In the example above I had a <= instead of the =)

So even simpler:

max 
2 1 0 1 2 3
s.t.
1 1 1 0 0 0 = 1
0 0 0 1 1 1 = 1

I expect (perhaps totally wrong) that the solution (x_1=1, x_6=1) would lead to the basis

1 0
0 1

which is not degenerate.

But even in this simpler setting HiGHS solves the LP again, from which I conclude it's degeneracy again.

[jajhall]

Yes, if you have an LP with an optimal solution, and add constraints that are active at the optimal solution, then the solution for the modified LP will be degenerate, as the slack variables for those constraints will be basic and zero.

In the example you've given, if the variables are just non-negative, then the optimal solution is the one you give, with both basic variables being positive, so it's not degenerate.

However, in the problem generated by your Python code, you've put upper bounds of 1 on all the variables. The optimal solution has 1795 values at 0 and 195 values at 1, a total of 1990 / 2000, so 10 are off their bounds (as observed earlier). All 195 variables at their upper bounds are basic, so the solution is degenerate.

I removed the upper bounds on the variables, and the solution was unchanged: the upper bounds were redundant, and the solution of the modified LP was not degenerate. Hence, when I used setSolution to resolve the LP, the optimal basis was deduced, and no simplex iterations were performed.

[grjzwaan]

Thanks! I got it now - I didn’t think about the upper bounds on the variables. Makes sense. Op zo 28 apr 2024 om 14:32 schreef Julian Hall ***@***.***>

…

Yes, if you have an LP with an optimal solution, and add constraints that are active at the optimal solution, then the solution for the modified LP will be degenerate, as the slack variables for those constraints will be basic and zero. In the example you've given, if the variables are just non-negative, then the optimal solution is the one you give, with both basic variables being positive, so it's not degenerate. However, in the problem generated by your Python code, you've put upper bounds of 1 on all the variables. The optimal solution has 1795 values at 0 and 195 values at 1, a total of 1990 / 2000, with 10 off their bounds. All 195 variables at their upper bounds are basic, so the solution is degenerate. I removed the upper bounds on the variables, and the solution was unchanged: the upper bounds were redundant, and the solution of the modified LP was not degenerate. Hence, when I used setSolution to resolve the LP, the optimal basis was deduced, and no simplex iterations were performed. — Reply to this email directly, view it on GitHub <#1733 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AFZEPSCYLK3ZMMEQI3QLT43Y7TT6LAVCNFSM6AAAAABGYRL7EOVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDAOBRGQ3TAMJVG4> . You are receiving this because you authored the thread.Message ID: ***@***.***>

[jajhall]

Fixed by #1740