Decision Optimization

Originally posted by: yuanyuanjia

Hi,

I have a scheduling model to schedule WOs within certain work period considering many constraints. When I run the model with some datasets, I got "no solution found" in my configured time limit.

Is there any way/tool to debug to find which constraints cause this issue? I've tried with "oplrun -conflict", but got following results in the end which didn't indicate me so much. Thank you in advance!

! Time = 531.07s, Average fail depth = 623, Memory usage = 584.0 MB
 ! Current bound is 0; 1228; 0; 0; 622; -3050; 0; 1551700800; -610; 0
 !          Best Branches  Non-fixed    W       Branch decision
 ! ----------------------------------------------------------------------------
 ! Search terminated by limit, no solution found.
 ! Best bound             : 0; 1228; 0; 0; 622; -3050; 0; 1551700800; -610; 0
 ! ----------------------------------------------------------------------------
 ! Number of branches     : 6669429
 ! Number of fails        : 3124226
 ! Total memory usage     : 685.6 MB (584.0 MB CP Optimizer + 101.6 MB Concert)
 ! Time spent in solve    : 532.11s (530.73s engine + 1.38s extraction)
 ! Search speed (br. / s) : 12566.5
 ! ----------------------------------------------------------------------------
 ! ----------------------------------------------------------------------------
 ! Maximization problem - 6219 variables, 7547 constraints, 2 phases
 ! Presolve      : 4 extractables eliminated
 ! FailLimit            = 3120000
 ! SolutionLimit        = 4
 ! TimeLimit            = 682
 ! Initial process time : 0.00s (0.00s extraction + 0.00s propagation)
 !  . Log search space  : 39218.2 (before), 39218.2 (after)
 !  . Memory usage      : 25.8 MB (before), 25.8 MB (after)
 ! Using sequential search.
 ! ----------------------------------------------------------------------------
 !          Best Branches  Non-fixed            Branch decision
 ! ----------------------------------------------------------------------------
 ! Maximization problem - 6219 variables, 7547 constraints, 2 phases
 ! Presolve      : 4 extractables eliminated
 ! FailLimit            = 3120000
 ! SolutionLimit        = 4
 ! TimeLimit            = 682
 ! Initial process time : 0.00s (0.00s extraction + 0.00s propagation)
 !  . Log search space  : 39218.2 (before), 39218.2 (after)
 !  . Memory usage      : 25.8 MB (before), 25.8 MB (after)
 ! Using sequential search.
 ! ----------------------------------------------------------------------------
 !          Best Branches  Non-fixed            Branch decision
 ! ----------------------------------------------------------------------------
 ! Conflict refining - 7547 constraints, 2 phases
 ! FailLimit            = 3.12e+06
 ! TimeLimit            = 682
 ! ----------------------------------------------------------------------------
 !   Iteration      Number of constraints
 *           1                       7509
 *           2                       7509

*           3                       7509
 ! Conflict refining terminated
 ! ----------------------------------------------------------------------------
 ! Conflict status           : Terminated normally, no conflict
 ! Number of iterations      : 3
 ! Total memory usage        : 58.3 MB
 ! Conflict computation time : 682.25s
 ! ----------------------------------------------------------------------------
  No conflicts available.
 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Petr Vilím

Hello,

it looks like there is a trouble to find initial solution. Without knowing more details I can give you only some generic thoughts. If you can export your model into a cpo file and share it with us then maybe I can give you better answer.

In general, in case of scheduling problem CP Optimizer builds the initial solution mostly chronologically. For most scheduling problems it is not that hard to find an initial solution (although of a bad quality) because by working chronologically, some tasks are simply delayed until enough resources (machines) is available to perform them. However sometimes this approach doesn't work because of some constraints in the model that forbid such schedules. For example:

• Maximum end time of interval variables is constrained and the deadline is too hard to satisfy easily.
• There are maximum delays between tasks. Once a task A starts a task B must be done within some time limit after A. This way, if CP Optimizer starts too many tasks like A then there may be not enough resources to do all the Bs within the maximum delay limit.
• There are some non-scheduling constraints to satisfy (something else then cumulative, noOverlap, state, precedences, alternative etc.). Such constraints can easily break the chronological construction of initial solution.
• There are search phases. Search phase works chronologically but fixes only specified interval variables. It could be that it doesn't leave enough room for the remaining interval variables.

So try to think why chronological creation of initial solution doesn't work in your case. You may also set LogPeriod=1 and see the decisions made by the solver and the point of the first failures. It may show that some important propagation is missing, maybe you can add some redundant constraints to provide this propagation. Maybe you can also relax some hard constraints and move them into objective functions.

Note that initial solution doesn't have to be very good. The search will work on it and improve it.

If you know how to find an initial solution, you may also compute it yourself and provide it to the CP Optimizer as "starting point". Starting point could be also used in a two-phase solve: first solve slightly different problem just to find the initial solution and then use the solution as starting point of the second solve.

I hope it helps, Petr

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: yuanyuanjia

Thank you Petr, I'll check my code according to your general guidelines. Here is a cpo file exported from my model, could you please take a look? Thanks!

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Petr Vilím

Hello,

I tried your model using CP Optimizer versions 12.10, 12.9 and 12.8. What I wrote in the previous post is mostly for the default search type Restarts, from the file I see that you're using MultiPoint. So I tried both. I also set Workers=4 and TimeLimit 60s. Here are results:

 

Version 12.10 + Multipoint, first solution after 17.37s, final solution: 332431.5; 0; -35397885; 0; 0; 0; 0; 0; 0 (gap is 99.15% @ crit. 1 of 9)

Version 12.10 + Restart: first solution after 5.57s, final solution 662032.8; 0; -109595657; 0; 0; 0; 0; 0; 0 (gap is 100.0% @ crit. 3 of 9)

Version 12.9 + Multipoint: no solution found

Version 12.9 + Restart: first solution after 8.74s, final solution  662032.8; 0; -110547086; 0; 0; 0; 0; 0; 0 (gap is 100.0% @ crit. 3 of 9)

Version 12.8 + MultiPoint: no solution found

Version 12.8 + Restart: first solution after 33.5s, final solution 342980.; 0; -34138004; 0; 0; 0; 0; 0; 0 (gap is 93.02% @ crit. 1 of 9)

 

From those results, I guess that you're using version 12.9 or older. So my recommendation is to upgrade and do not change SearchType to MultiPoint (because Restart is the default).

 

I also noticed repeating pattern of constraints like the following one:

(0 == sizeOf("V_taskSlice#0")) => (0 == presenceOf("V_taskSlice#0"));

The constraint above is: if V_taskSlice#0 has size 0 then it should be absent. As a result, V_taskSlice#0 never has size 0 because in this case it simply doesn't exit (it is absent). In other words, this constraint can be replaced by:

sizeOf("V_taskSlice#0", 1) > 0;

Because if V_taskSlice#0 is absent then sizeOf returns the second parameter 1 and the constraint is true. And if V_taskSlice#0 is present then sizeOf returns it size and it must be bigger than 0.

Currently we don't have a presolve for this transformation, so if you do it manually then your model will propagate better and you may get better performance.

 

But there is one more repeating pattern, improving this one can help quite a lot:

span("V_task#0", ["V_taskSlice#0"]);
(presenceOf("V_task#0") >= 1) => (sum([sizeOf("V_taskSlice#0")]) == 4259);

The first constraint "span" says: There's only one slice for V_task#0. As the result the two interval variables are actually identical. They could be either both present or both absent. And if they are both present then they are synchronize.

The second constraint says that if V_task#0 is present then size of V_taskSlice#0 is 4259. However, considering that V_task#0 and V_taskSlice#0 are basically the same interval variables, it could be rewritten to:

sizeOf("V_taskSlice#0", 4259) == 4259;

Or:

sizeOf("V_task#0", 4259) == 4259;

Maybe in the future you will have more slices per task? Then you may keep the original constraints and add redundant constraint that will improve the propagation:

sizeOf("V_task#0", 4259) >= 4259;

BTW, if you plan to have more slices for a task then it is good to break symmetries in the solution by ordering them in time and by forcing only the first slices to be present:

endBeforeStart("task1slice1", "task1slice2");
presenceOf("task1slice1") >= presenceOf("task1slice2");

Best regards, Petr

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: yuanyuanjia

Hi Petr,

Thank you for the detailed information. Yes, I'm using 12.9 now. And it's not possible to upgrade our production environment into latest release. So I've changed to the default search type in 12.9. I've made some modification according to your suggestions, it works well for tasks with 1 slice.

We did allow task to be split into multiple task slices to be scheduled. The one I tested in previous .cpo don't have such tasks, but when I test with dataset that some tasks can have multiple task slices(they have extra constraints), I still get no solution found in search phase, could you please help to check? Thanks!

Sorry that I can't upload my .cpo in this community, it logged out when I post with my .cpo file, I'll send you an email for it. Thanks!

#DecisionOptimization
#OPLusingCPOptimizer