Decision Optimization

Decision Optimization

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

 View Only

  • 1.  Docplex CP "No solution" vs "Infeasible"

    Posted Wed April 09, 2025 01:54 AM

    Clarification please

    When running Docplex CP (in python) projects, there are several outcomes.

    1. Solution found.

    Great !!

    2. Solver runs until timeout. Verbose mode generates details of the search. Result "No solution found"

     

    3. Solver stops almost immediately & "Infeasible" reported

    Is it safe to assume:

    #2 => model is under-constrained & some variables are not instantiated
    #3 => model is over-constrained, so no solution exists

     

    If my assumptions are correct, in case #2 (under-constrained) is it possible to find the variables that are not instantiated?

     

    I am having an issue where CP does not find a solution no matter solve time limit.

     

    Thanks & regards

     

    Ross Dye

    0400669880

     



  • 2.  RE: Docplex CP "No solution" vs "Infeasible"

    Posted Thu April 10, 2025 10:58 AM
    Edited by PhR Thu April 10, 2025 10:59 AM

    When solving a decision model (that has no objective function), the CP engine traverses (implicitly) all the possible combinations of values (the search space) to find a solution or to prove that there is none. It is only when the search is terminated without finding any solution that one can say the model does not have a solution. So in case 2 we don't know yet if the model admits a solution or not since search hasn't explored all the search space. In that case the engine does not report what could be the longest assignment found because this is dependent on the strategies the engine use and thus has no meaning w.r.t. the solutions set nor it gives information about the hardest variables of the model.
    For improving the time to find a solution, you can start by reformulating the problem to have a stronger formulation, add additional constraints to reduce the search space or change parameters (https://www.ibm.com/docs/en/icos/22.1.2?topic=optimizer-parameters-cp). 


    Original Message


  • 3.  RE: Docplex CP "No solution" vs "Infeasible"

    Posted Thu April 10, 2025 10:45 PM

    Thank you

    That is an excellent introduction to Docplex 1.01. But that is not answering my questions.

    I have developed quite a complex model for production scheduling. One result from this model is shown graphically below

     

    This model has:

    12:08:01:678    - modeling time: 15.37 sec

    12:08:02:419    - number of integer variables:  7253

    12:08:02:419    - number of interval variables: 38606

    12:08:02:419    - number of sequence variables: 7

    12:08:02:419    - number of constraints:        75266

     

    Solve time for this quality solution is around 90 sec

     

    Clearly stage 2 (Fillers and Packers) have sequence variables and transition matrices applied, and are sequenced nicely, grouping similar items (colours)

    Note also that the objective function (minimize makespan) is working well.

     

    But, the problem arises when I add sequence variables to stage 1, ie the mixers. Then, no solution can be found, regardless of solve time allowed.

     

    I have simplified the model to isolate the issue, as described in previous post. I will restate it here:

    With just one mixer and 2 fillers, 1 order, minimize makespan I get this result



    GREAT

     

    But if I add an alternative Filler (or Packer) I get this result:

    And:
    12:32:27:353    ! ----------------------------------------------------------------------------

    12:32:27:353    ! Search terminated by limit, no solution found.

    12:32:27:353    ! Best bound             : 60

    12:32:27:353    ! makespan               : NaN

    12:32:27:353    ! total_transitions      : NaN

    12:32:27:353    ! F2_makespan            : NaN

    12:32:27:353    ! F3_makespan            : NaN

    12:32:27:353    ! Mx1_makespan           : NaN

    12:32:27:353    ! Pk2_makespan           : NaN

    12:32:27:353    ! Pk3_makespan           : NaN

    12:32:27:353    ! Ps1_makespan           : NaN

    12:32:27:353    ! resource_makespan      : NaN

    12:32:27:353    ! ----------------------------------------------------------------------------

    12:32:27:353    ! Number of branches     : 5554297

    12:32:27:353    ! Number of fails        : 2776837

    12:32:27:353    ! Total memory usage     : 118.3 MB (118.3 MB CP Optimizer + 0.0 MB Concert)

    12:32:27:353    ! Time spent in solve    : 10.06s (10.06s engine + 0.01s extraction)

    12:32:27:353    ! Search speed (br. / s) : 552501.4

    12:32:27:353    ! ----------------------------------------------------------------------------

    12:32:27:353    12:32:27 . . . . No solution, result = Unknown

     

    NOTE also model dimensions – it is not big:

    12:32:17:044    - number of integer variables:  4

    12:32:17:044    - number of interval variables: 14

    12:32:17:044    - number of sequence variables: 4

    12:32:17:044    - number of state functions:    0

    12:32:17:044    - number of float variables:    0

    12:32:17:044    - number of constraints:        40

    12:32:17:044    - number of root expressions:   40

     

    So, clearly no solution can be found when I add a sequence_var to the upstream resource and there are alternative resources downstream

     

    My conclusions are:

    1. There is an issue with Docplex – which I strongly doubt, OR
    2. There is an issue with my model

    Assuming B, then

    • I should have additional constraints, or
    • I need to identify which variables are not being instantiated and resolve

     

    SO, how can I identify variables that are not instantiated.

     

    SO, I would appreciate some feedback based on AE (Actual Experience), not AI

     

    Thanks

     

    Ross




    Original Message


Related Content