optimization of cp-sat problem - limits on objective variable make the solver slower

[Jan Gregor]

Hello,

  I don't know how to help cp-sat solver to get solutions faster for my problem.

  My worker assignment problem contains following variables.

     Y[t][w] = 1 means that the worker w is used for a task

                = 0 the worker w is not used by a task

     W[w] = 1 a worker is used by some task

              = 0 a worker is not used by any task

  Constraints can be divided into three groups.

1. sum of workers used by a task is equal to number of workers needed by a task

  example Y[t][w1] + Y[t][w2] = 1

  task needs one worker, a solver can choose between worker w1 or w2

2. two tasks are overlapping, a worker can be used used only by one task

  example 0 <= Y[t1][w] + Y[t2][w] <= 1

3. Y[t][w] -> W[w] for any possible value of t and w

Optimization function is minimization of  sum(W[w]) so minimal number of workers is used.

I know in most cases lower limit for number of workers.

Originally I tried to model it as MIP problem but CBC solver was very slow and many times no solution was found.

I tried to measure total time of 100x executions to minimize effect of stochastic search. 5 instances of search workers was used.

1. 685 seconds for original solution, lower bound of objective variable is 0

2. 1020 seconds when lower bound of objective variable is limited by constraint. I received similar result when lower bound was defined during creation of the variable.

3. 487 seconds when execution is stopped in solution callback by stopSearch method when lower limit was reached.

My opinion is that variant 2 should be as fast if not faster than variant 3.

Can you give me some insight why are results for variants 2 and 3 so different ?

Attached are proto files for variants 1 and 2.

Thanks,

Jan

[Laurent Perron]

Can you send me the source code ? (can be a PM).

I cannot conclude looking at protos :-)

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/4715117f-00e4-4786-97bc-4c17d688e8bb%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.