Topic
  • 3 replies
  • Latest Post - ‏2014-04-09T15:44:23Z by Philippe_Refalo
JorisK
JorisK
26 Posts

Pinned topic Adding solution to internal solution pool

‏2014-03-19T20:15:09Z |

Dear,

I've a custom constraint and corresponding propagator implementation in C++. The propagator maintains its own problem-specific data structures. After each propagation loop I can perform a heuristic search on these data structures.  The heuristic often finds feasible solutions to the original problem. If one of the heuristic solutions is better than the best incumbent solution, I would like to insert this solution into the solution pool. Could anyone tell me how I could do this?

I currently use a work-around to insert a heuristic solution. I've created a custom branching scheme using IloGoals. If I find a new best solution, I create the following 3 branches:

Branch 1. Fix all variables to the values in the heuristic solution

Branch 2. Choose the first unfixed variable x and fix it to the first available value y in its domain

Branch 3. State that variable x cannot be fixed to value y.

If my heuristic solution isn't better than the best incumbent solution, I only create branches 2 and 3. Although this approach works, I would rather use CP's default branching scheme as this scheme performs a lot better than my own branching scheme. Perhaps the variable/value to branch on is selected in a smarter way? Either way, if I could insert the solution from my primal heuristic directly into the solution pool, I don't need my own custom branching scheme anymore.

 

  • Philippe_Refalo
    Philippe_Refalo
    50 Posts

    Re: Adding solution to internal solution pool

    ‏2014-03-27T18:34:26Z  

    Hi JorisK,

    There is no way to indicate to CP Optimizer that a solution has been found at a node by a (primal) heuristic. The best way to go is to check that you have an improving solution and to stop the search in this case.Then, restart the search by specifiying that this solution is a starting point of the search. CP Optimizer will then start searching and trying to improve it. 

    Regards

    Philippe

  • JorisK
    JorisK
    26 Posts

    Re: Adding solution to internal solution pool

    ‏2014-04-09T03:57:32Z  

    Hi JorisK,

    There is no way to indicate to CP Optimizer that a solution has been found at a node by a (primal) heuristic. The best way to go is to check that you have an improving solution and to stop the search in this case.Then, restart the search by specifiying that this solution is a starting point of the search. CP Optimizer will then start searching and trying to improve it. 

    Regards

    Philippe

    Ok, thank you. That answers my question, but the solution is unfortunately very inconvenient. Simply restarting the search would require to re-initialize a substantial amount of large data structures which is too expensive. It would be nice if a feature could be added to CP optimizer that allows you to add new solutions originating from primal heuristics. After all, this is very natural in for example an integer programming context.

  • Philippe_Refalo
    Philippe_Refalo
    50 Posts

    Re: Adding solution to internal solution pool

    ‏2014-04-09T15:44:23Z  
    • JorisK
    • ‏2014-04-09T03:57:32Z

    Ok, thank you. That answers my question, but the solution is unfortunately very inconvenient. Simply restarting the search would require to re-initialize a substantial amount of large data structures which is too expensive. It would be nice if a feature could be added to CP optimizer that allows you to add new solutions originating from primal heuristics. After all, this is very natural in for example an integer programming context.

    Where is the initialization of this large data done ? If it is at constraint post, it could be moved outside the search so that you can restart without much cost. If you fear that the update made at each propagation to reach a node of the search is costly, keep in mind that the CP Optimizer search restarts often. Restarting one more time because a better solution has been found will not have an impact considering that this should not happen that often. 

    I dont think that a heuristic callback can have the same effect in CP (where search is restarted often) than in IP (where breadth-first search is the norm) also because the work done at each node can be significantly lighter in CP compared to IP but I agree it would be more convenient than restarting by hand.

    Philippe