Despite solution hinting model takes A LOT of time to find an initial solution

[S. K.]

So I am having a more complex job scheduling problem with alternatives, transition costs, lateness penalties, earliest possible start date, dependencies between jobs, a machine calendar with times where all machines or some of them are shut off, and more.

I am dealing with 22 machines at the moment and about 350 jobs.

I'm doing a "small" run where the jobs are only allowed to be manufactured on the machine they are currently scheduled on. So I only optimize the time schedule on each machine .

In the "big" run a job can be manufactured on every machine that is capable to do so.

Depending on the job it can now be manufactured on 1 up to 9 machines (instead of only 1 chosen machine like in the small run).

Right before I am doing a big run, I do a small run, and then take the solution from this run to hint the big one.

Right now I am only handling a smaller test set with 9 machines and 243 jobs.

In the small run my model creates 34584 variables and in the big run 206441.

The name of my old model is model, the name of my new model is model_free (because the jobs have a FREE choice in machines).

I hint the new model the following way:

### Hint NEW model with old solver data

model_free.Proto().solution_hint.Clear()

old_model_list = [field.name for (i, field) in enumerate(model.Proto().variables) ]

new_model_list = [field.name for (i, field) in enumerate(model_free.Proto().variables) ]

for (i, field) in enumerate(model_free.Proto().variables):

  if field.name in old_model_list:

    index_old_model = old_model_list.index(field.name)

    model_free.Proto().solution_hint.vars.append(i)

    model_free.Proto().solution_hint.values.append( solver.ResponseProto().solution[index_old_model])  

  else:

    if 'rank' in field.name:

      model_free.Proto().solution_hint.vars.append(i)

      model_free.Proto().solution_hint.values.append(-1)

    elif 'duration' in field.name:

      continue

    elif 'termin' in field.name:

      continue

    elif 'delta' in field.name:

      continue

    elif 'ueberzogen' in field.name:

      continue        

    else:

      model_free.Proto().solution_hint.vars.append(i)

      model_free.Proto().solution_hint.values.append(0)  

Most of the variables that don't exist in the old model are 0/false in the new model, so I try to hint them anyway.

(after that I create a new solver for the new model model_free with 

12 workers, 

solver.parameters.hint_conflict_limit = 3500

solver.parameters.repair_hint = True

solver.parameters.max_presolve_iterations = 12

solver.cp_model_probing_level = 4

and start the optimization)

Despite the solution hinting (with a valid, good found solution from the old model that did the small run), the new model with the new solver takes hours to find a first solution.

(In the last run it took 25 hours!)

What is the problem?

[Because I have multiple objectives I want to minimize, I am doing one after another, see Multi-objective optimization. After one objective is done, I hint the model for the new objective with the solution from the model before a similar way like the one above and it works perfectly fine....

  model_free.Proto().solution_hint.Clear()

  for i in range(len(model_free.Proto().variables)):

    model_free.Proto().solution_hint.vars.append(i)

    model_free.Proto().solution_hint.values.append(solver.ResponseProto().solution[i])  

]

[Priidik Vilumaa]

I have never managed to use hints successfully so that they would actually speed up the solution finding process. What I would try in your case is to run the "big model" in chunks using LNS. I.e. take the small model final solution, then randomly "unfix" ~20% of jobs (allow these to be scheduled on any machine) and optimize. Rinse and repeat.

However, the challenge is how it fits into the multi objective framework :) I'm not sure if you'd like to optimize every objective separately at every step of LNS.

Best,

Priidik