Decision Optimization

 View Only

  • 1.  CP to MP - Constraint Help

    Posted Tue December 19, 2023 04:32 AM
    Edited by Aarushi Gupta Tue December 19, 2023 04:37 AM

    I had initially solved my problem using CP. Now I am trying to redo it using MP.
    I am facing issue with one of my constraints.

    CP code:

    bin_task_var = [[mdl.interval_var(optional=True, size=all_task_mh[task], name="b{}-t{}".format(bin, task))
                     for task in range(nb_tasks)] for bin in range(max_nb_bins)]

for bin in range(max_nb_bins):
        min_intvl = mdl.min([((mdl.presence_of(bin_task_var[bin][task]) * all_task_interval[task]) +
                              ((1 - mdl.presence_of(bin_task_var[bin][task])) * 1000000000000))
                             for task in range(nb_tasks)])
        for task in range(nb_tasks):
            mdl.add(
                mdl.if_then(
                    mdl.presence_of(bin_task_var[bin][task]) == 1,
                    (min_intvl / all_task_interval[task]) >= required_yield
                )
            )

    MP code:

    bin_task_var = [[mdl.binary_var(name="b{}-t{}".format(bin, task))
                     for task in range(nb_tasks)] for bin in range(max_nb_bins)]   

for bin in range(max_nb_bins):
        min_intvl = mdl.min([((bin_task_var[bin][task] * all_task_interval[task]) +
                              ((1 - bin_task_var[bin][task]) * 1000000000000))
                             for task in range(nb_tasks)])
        for task in range(nb_tasks):
            mdl.add(
                mdl.if_then(
                    (bin_task_var[bin][task] == 1),
                    (min_intvl / all_task_interval[task] >= required_yield)
                )
            )

    The MP code gives No Solution for scenarios where CP was working.

    Is there something wrong in the way I have coded this constraint? 

    Any inputs are welcome! TIA

    #DecisionOptimization#AIandDSSkills#docplex#MathematicalProgramming-General



    ------------------------------
    Aarushi Gupta
    ------------------------------



  • 2.  RE: CP to MP - Constraint Help

    Posted Wed January 10, 2024 10:11 AM
    Edited by Philippe Refalo Wed January 10, 2024 10:12 AM
    The problem comes probably from the big integer you use for expressing a logical relation while it is hard to see how it would made the model infeasible with the model extract given, probably because of a combination of these and other constraints. 
     
    The expression used as argument for min is 
     
    b * A + (1-b) * M that is M + (A-M) * b 
     
    where
    • b is bin_task_var[bin][task]
    • A is all_task_interval[task]
    • M = 1000000000000
    It means that the expression is M when b = 0 and A when b = 1.
    The problem when using such a big value for M is because when CPLEX considers that b equals 1, it can be very close to 1 but not necessarily equals to 1. 
    Assume A = 1000 and b value to be very close to 1 (say 0.99999) one end up with a value of about 10000000. for the expression above. It is far from the expected value A=1000. The bigger M is the larger will be that gap.
     
    A solution is to choose for M the smallest possible value that preserves the logic of the expression. Here it can be set to the biggest value the expression A (all_task_interval[task]) can take. It should be smaller than the current value used.
     
    Note that problems with this formulation are less likely to appear in CP Optimizer because it instantiates b to the integer 1 and uses interval computations to evaluate expressions.


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

    Original Message