[SCIP] performance for scheduling problems
Marc Pfetsch
pfetsch at mathematik.tu-darmstadt.de
Thu Jun 13 21:15:20 CEST 2024
May I add to Sascha's answer that of course contributions and
improvements to SCIP are also very welcome! This is important to improve
SCIP in the future.
Best
Marc
On 13/06/2024 20:38, s schnug wrote:
> "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 <mailto: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 <http://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 <http://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 <http://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 <http://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 <mailto:Scip at zib.de>
> https://listserv.zib.de/mailman/listinfo/scip
> <https://listserv.zib.de/mailman/listinfo/scip>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
More information about the Scip
mailing list