Runner: record more metrics

[siddharth-krishna]

For MIP, also check if they've found an Int feasible solution and then check duality gap -- measure of how well they've done.

For LP, if we use IPM, do we crossover to get a basic solution? What solution quality do we require? Vertex or optimal?

[jacek-oet]

I'm running solver highs for this MIP problem

mip_1.lp

Minimize
  obj: 5 x1 + 7 x2 + 3 x3 + 4 x4

Subject To
  c1: 2 x1 + 4 x2 + 3 x3 + 5 x4 >= 15
  c2: 3 x1 + 2 x2 + 5 x3 + 4 x4 <= 20
  c3: 4 x1 + 3 x2 + 2 x3 + 3 x4 <= 10

Bounds
  0 <= x1 <= 10
  0 <= x2 <= 5
  0 <= x3 <= 6
  0 <= x4 <= 8

Integer
  x1 x2

End

command
python runner/run_solver.py highs runner/benchmarks/mip_1.lp

Note:
The solver name highs can be replaced with other solvers like glpk, gurobi, or scip depending on which solver you'd like to use. For example:

glpk: python runner/run_solver.py glpk runner/benchmarks/mip_1.lp
gurobi: python runner/run_solver.py gurobi runner/benchmarks/mip_1.lp
scip: python runner/run_solver.py scip runner/benchmarks/mip_1.lp

Highs

Output

Running HiGHS 1.7.2 (git hash: 184e327): Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
  Matrix [2e+00, 5e+00]
  Cost   [3e+00, 7e+00]
  Bound  [5e+00, 1e+01]
  RHS    [1e+01, 2e+01]
Presolving model
3 rows, 4 cols, 12 nonzeros  0s
3 rows, 4 cols, 12 nonzeros  0s

Solving MIP model with:
   3 rows
   4 cols (0 binary, 2 integer, 0 implied int., 2 continuous)
   12 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%   0               inf                  inf        0      0      0         0     0.0s
 T       0       0         0   0.00%   0               12               100.00%        0      0      0         1     0.0s

Solving report
  Status            Optimal
  Primal bound      12
  Dual bound        12
  Gap               0% (tolerance: 0.01%)
  Solution status   feasible
                    12 (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)
Status: ok
Termination condition: optimal
Solution: 4 primals, 3 duals
Objective: 1.20e+01
Solver model: available
Solver message: optimal
{"runtime": 0.012918710708618164, "status": "ok", "condition": "optimal", "objective": 12.0}

Summary

The output from HiGHS indicates that the solver successfully found an integer feasible solution for the MIP

• Objective: The solver found an optimal objective value of 12.
• Solution status: The solver found a feasible solution.
• Dual bound: The dual bound is 12, which matches the primal bound, indicating that the solution is optimal with a gap of 0%.

This confirms that the solver was able to find an integer feasible solution, as indicated by the "Solution status: feasible" and "Termination condition: optimal". Additionally, the primal and dual bounds matching, with a 0% gap, confirms that the solution is optimal.

glpk

Output

Dual values of MILP couldn't be parsed
Status: ok
Termination condition: optimal
Solution: 4 primals, 0 duals
Objective: 1.20e+01
Solver model: not available
Solver message: integer optimal
{"runtime": 0.00967717170715332, "status": "ok", "condition": "optimal", "objective": 12.0}

Summary

Integer Feasibility:
The solution found is integer-feasible, as indicated by the message "integer optimal."

Duality Gap:
GLPK does not provide duality gaps for MILP problems.

Gurobi

Output

Restricted license - for non-production use only - expires 2025-11-24
Reading time = 0.00 seconds
obj: 3 rows, 4 columns, 12 nonzeros
Gurobi Optimizer version 11.0.3 build v11.0.3rc0 (linux64 - "Ubuntu 22.04.3 LTS")
Optimize a model with 3 rows, 4 columns and 12 nonzeros
Model fingerprint: 0xd0e35d86
Variable types: 2 continuous, 2 integer (0 binary)
Coefficient statistics:
  Matrix range     [2e+00, 5e+00]
  Objective range  [3e+00, 7e+00]
  Bounds range     [5e+00, 1e+01]
  RHS range        [1e+01, 2e+01]
Presolve time: 0.01s
Presolved: 3 rows, 4 columns, 12 nonzeros
Variable types: 2 continuous, 2 integer (0 binary)
Found heuristic solution: objective 12.0000000

Root relaxation: cutoff, 0 iterations, 0.00 seconds (0.00 work units)

Explored 1 nodes (0 simplex iterations) in 0.03 seconds (0.00 work units)
Thread count was 4 (of 4 available processors)

Solution count 1: 12 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.200000000000e+01, best bound 1.200000000000e+01, gap 0.0000%
Dual values of MILP couldn't be parsed
Status: ok
Termination condition: optimal
Solution: 4 primals, 0 duals
Objective: 1.20e+01
Solver model: available
Solver message: 2
{"runtime": 0.05907893180847168, "status": "ok", "condition": "optimal", "objective": 12.0}

Summary

Integer Feasibility:
The line "Found heuristic solution: objective 12.0000000" indicates that Gurobi found a heuristic integer-feasible solution with an objective value of 12.

Duality Gap:
The lines "Best objective 1.200000000000e+01, best bound 1.200000000000e+01, gap 0.0000%" show that Gurobi found both the best objective (primal value) and the best bound (dual value), both equal to 12, resulting in a duality gap of 0%. This confirms that an integer-feasible solution was found with no duality gap.

SCIP

Output

original problem has 4 variables (0 bin, 2 int, 0 impl, 2 cont) and 3 constraints
presolving:
   (0.0s) symmetry computation started: requiring (bin +, int +, cont +), (fixed: bin -, int -, cont -)
   (0.0s) no symmetry present (symcode time: 0.00)
presolving (0 rounds: 0 fast, 0 medium, 0 exhaustive):
 0 deleted vars, 0 deleted constraints, 0 added constraints, 0 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
 0 implications, 0 cliques
presolved problem has 4 variables (0 bin, 2 int, 0 impl, 2 cont) and 3 constraints
      3 constraints of type <linear>
Presolving Time: 0.00

 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl. 
p 0.0s|     1 |     0 |     1 |     - |shiftand|   0 |   4 |   3 |   3 |   0 |  0 |   0 |   0 | 0.000000e+00 | 1.200000e+01 |    Inf | unknown
  0.0s|     1 |     0 |     2 |     - |   611k |   0 |   4 |   3 |   3 |   0 |  0 |   0 |   0 | 1.200000e+01 | 1.200000e+01 |   0.00%| unknown

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 0.00
Solving Nodes      : 1
Primal Bound       : +1.20000000000000e+01 (1 solutions)
Dual Bound         : +1.20000000000000e+01
Gap                : 0.00 %
Status: ok
Termination condition: optimal
Solution: 4 primals, 3 duals
Objective: 1.20e+01
Solver model: available
Solver message: optimal
{"runtime": 0.0071451663970947266, "status": "ok", "condition": "optimal", "objective": 12.0}

Summary

In the SCIP solver output:

Gap: 0%
Primal Bound: +1.20000000000000e+01 (1 solution)
Termination condition: optimal
SCIP Status: problem is solved [optimal solution found]
The fact that the primal bound is reported, the gap is 0%, and the solver reached optimality all indicate that an integer-feasible solution was found.

[siddharth-krishna]

@FabianHofmann , if you still have some time this week, we would also love your review on this code:

solver-benchmark/runner/run_solver.py

Lines 98 to 102 in ffc342f

	if is_mip_problem(solver_model, solver_name):
	duality_gap = get_duality_gap(solver_model, solver_name)
	max_integrality_violation = calculate_integrality_violation(
	solver_result.solution.primal
	)

We added max integrality violation and duality gap to the metrics recorded for MILPs. But I'm not sure if we've done it correctly. Also not sure what's the best way to analyze or present this information on the website? Currently, we've added a table to the Benchmark Details page, so if you select a MILP benchmark then you can see these 2 metrics for each solver:

Thanks!

[FabianHofmann]

@siddharth-krishna thanks for pointing that to me. The function itself is well written. I see the potential issue that all values are checked and not only those which are integer variables. So this would only work if we have a pure integer problem. Should I make a proposal to fix this?

[siddharth-krishna]

Thanks, Fabian, that would be super helpful. If you don't have time you could also make an issue with pointers to what we need to do. 🙏

[FabianHofmann]

@siddharth-krishna I have tried to come up with a solution, but it is quite hard since at this stage where we don't have the properties of the variables, whether there are integer variables or not. The only thing I can think about is to try to extract this quantity in the linopy function. I will look further what we can do here.

the problem files can be both in MPS and LP format right?

[siddharth-krishna]

Thank you. It would also be useful for us to be able to get stats on how many variables are linear/integer/binary from linopy, we can display this on the website too. Currently we are doing it like this: https://github.com/open-energy-transition/solver-benchmark/blob/main/benchmarks/size_measurement.py

Yes, some of our benchmarks are MPS and some are LP.

[FabianHofmann]

hey @siddharth-krishna, the code you sent seems working well. so if you have a linopy.Model m instance available, what you can do is:

n_continuous = sum(v.size for k, v in m.variables.continuous.items())
n_integers = sum(v.size for k, v in m.variables.integers.items())
n_binaries = sum(v.size for k, v in m.variables.binaries.items())

but if we only have a raw file we without the linopy model, the current approach is good.

[jajhall]

Since you've passed the models to the solver, they should all be able to return the model in code, including a statement of the type of each variable. Since this is only problem data, you can use HiGHS (say) to get this, whatever solver you are benchmarking.

[siddharth-krishna]

@FabianHofmann (and @danielelerede-oet) I am afraid the code in https://github.com/open-energy-transition/solver-benchmark/blob/main/benchmarks/size_measurement.py does not work for MPS files where the integrality of some variables is specified using lines such as:

    INT1      'MARKER'                 'INTORG'
    C03     R02              1.1   R03              1.0
    C04     R01             -2.0   R04              2.8
    INT1END   'MARKER'                 'INTEND'

@jajhall , how can I get the type of each variable using highspy? I can read a problem file and inspect it using the following code, but I don't see which of the functions listed in the docs lets me enumerate the types of each variable. Thanks!

import highspy
h = highspy.Highs()
status = h.readModel("filename.mps")
info = h.getInfo()

[jajhall]

@jajhall , how can I get the type of each variable using highspy?

[status, integrality] = h.getColIntegrality(col)