jacek-oet
commented
1 month ago 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
Endcommand
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.lpHighs
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.
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?