Topic
  • 1 reply
  • Latest Post - ‏2014-03-25T09:02:28Z by Philippe_Refalo
JorisK
JorisK
37 Posts

Pinned topic Warmstart CP optimizer while using DFS

‏2014-03-19T20:32:05Z |

Dear,

I'm using a CP model with custom constraints, together with depth-first search (cp.setParameter(IloCP::SearchType, IloCP::DepthFirst);).

I also have a heuristic which calculates an initial feasible solution which I would like to use to warm start the search. However, the manual states the following:

Note: the starting point information is used by the restart and multi-point search types only. It is not used by the depth-first search.

This is problematic. My initial solution is completely ignored. Its objective value isn't used at all. Even though CP might not start from this solution, I would at least expect that it stores the solution in its solution pool and that it correctly reports that it knows a solution with objective value Y.

Example> Imagine that I'm solving a routing problem where the objective is to minimize the travel distance and that I heuristically found a feasible solution with objective 10. As a consequence, we can remove all edges with travel cost >= 10 because they can never be used in an optimal solution. This holds independently of the search method used. 

Something I could do is add a constraint like: "objective <= objective_heuristic_solution -1" to ensure that the CP model searches for solutions which are strictly better than the heuristic solution. This however is a rather ugly work around.

  • Philippe_Refalo
    Philippe_Refalo
    50 Posts

    Re: Warmstart CP optimizer while using DFS

    ‏2014-03-25T09:02:28Z  

    Hi JorisK,

    In your case, warmstarting DFS would not do anything else than what you mention as a workaround : set a constraint on the objective function that forces to find a better solution. There is little room for an "advanced" usage of the starting point in DFS such as what we do in Restart or MultiPoint where we can use the starting point as a guide for example. 

    The workaround you propose is the right way to go. You could perhaps do better by observing the result of propagating the constraint on the cost and enforcing manualy the inferences that should be made and that propagation does not perform because the model is not strong enough.

    Regards

    Philippe