<div dir="ltr">"I know many scheduling heuristics, but I doubt that Gurobi is using scheduling-specific heuristics behind the scenes."<br><br>I wouldn't be to sure about that. It's quite possible they do, if they somehow can reconstruct the scheduling-structure from the MILP. As there are papers about reconstructing multi-commodity flow problems and such from a MILP, i guess it might be possible too with scheduling problems.<br><br><br>Howewer, two recommendations from me:<br><br>Recommendation A:<br><br>SCIP actually has some scheduling-specific code living in scip/applications/Scheduler/...<br><br>I think the canonical resource on this is: Heinz, Stefan, and J. Christopher Beck. "Solving resource allocation/scheduling problems with constraint integer programming." (2011).<br><br>As it's kinda hidden (the SCIP docs make you think it's just one more constraint-handler; a first-class citizen like the others; but the path forces you to take care about how to include it) i would be surprised to see it being accessible through some Python-Interface.<br><br>I ran some problems with it (using C++) and it seems to work (no dead / deprecated code), although i did not analyze it in detail.<br><br>Without checking above resource again, it should contain presolving-rules, primal-heuristics (e.g. list-scheduling; one of those you indicated), constraint-propagation (as in constraint-programming for scheduling-problems), conflict-analysis and cutting-plan additions tuned to the cumulative constraint (which generalizes the disjunctive constraint).<br><br>Recommendation B:<br><br>If you can live with swapping out SCIP for another FOSS project: use (googles) ortools' cp-sat solver! At least try it!<br><br>It's a SAT/CP/MILP-Hybrid and brings all the things you want:<br><br>- global scheduling constraints: API (easier modelling) as well as CP-style propagation (e.g. energetic reasoning); also providing structure to local-search / large-neighborhood search components<br>- very strong conflict-analysis aka "learning" due to having a L(azy)-C(lause)-G(eneration) core which fully connects SAT-style conflict-analysis and the CP-style propagation of global constraints<br>- multicore out of the box: currently tuned towards >= 16 cores i guess; heavily based on synced/communicating portfolios including scheduling-specific local-search and large-neighborhood search but also "LP-relaxation following" procedures and many other things<br><br>In some sense, CP-SAT feels MILP-like although there are no continuous variables! Discrete domains only!<br><br>While SCIP has much better documentation than ortools, ortools has way more example spanning multiple languages and if you want to give it a try, there is a lot to help!<br><br>-----<br><br>Greetings,<br>Sascha<br><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Am Do., 13. Juni 2024 um 19:07 Uhr schrieb Brannon King <<a href="mailto:countprimes@gmail.com">countprimes@gmail.com</a>>:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">I know it's improper to compare SCIP to commercial solvers. However,<br>
some days I really wish that SCIP was faster for my experimentation<br>
purposes. For scheduling problems in particular, are there SCIP<br>
parameters that you tweak to get more performance? Are there known<br>
cuts/heuristics that aren't coded in SCIP that address these types of<br>
problems? I know many scheduling heuristics, but I doubt that Gurobi<br>
is using scheduling-specific heuristics behind the scenes.<br>
<br>
I offer this code below as proof of my performance conundrum. CPLEX<br>
tends to be 2-3x worse than Gurobi on these 10x10s, although it's<br>
constraint solver is faster than Gurobi. SCIP is on average 100x worse<br>
than Gurobi.<br>
<br>
import job_shop_lib as jsl # get this from pypi<br>
import job_shop_lib.generators as jslg<br>
import gurobipy as grb<br>
import pyscipopt as scp<br>
<br>
<br>
def as_gurobi_balas_model(instance: jsl.JobShopInstance):<br>
model = grb.Model(<a href="http://instance.name" rel="noreferrer" target="_blank">instance.name</a>)<br>
O = M = instance.num_machines<br>
s = model.addMVar((instance.num_jobs, O), vtype='C') # start time<br>
for each op o on job j<br>
cmax = model.addVar(name='c_max')<br>
model.setObjective(cmax, grb.GRB.MINIMIZE)<br>
<br>
bigM = 1<br>
lookup = {m: [] for m in range(M)}<br>
for job in <a href="http://instance.jobs" rel="noreferrer" target="_blank">instance.jobs</a>:<br>
for op in job: # operation, (machine, delay)<br>
o = op.position_in_job<br>
j = op.job_id<br>
model.addConstr((s[j, o + 1] if o + 1 < O else cmax) -<br>
s[j, o] >= op.duration) # op precedence<br>
lookup[op.machine_id].append((j, o, op.duration))<br>
bigM += op.duration<br>
<br>
for m in range(M):<br>
for l1, (j1, o1, d1) in enumerate(lookup[m]):<br>
for l2, (j2, o2, d2) in enumerate(lookup[m][l1 + 1:], l1 + 1):<br>
x = model.addVar(vtype='B') # no overlap, indicator<br>
constraints are slower<br>
model.addConstr(s[j2, o2] >= d1 + s[j1, o1] - bigM * (1 - x))<br>
model.addConstr(s[j1, o1] >= d2 + s[j2, o2] - bigM * x)<br>
<br>
return model<br>
<br>
<br>
def as_scip_balas_model(instance: jsl.JobShopInstance):<br>
model = scp.Model(<a href="http://instance.name" rel="noreferrer" target="_blank">instance.name</a>)<br>
O = M = instance.num_machines<br>
s = {(j, o): model.addVar(vtype='C') for j in<br>
range(instance.num_jobs) for o in range(O)}<br>
cmax = model.addVar(name='c_max')<br>
model.setObjective(cmax)<br>
<br>
bigM = 1<br>
lookup = {m: [] for m in range(M)}<br>
for job in <a href="http://instance.jobs" rel="noreferrer" target="_blank">instance.jobs</a>:<br>
for op in job: # operation, (machine, delay)<br>
o = op.position_in_job<br>
j = op.job_id<br>
model.addCons((s[j, o + 1] if o + 1 < O else cmax) - s[j,<br>
o] >= op.duration) # op precedence<br>
lookup[op.machine_id].append((j, o, op.duration))<br>
bigM += op.duration<br>
<br>
for m in range(M):<br>
for l1, (j1, o1, d1) in enumerate(lookup[m]):<br>
for l2, (j2, o2, d2) in enumerate(lookup[m][l1 + 1:], l1 + 1):<br>
x = model.addVar(vtype='B') # no overlap, indicator<br>
constraints are slower<br>
model.addCons(s[j2, o2] >= d1 + s[j1, o1] - bigM * (1 - x))<br>
model.addCons(s[j1, o1] >= d2 + s[j2, o2] - bigM * x)<br>
<br>
return model<br>
<br>
<br>
bgen = jslg.BasicGenerator(duration_range=(20, 200), seed=42,<br>
num_jobs=10, num_machines=10)<br>
instance1 = bgen.generate()<br>
model_gur = as_gurobi_balas_model(instance1)<br>
model_scp = as_scip_balas_model(instance1)<br>
<br>
model_gur.optimize()<br>
model_scp.optimize()<br>
_______________________________________________<br>
Scip mailing list<br>
<a href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a><br>
<a href="https://listserv.zib.de/mailman/listinfo/scip" rel="noreferrer" target="_blank">https://listserv.zib.de/mailman/listinfo/scip</a><br>
</blockquote></div>