[SCIP] performance for scheduling problems

[Brannon King]

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()