Decision Optimization

Decision Optimization

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


#Analytics
#DecisionOptimization
#DecisionOptimization
 View Only

  • 1.  State Function Symmetry

    Posted 10/08/21 05:26 PM
    Hi,

    I was wondering how should I deal with symmetry in a state function for CP Optimizer.

    Specifically, say for a single-valued state function, with all else being equal, how does the solver search through the two solutions S1 and S2,
    where state function of S1 = ((start=0, end=10, state=0), (start=10, end=15, state=0)) and
    state function of S2 = ((start=0, end=5, state=0), (start=5, end=15, state=0))?

    In other words, if I know swapping the two discrete states within a solution always yields the same objective (i.e z(S1) = z(S2)), should I impose additional symmetry reducing constraints?

    Thanks,
    Louis

    ------------------------------
    Louis Luo
    ------------------------------

    #DecisionOptimization


  • 2.  RE: State Function Symmetry

    Posted 10/12/21 11:14 AM
    Dear Louis, 

    In general, adding symmetry-breaking constraints to a scheduling model in CP Optimizer hurts performance to converge towards good solutions. In your case, state functions are instantiated after interval variables and having ties at this lever should not deteriorate performance.

    Regards

    Philippe

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



  • 3.  RE: State Function Symmetry

    Posted 10/13/21 01:37 PM
    Hi Philippe,

    Thanks for your response. I just want to confirm that not imposing symmetry-reducing constraints will generally improve solution quality, but not aid in the proof of optimality.

    Align the same line of thought, for two intervals variables (i.e. x1, x2) that each takes on a state in the state function, would symmetry-reducing constraints (such as end_before_start(x1, x2)) improve solution quality/aid proof of optimality?

    Best,
    Louis

    ------------------------------
    Louis Luo
    ------------------------------

    Original Message


Related Content