Decision Optimization

 View Only
Expand all | Collapse all

Custom branching strategy with docplex

  • 1.  Custom branching strategy with docplex

    Posted Tue July 05, 2022 09:09 AM
    Is there any way to use a completely custom (external) branching strategy for the CP optimizer through docplex's Python API? I was hoping there is some way callback or goal interface in the API, but I cannot find it in the documentation. Is this at all possible?

    ------------------------------
    Marijn K
    ------------------------------

    #DecisionOptimization


  • 2.  RE: Custom branching strategy with docplex

    Posted Wed July 06, 2022 08:25 AM
    The Python API does not provide a full access to the branching strategy yet. Only C++ API does.
    However the Search Phases customize the selection and the evaluation of the variables. They may help.

    ------------------------------
    Cedric Doens
    ------------------------------



  • 3.  RE: Custom branching strategy with docplex

    Posted Thu July 07, 2022 06:35 AM
    Thank you for you response, Cédric. Is there a way then, to update/change the search phases between decision points? I would like to steer the decision-making progress based on the current state of the solving process.

    ------------------------------
    Marijn K
    ------------------------------



  • 4.  RE: Custom branching strategy with docplex

    Posted Thu July 07, 2022 09:37 AM
    Edited by System Fri January 20, 2023 04:26 PM

    Once the solver research is launched, its strategy cannot change.
    However, a common practice is to start a new search, with its own phases, using a previously reached solution as a Starting Point.
    This might suit your situation

    ------------------------------
    Cédric Doens
    ------------------------------



  • 5.  RE: Custom branching strategy with docplex

    Posted Thu July 07, 2022 11:37 AM
    Thank you again for your help. This does indeed look more like what I'm after. I see though that it is limited to only adjusting the search phases whenever a solution is reached. Is there any possibility for more fine-grained control? The propagate() function looks promising for taking single steps. But I can't find how I would use the resulting CpoSolveResult as a new starting point. Would it work to use that to build a new partial CpoModelSolution (with create_empty_solution()) and then use that as a new starting point?

    ------------------------------
    Marijn K
    ------------------------------



  • 6.  RE: Custom branching strategy with docplex

    Posted Fri July 08, 2022 06:53 AM

    If a CpoSolveResult contains a solution (is_solution()), you can get its CpoModelSolution representation directly (get_solution()).
    Note that the methods implemented in the class CpoModelSolution to access solution elements are available directly CpoSolveResult,
    so you can use them as condition to end the current search (end_search())


    The general idea is:
    - start a first search, examine each new solution until it meet your criteria; then store a first solution and end the search
    - start a second search using the first solution as a starting point.
    Each search might use its proper search phases.

    A starting point accepts partial CpoModelSolution . Indeed  you can create_empty_solution() then populate it with external values such as values extracted from previous solutions. (e.g. plant_location_with_starting_point)



    ------------------------------
    Cédric Doens
    ------------------------------



  • 7.  RE: Custom branching strategy with docplex

    Posted Thu August 04, 2022 07:13 AM
    I understand that it is common to work from solution to solution, but I really need to be able to influence each branching decision. I understand that this can be done with search phases. However, the currently available functions for choosing variables are not flexible enough for my purposes. Is there a way to customize/add varchooser/valchooser functions for the search_phase function?

    ------------------------------
    Marijn K
    ------------------------------



  • 8.  RE: Custom branching strategy with docplex

    Posted Thu August 04, 2022 10:22 AM
    Edited by System Fri January 20, 2023 04:18 PM
    Dear Marijn,

    It is not yet possible. Custom var and value choosers are only available in C++ and Java.
    Cheers,


    ------------------------------
    Renaud Dumeur
    ------------------------------



  • 9.  RE: Custom branching strategy with docplex

    Posted Fri August 12, 2022 08:58 AM
    Thanks for the clarification Renaud. Can you please point me to the relevant documentation page for the C++ API? I'm having some trouble locating it.

    ------------------------------
    Marijn K
    ------------------------------



  • 10.  RE: Custom branching strategy with docplex

    Posted Fri August 12, 2022 09:29 AM

    On this page you can find the documentation about search phases and variable/value selectors:

    https://www.ibm.com/docs/en/icos/22.1.0?topic=search-ordering-variables-values

    You have several level of selection:
    1. Order  groups of variables
    2. Use already-defined variable and value selectors on a group
    3. Write your own selector for variables and values. 

    Regards

    Philippe



    ------------------------------
    Philippe Refalo
    IBM ILOG CP Optimizer
    ------------------------------



  • 11.  RE: Custom branching strategy with docplex

    Posted Tue August 16, 2022 02:18 PM
    Thanks for the pointer, Philippe. I would like to control the order in which interval variables are fixed, based on a custom function. Therefore, I was expecting a function with signature IloSearchPhase(env, intervalVarArray, varChooser, valueChooser), or something similar. However, such an interface is missing. I don't see how I can accomplish this with the ones that are available. I'm assuming at this point that I'll have to resort to manipulating IlcGoal in order to achieve this. Is that correct?

    ------------------------------
    Marijn K
    ------------------------------