Closed tlambert03 closed 6 months ago
tlambert03
commented
9 months ago SCIP offers events that we could hook into (https://scipopt.org/doc/html/group__PublicEventMethods.php) and presumably gurobi has similar.
Alternatively, we could just parse stdout (after setting solve.set_verbose(True))
tlambert03
commented
7 months ago just for records: here's an example of verbose output from Scip backend:
feasible solution found by trivial heuristic after 0.0 seconds, objective value 0.000000e+00
presolving:
(round 1, fast) 73 del vars, 292 del conss, 0 add conss, 0 chg bounds, 0 chg sides, 0 chg coeffs, 370 upgd conss, 0 impls, 0 clqs
(round 2, fast) 111 del vars, 350 del conss, 0 add conss, 0 chg bounds, 27 chg sides, 27 chg coeffs, 370 upgd conss, 0 impls, 62 clqs
(round 3, fast) 127 del vars, 350 del conss, 0 add conss, 0 chg bounds, 27 chg sides, 27 chg coeffs, 370 upgd conss, 0 impls, 62 clqs
(0.0s) running MILP presolver
(0.0s) MILP presolver (2 rounds): 0 aggregations, 0 fixings, 0 bound changes
(round 4, exhaustive) 127 del vars, 390 del conss, 0 add conss, 0 chg bounds, 27 chg sides, 27 chg coeffs, 370 upgd conss, 0 impls, 62 clqs
(round 5, exhaustive) 127 del vars, 390 del conss, 0 add conss, 0 chg bounds, 27 chg sides, 27 chg coeffs, 588 upgd conss, 0 impls, 62 clqs
(round 6, medium) 175 del vars, 522 del conss, 238 add conss, 0 chg bounds, 62 chg sides, 62 chg coeffs, 588 upgd conss, 0 impls, 252 clqs
(round 7, fast) 175 del vars, 557 del conss, 238 add conss, 0 chg bounds, 62 chg sides, 62 chg coeffs, 588 upgd conss, 0 impls, 252 clqs
(round 8, fast) 181 del vars, 560 del conss, 238 add conss, 0 chg bounds, 62 chg sides, 62 chg coeffs, 588 upgd conss, 0 impls, 249 clqs
(0.0s) running MILP presolver
(0.0s) MILP presolver found nothing
(round 9, medium) 194 del vars, 573 del conss, 238 add conss, 0 chg bounds, 62 chg sides, 62 chg coeffs, 588 upgd conss, 0 impls, 236 clqs
(round 10, medium) 195 del vars, 574 del conss, 238 add conss, 0 chg bounds, 62 chg sides, 62 chg coeffs, 588 upgd conss, 0 impls, 235 clqs
(round 11, exhaustive) 195 del vars, 574 del conss, 238 add conss, 0 chg bounds, 62 chg sides, 64 chg coeffs, 588 upgd conss, 0 impls, 235 clqs
(round 12, exhaustive) 195 del vars, 574 del conss, 238 add conss, 0 chg bounds, 62 chg sides, 64 chg coeffs, 637 upgd conss, 0 impls, 235 clqs
(round 13, medium) 195 del vars, 602 del conss, 294 add conss, 0 chg bounds, 116 chg sides, 210 chg coeffs, 637 upgd conss, 0 impls, 291 clqs
(round 14, exhaustive) 195 del vars, 781 del conss, 341 add conss, 0 chg bounds, 116 chg sides, 210 chg coeffs, 637 upgd conss, 0 impls, 291 clqs
(round 15, exhaustive) 195 del vars, 781 del conss, 341 add conss, 0 chg bounds, 116 chg sides, 212 chg coeffs, 637 upgd conss, 0 impls, 291 clqs
(round 16, exhaustive) 195 del vars, 808 del conss, 341 add conss, 0 chg bounds, 116 chg sides, 212 chg coeffs, 637 upgd conss, 0 impls, 291 clqs
(0.0s) probing: 141/205 (68.8%) - 0 fixings, 0 aggregations, 92 implications, 0 bound changes
(0.0s) probing aborted: 50/50 successive totally useless probings
(0.0s) symmetry computation started: requiring (bin +, int -, cont +), (fixed: bin -, int +, cont -)
(0.0s) no symmetry present (symcode time: 0.00)
presolving (17 rounds: 17 fast, 12 medium, 8 exhaustive):
195 deleted vars, 808 deleted constraints, 341 added constraints, 0 tightened bounds, 0 added holes, 116 changed sides, 212 changed coefficients
0 implications, 383 cliques
presolved problem has 205 variables (205 bin, 0 int, 0 impl, 0 cont) and 195 constraints
6 constraints of type <knapsack>
132 constraints of type <setppc>
47 constraints of type <and>
5 constraints of type <linear>
5 constraints of type <logicor>
Presolving Time: 0.02
transformed 1/1 original solutions to the transformed problem space
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 | 27 | - | vbounds| 0 | 205 | 196 | 242 | 0 | 0 | 0 | 0 |-6.932304e+03 |-6.853091e+02 | 911.56%| unknown
0.0s| 1 | 0 | 146 | - | 7301k | 0 | 205 | 196 | 242 | 0 | 0 | 0 | 0 |-2.689878e+03 |-6.853091e+02 | 292.51%| unknown
r 0.0s| 1 | 0 | 146 | - |shifting| 0 | 205 | 196 | 242 | 0 | 0 | 0 | 0 |-2.689878e+03 |-1.203164e+03 | 123.57%| unknown
i 0.0s| 1 | 0 | 146 | - | oneopt| 0 | 205 | 196 | 242 | 0 | 0 | 0 | 0 |-2.689878e+03 |-1.788877e+03 | 50.37%| unknown
L 0.1s| 1 | 0 | 146 | - |undercov| 0 | 205 | 196 | 242 | 0 | 0 | 0 | 0 |-2.689878e+03 |-1.885277e+03 | 42.68%| unknown
0.1s| 1 | 0 | 171 | - | 7559k | 0 | 205 | 196 | 254 | 12 | 1 | 0 | 0 |-2.443280e+03 |-1.885277e+03 | 29.60%| unknown
r 0.1s| 1 | 0 | 171 | - |rounding| 0 | 205 | 196 | 254 | 12 | 1 | 0 | 0 |-2.443280e+03 |-1.961850e+03 | 24.54%| unknown
r 0.1s| 1 | 0 | 171 | - |shifting| 0 | 205 | 196 | 254 | 12 | 1 | 0 | 0 |-2.443280e+03 |-1.962669e+03 | 24.49%| unknown
i 0.1s| 1 | 0 | 171 | - | oneopt| 0 | 205 | 196 | 254 | 12 | 1 | 0 | 0 |-2.443280e+03 |-2.160606e+03 | 13.08%| unknown
0.1s| 1 | 0 | 178 | - | 7617k | 0 | 205 | 196 | 257 | 15 | 2 | 0 | 0 |-2.422744e+03 |-2.160606e+03 | 12.13%| unknown
r 0.1s| 1 | 0 | 178 | - |shifting| 0 | 205 | 196 | 257 | 15 | 2 | 0 | 0 |-2.422744e+03 |-2.236327e+03 | 8.34%| unknown
0.1s| 1 | 0 | 182 | - | 7646k | 0 | 205 | 196 | 259 | 17 | 3 | 0 | 0 |-2.413296e+03 |-2.236327e+03 | 7.91%| unknown
0.1s| 1 | 0 | 182 | - | 7649k | 0 | 205 | 196 | 259 | 17 | 3 | 0 | 0 |-2.413296e+03 |-2.236327e+03 | 7.91%| unknown
0.1s| 1 | 0 | 187 | - | 7690k | 0 | 205 | 196 | 262 | 20 | 4 | 0 | 0 |-2.395378e+03 |-2.236327e+03 | 7.11%| unknown
0.1s| 1 | 0 | 187 | - | 7694k | 0 | 205 | 196 | 262 | 20 | 4 | 0 | 0 |-2.395378e+03 |-2.236327e+03 | 7.11%| unknown
time | node | left |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr| dualbound | primalbound | gap | compl.
0.1s| 1 | 0 | 190 | - | 7719k | 0 | 205 | 196 | 264 | 22 | 5 | 0 | 0 |-2.377944e+03 |-2.236327e+03 | 6.33%| unknown
r 0.1s| 1 | 0 | 190 | - |rounding| 0 | 205 | 196 | 263 | 22 | 5 | 0 | 0 |-2.377944e+03 |-2.269949e+03 | 4.76%| unknown
0.1s| 1 | 0 | 190 | - | 7723k | 0 | 205 | 196 | 263 | 22 | 5 | 0 | 0 |-2.377944e+03 |-2.269949e+03 | 4.76%| unknown
0.1s| 1 | 0 | 190 | - | 7764k | 0 | 205 | 196 | 263 | 22 | 5 | 0 | 0 |-2.377944e+03 |-2.269949e+03 | 4.76%| unknown
0.1s| 1 | 0 | 192 | - | 7799k | 0 | 205 | 196 | 259 | 23 | 6 | 0 | 0 |-2.350223e+03 |-2.269949e+03 | 3.54%| unknown
0.1s| 1 | 0 | 192 | - | 7799k | 0 | 205 | 196 | 252 | 23 | 6 | 0 | 0 |-2.350223e+03 |-2.269949e+03 | 3.54%| unknown
0.1s| 1 | 0 | 192 | - | 7799k | 0 | 205 | 181 | 255 | 23 | 8 | 0 | 0 |-2.350223e+03 |-2.269949e+03 | 3.54%| unknown
d 0.1s| 1 | 0 | 192 | - |farkasdi| 0 | 205 | 181 | 255 | 0 | 10 | 0 | 0 |-2.350223e+03 |-2.350223e+03 | 0.00%| unknown
0.1s| 1 | 0 | 192 | - | 7803k | 0 | 205 | 181 | 255 | 23 | 10 | 0 | 0 |-2.350223e+03 |-2.350223e+03 | 0.00%| unknown
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 0.08
Solving Nodes : 1
Primal Bound : -2.35022276908159e+03 (14 solutions)
Dual Bound : -2.35022276908159e+03
Gap : 0.00 %and from gurobi:
Set parameter Username
Academic license - for non-commercial use only - expires 2025-03-25
Set parameter OutputFlag to value 1
Set parameter NonConvex to value 2
Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (mac64[arm])
CPU model: Apple M2 Max
Thread count: 12 physical cores, 12 logical processors, using up to 1 threads
Optimize a model with 0 rows, 399 columns and 0 nonzeros
Model fingerprint: 0x217f4822
Model has 664 quadratic constraints
Variable types: 0 continuous, 399 integer (399 binary)
Coefficient statistics:
Matrix range [0e+00, 0e+00]
QLMatrix range [1e+00, 4e+00]
Objective range [5e-01, 2e+02]
Bounds range [1e+00, 1e+00]
RHS range [0e+00, 0e+00]
QRHS range [1e+00, 3e+00]
Found heuristic solution: objective 0.0000000
Presolve added 149 rows and 0 columns
Presolve removed 0 rows and 244 columns
Presolve time: 0.01s
Presolved: 149 rows, 155 columns, 416 nonzeros
Found heuristic solution: objective -336.8315849
Variable types: 0 continuous, 155 integer (155 binary)
Found heuristic solution: objective -616.9683616
Root relaxation: objective -2.470905e+03, 59 iterations, 0.00 seconds (0.00 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 -2470.9053 0 59 -616.96836 -2470.9053 300% - 0s
H 0 0 -2043.115757 -2470.9053 20.9% - 0s
H 0 0 -2134.704132 -2470.9053 15.7% - 0s
0 0 -2233.8300 0 6 -2134.7041 -2233.8300 4.64% - 0s
H 0 0 -2156.847407 -2233.8300 3.57% - 0s
H 0 0 -2184.750092 -2233.8300 2.25% - 0s
H 0 0 -2228.487141 -2233.8300 0.24% - 0s
Cutting planes:
Gomory: 3
Clique: 1
MIR: 8
Zero half: 3
Explored 1 nodes (77 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 1 (of 12 available processors)
Solution count 8: -2228.49 -2184.75 -2156.85 ... 0
No other solutions better than -2228.49
Optimal solution found (tolerance 1.00e-04)
Best objective -2.228487140775e+03, best bound -2.228487140775e+03, gap 0.0000%(prolly need a more complex problem to see more from gurobi)
tlambert03
commented
7 months ago also a note to self. here's a hacky script that will run the solver in another thread, capture output, and print the gap as it comes. Can be used as a starting point (but may well only be a unix solution)
import os
import queue
import re
import sys
import threading
import ilpy
import motile
from motile.constraints import MaxChildren, MaxParents
from motile.costs import Appear, EdgeDistance, EdgeSelection, NodeSelection, Split
from motile.data import arlo_graph
graph = arlo_graph()
solver = motile.Solver(graph)
solver.add_costs(NodeSelection(weight=-1.0, attribute="score", constant=-100.0))
solver.add_costs(
EdgeSelection(weight=0.5, attribute="prediction_distance", constant=-1.0)
)
solver.add_costs(EdgeDistance(position_attributes=("x",), weight=0.5))
solver.add_costs(Appear(constant=200.0, attribute="score", weight=-1.0))
solver.add_costs(Split(constant=100.0, attribute="score", weight=1.0))
solver.add_constraints(MaxParents(1))
solver.add_constraints(MaxChildren(2))
def capture_output(q, func, *args, **kwargs):
# Save the original stdout file descriptor
original_stdout_fd = sys.stdout.fileno()
# Create a duplicate of the original stdout file descriptor
saved_stdout_fd = os.dup(original_stdout_fd)
# Create a temporary file and replace the original stdout file descriptor with it
with open("temp.txt", "w") as f:
os.dup2(f.fileno(), original_stdout_fd)
# Call the function
result = func(*args, **kwargs)
# Restore the original stdout file descriptor using the duplicate
os.dup2(saved_stdout_fd, original_stdout_fd)
# Read the output from the temporary file and put it in the queue
with open("temp.txt") as f:
for line in f:
q.put(line)
q.put(None) # Signal that we're done
return result
def log_output(q: queue.Queue) -> None:
# Get lines from the queue and log them
for line in iter(q.get, None):
if any(x in line for x in {"probing", "best"}):
continue
# dumb way to get the gap, it's the only thing expressed as a percentage
if match := re.search(r"(\d+(\.?\d+))%", line):
print(match.group(1))
q = queue.Queue()
t1 = threading.Thread(
target=capture_output,
args=(q, solver.solve),
kwargs={"pref": ilpy.Preference.Scip, "verbose": True},
)
t2 = threading.Thread(target=log_output, args=(q,))
t1.start()
t2.start()
t1.join()
t2.join()
cmalinmayor
commented
6 months ago Resolved by #56
look into passing progress info on from the backend solver. such as an iteration callback or something