Decision Optimization

Decision Optimization

Delivers prescriptive analytics capabilities and decision intelligence to improve decision-making.

 View Only

  • 1.  CPOptimizer specifying value ordering for sequence variables in search phase

    Posted Wed May 13, 2020 10:31 AM
    Hello CPO Team,

    I have a question about search phase in CPOptimizer (I'm using the java API with version 12.9.0)

    I read in the users manual that we can specify search phase before starting the search. I also read that I can give a value selector to the search phase : for exemple if I have some knowledge on promising value for a given variable I can define my own value selector (extending the abstract class IloCustomIntValueEval) to guide the search. We can also specify search phase for scheduling variables (especially sequence variables).

    But I can't find a way to give a value selector to a search phase which deals with sequence variables. Is it possible to do something like it ?

    Let's say I have some knowledge on the sequences which lead to good solutions, how can I use that knowledge to help the solver ? Can I say to the solver 'it is probably good to schedule interval i just after interval j' or 'it is probably  good to schedule interval i in the n-th position' ?

    Thanks for your answer and for your wonderful solver

    ------------------------------
    Lucas Groleaz
    ------------------------------

    #DecisionOptimization


  • 2.  RE: CPOptimizer specifying value ordering for sequence variables in search phase

    Posted Wed May 13, 2020 01:29 PM
    Hi,

    let me quote documentation

    <main role="main">

    Sequence variable search phase

    </main>    <main role="main">

    A search phase on sequence variables works on a unique sequence variable or on an array of sequence variables. During this phase CP Optimizer fixes the value of the specified sequence variable(s): Each sequence variable will be assigned a totally ordered sequence of present interval variables. Note that this search phase also fixes the presence statuses of the intervals involved in the sequence variables. This phase does not fix the start and end values of interval variables.

    </main>

    It is recommended to use this search phase only if the possible range for start and end values of all interval variables is limited (for example by some known horizon that limits their maximal values).



    If you have some hint about the right sequence why don't you build a solution and warm start from that solution ?

    regards


    ​

    ------------------------------
    ALEX FLEISCHER
    ------------------------------

    Original Message


  • 3.  RE: CPOptimizer specifying value ordering for sequence variables in search phase

    Posted Thu May 14, 2020 03:31 AM
    Hi Alex,

    Thanks for your answer. I already try to warm start from a solution I build and it gives good results. However I would like to try the method described in the following paper :

    Khichane, Madjid, Patrick Albert, et Christine Solnon. « Strong Combination of Ant Colony Optimization with Constraint Programming Optimization ». In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, édité par Andrea Lodi, Michela Milano, et Paolo Toth, 6140:232‑45. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. https://doi.org/10.1007/978-3-642-13520-0_26.

    The idea is to combine Ant Colony Optimization (ACO) and CPO. In the article it is applied on optimization problem where decision variables takes integer values, and hence authors use the class IloCustomIntValueEval (or something equivalent in another programming language). I would like to apply it to scheduling problems, where some decision variables are sequence variables.

    Hence the idea is to execute an ACO algorithm during a given duration. Then the ACO algorithm gives me a 'pheromone matrix'. This pheromone matrix gives a score for scheduling interval i just after interval j for each pair of interval (i,j), which will help the CPO solver. For example with 4 interval, I have results like scheduling i4 just after i1 has a score of 0.1, scheduling i3 just after i1 has a score of 0.5 and scheduling i2 just after i1 has a score of 0.2.
    Now, what I would like to do is : during the search phase if i1 is scheduled, and we must choose in the sequence variable the next interval to schedule, first we choose i3 (because it has the highest score). Then we propagate and we build an entire sequence, and if it fails during the search, after the backtracking, we then choose to schedule i2 just after i1 (because it has the second highest score), and so on...

    Regards


    ------------------------------
    Lucas Groleaz
    ------------------------------

    Original Message


  • 4.  RE: CPOptimizer specifying value ordering for sequence variables in search phase
    Best Answer

    Posted Fri May 15, 2020 04:05 AM
    Hello Lucas,

    I'm sorry but CP Optimizer does not provide an API to do what you want. Warm start seems to be the closest. Note that warm start doesn't have to be a valid solution, even if it is invalid, CP Optimizer still uses it as a guide to find the first solution. Once the first solution is found though it switches to LNS and forgets about the warm start. LNS is described in the following paper:

    Laborie, Godard: Self-adapting large neighborhood search: Application to single-mode scheduling problems, 2007

    Even if the API existed, it is a question how to integrate LNS with your approach. In LNS, part of the current solution is relaxed and the search tries to extend the non-relaxed part of the old solution in order to find a better solution. So it is also important what part of the current solution is relaxed.

    Another possibility is to write your own search goal in C++. That's much more laborious though.

    Best regards, Petr

    ------------------------------
    Petr Vilím
    IBM
    ------------------------------

    Original Message


  • 5.  RE: CPOptimizer specifying value ordering for sequence variables in search phase

    Posted Mon May 18, 2020 03:35 AM
    Hello Petr,

    Thank you for your answer ! Indeed it is hard to integrate it with the LNS, I hadn't thought about that. By the way, is there a way to interact with the LNS ? For example if I want to say 'If this part is relaxed, this other part should be relaxed too (because of some particularity of my problem )' ? Or is it possible to turn it off in order to evaluate performance with and without it ?

    Thanks

    Best regards,

    ------------------------------
    Lucas Groleaz
    ------------------------------

    Original Message


  • 6.  RE: CPOptimizer specifying value ordering for sequence variables in search phase

    Posted Mon May 18, 2020 07:35 AM
    Hello Lucas,

    unfortunately, again there is no public API to interact with the internal LNS. And yes, it is possible to turn LNS off using parameter SearchType, I didn't think about it in my previous post. When SearchType is Restart then, in case of scheduling problems, CP Optimizer runs LNS (for simpler problem it also it may also trigger Failure-Directed Search, depending on parameter FailureDirectedSearchEmphasis). SearchType could be also DepthFirst what turns on simple depth-first search. The last search type is MultiPoint that tries to combine solutions (or partial solutions) using genetic algorithms.

    Usually, Restart is the best method. Sometimes Multipoint could work well. And DepthFirst is almost always worse. From my experience, the only case when DepthFirst could be better is when it takes a lot of backtracks to find initial solution, in that case initial fast restarts are useless and only slow down the search.

    Best regards, Petr

    ------------------------------
    Petr Vilím
    IBM
    ------------------------------

    Original Message


  • 7.  RE: CPOptimizer specifying value ordering for sequence variables in search phase

    Posted Tue May 19, 2020 08:59 AM
    Hello Petr,

    Thank you so much for all your answers !

    Best regards,

    ------------------------------
    Lucas Groleaz
    ------------------------------

    Original Message


Related Content