[SCIP] performance for scheduling problems
s schnug
sascha.schnug at gmail.com
Thu Jun 13 20:38:36 CEST 2024
"I know many scheduling heuristics, but I doubt that Gurobi is using
scheduling-specific heuristics behind the scenes."
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.
Howewer, two recommendations from me:
Recommendation A:
SCIP actually has some scheduling-specific code living in
scip/applications/Scheduler/...
I think the canonical resource on this is: Heinz, Stefan, and J.
Christopher Beck. "Solving resource allocation/scheduling problems with
constraint integer programming." (2011).
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.
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.
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).
Recommendation B:
If you can live with swapping out SCIP for another FOSS project: use
(googles) ortools' cp-sat solver! At least try it!
It's a SAT/CP/MILP-Hybrid and brings all the things you want:
- 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
- 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
- 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
In some sense, CP-SAT feels MILP-like although there are no continuous
variables! Discrete domains only!
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!
-----
Greetings,
Sascha
Am Do., 13. Juni 2024 um 19:07 Uhr schrieb Brannon King <
countprimes at gmail.com>:
> I know it's improper to compare SCIP to commercial solvers. However,
> some days I really wish that SCIP was faster for my experimentation
> purposes. For scheduling problems in particular, are there SCIP
> parameters that you tweak to get more performance? Are there known
> cuts/heuristics that aren't coded in SCIP that address these types of
> problems? I know many scheduling heuristics, but I doubt that Gurobi
> is using scheduling-specific heuristics behind the scenes.
>
> I offer this code below as proof of my performance conundrum. CPLEX
> tends to be 2-3x worse than Gurobi on these 10x10s, although it's
> constraint solver is faster than Gurobi. SCIP is on average 100x worse
> than Gurobi.
>
> import job_shop_lib as jsl # get this from pypi
> import job_shop_lib.generators as jslg
> import gurobipy as grb
> import pyscipopt as scp
>
>
> def as_gurobi_balas_model(instance: jsl.JobShopInstance):
> model = grb.Model(instance.name)
> O = M = instance.num_machines
> s = model.addMVar((instance.num_jobs, O), vtype='C') # start time
> for each op o on job j
> cmax = model.addVar(name='c_max')
> model.setObjective(cmax, grb.GRB.MINIMIZE)
>
> bigM = 1
> lookup = {m: [] for m in range(M)}
> for job in instance.jobs:
> for op in job: # operation, (machine, delay)
> o = op.position_in_job
> j = op.job_id
> model.addConstr((s[j, o + 1] if o + 1 < O else cmax) -
> s[j, o] >= op.duration) # op precedence
> lookup[op.machine_id].append((j, o, op.duration))
> bigM += op.duration
>
> for m in range(M):
> for l1, (j1, o1, d1) in enumerate(lookup[m]):
> for l2, (j2, o2, d2) in enumerate(lookup[m][l1 + 1:], l1 + 1):
> x = model.addVar(vtype='B') # no overlap, indicator
> constraints are slower
> model.addConstr(s[j2, o2] >= d1 + s[j1, o1] - bigM * (1 -
> x))
> model.addConstr(s[j1, o1] >= d2 + s[j2, o2] - bigM * x)
>
> return model
>
>
> def as_scip_balas_model(instance: jsl.JobShopInstance):
> model = scp.Model(instance.name)
> O = M = instance.num_machines
> s = {(j, o): model.addVar(vtype='C') for j in
> range(instance.num_jobs) for o in range(O)}
> cmax = model.addVar(name='c_max')
> model.setObjective(cmax)
>
> bigM = 1
> lookup = {m: [] for m in range(M)}
> for job in instance.jobs:
> for op in job: # operation, (machine, delay)
> o = op.position_in_job
> j = op.job_id
> model.addCons((s[j, o + 1] if o + 1 < O else cmax) - s[j,
> o] >= op.duration) # op precedence
> lookup[op.machine_id].append((j, o, op.duration))
> bigM += op.duration
>
> for m in range(M):
> for l1, (j1, o1, d1) in enumerate(lookup[m]):
> for l2, (j2, o2, d2) in enumerate(lookup[m][l1 + 1:], l1 + 1):
> x = model.addVar(vtype='B') # no overlap, indicator
> constraints are slower
> model.addCons(s[j2, o2] >= d1 + s[j1, o1] - bigM * (1 - x))
> model.addCons(s[j1, o1] >= d2 + s[j2, o2] - bigM * x)
>
> return model
>
>
> bgen = jslg.BasicGenerator(duration_range=(20, 200), seed=42,
> num_jobs=10, num_machines=10)
> instance1 = bgen.generate()
> model_gur = as_gurobi_balas_model(instance1)
> model_scp = as_scip_balas_model(instance1)
>
> model_gur.optimize()
> model_scp.optimize()
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20240613/8eec7e18/attachment.html>
More information about the Scip
mailing list