Topic
  • 4 replies
  • Latest Post - ‏2013-06-19T15:37:08Z by HWFN_Hossein_Hojabri
HWFN_Hossein_Hojabri
25 Posts

Pinned topic growing number of constraints

‏2013-06-13T15:04:05Z |

Hi,

 

One thing that I noticed in my algorithm is that whenever I call cp.solve(), the number of constraint grows. For example if have 1000 constraint the second time I call cp.solve(), the number of constraints is 2000, the third time 3000, and so on.

 

It does not matter where I call cp.solve()! Even if I call them back to back in the same iteration of the algorithm like in the following this happens:

cp.solve();

cp.solve();

cp.solve();

I think this shouldn't happen! And I don't know what to do about it to make it stop duplication the the same constraints at every iteration.

 

The other thing is that in every iteration of my algorithm (where I call cp once to solve a sub-problem), it increasingly  takes more time for cp to solve the sub-problem! However, I don't know if the reason is behind the fact that in every iteration the current solution is one step closer to optimal solution and it would be harder for cp to improve the current solution, or it's because of the fact that the number of constraints are really increasing?!?

 

Any idea is appreciated,

Hossein

  • GGR
    GGR
    65 Posts

    Re: growing number of constraints

    ‏2013-06-14T16:13:01Z  

    Hi Hossein

    Seems a poor behavior. Nevertheless can you give me some insight.

     

    The version and language you are working on. (language are OPL, Java, .Net, and C++

    Do you confirm between two call to solve you do not change the model.

     

    For your last point, it seems a consequence of the first issue you raised.

     

    Cheers

     

     

  • HWFN_Hossein_Hojabri
    25 Posts

    Re: growing number of constraints

    ‏2013-06-17T20:19:24Z  
    • GGR
    • ‏2013-06-14T16:13:01Z

    Hi Hossein

    Seems a poor behavior. Nevertheless can you give me some insight.

     

    The version and language you are working on. (language are OPL, Java, .Net, and C++

    Do you confirm between two call to solve you do not change the model.

     

    For your last point, it seems a consequence of the first issue you raised.

     

    Cheers

     

     

    Hi, thanks for the reply.

     

    - I'm working with 125 version of CPLEX studio on C++.

    - Yes, the model doesn't change. However, one constraint is being updated at every iteration (obj<PrevObjVal: the value PrevObjVal is updated at every iteration). But, it does not explain it, because I even tried calling cp.solve() back to back for a number of times, like in the previous message. But, it showed in the interface that the number of constraints was increasing.

     

    Anyway, I have to make sure about the reason why CP takes much more time in the last iterations to solve the partial solution. I think this shouldn't  happen, especially because it's a satisfaction problem, and not an minimization one. At every iteration the solution objective value must be strictly better (as a constraint) than the one in the last step (or returns no solution found), though.

     

    Regards

  • Paul Shaw
    Paul Shaw
    7 Posts

    Re: growing number of constraints

    ‏2013-06-18T13:08:52Z  

    Hi, thanks for the reply.

     

    - I'm working with 125 version of CPLEX studio on C++.

    - Yes, the model doesn't change. However, one constraint is being updated at every iteration (obj<PrevObjVal: the value PrevObjVal is updated at every iteration). But, it does not explain it, because I even tried calling cp.solve() back to back for a number of times, like in the previous message. But, it showed in the interface that the number of constraints was increasing.

     

    Anyway, I have to make sure about the reason why CP takes much more time in the last iterations to solve the partial solution. I think this shouldn't  happen, especially because it's a satisfaction problem, and not an minimization one. At every iteration the solution objective value must be strictly better (as a constraint) than the one in the last step (or returns no solution found), though.

     

    Regards

    Hello,

     

    There are two things going on here.  First, you are seeing the constraint count going up at each solve.  This is a display bug which has

    been fixed in the recently released CPLEX Studio 12.5.1.  You don't really have more constraints at each solve, just the display is wrong,

    so the slowdown at each solve is not coming from additional constraints.

     

    The second point is that you are solving tighter and tighter problems (continually reduced solution space) at each round of your algorithm,

    so it is not surprising that solutions are harder and harder to find.  Does you problem have some special structure which makes you think

    that it should _not_ get harder as you tighten the objective constraint?

     

     

    Regards

  • HWFN_Hossein_Hojabri
    25 Posts

    Re: growing number of constraints

    ‏2013-06-19T15:37:08Z  
    • Paul Shaw
    • ‏2013-06-18T13:08:52Z

    Hello,

     

    There are two things going on here.  First, you are seeing the constraint count going up at each solve.  This is a display bug which has

    been fixed in the recently released CPLEX Studio 12.5.1.  You don't really have more constraints at each solve, just the display is wrong,

    so the slowdown at each solve is not coming from additional constraints.

     

    The second point is that you are solving tighter and tighter problems (continually reduced solution space) at each round of your algorithm,

    so it is not surprising that solutions are harder and harder to find.  Does you problem have some special structure which makes you think

    that it should _not_ get harder as you tighten the objective constraint?

     

     

    Regards

    Hi,

     

    Thanks for the reply. No, it does not have any special structure. Reporting the model, I found out that it's only the new constraint in the objective function which is added at each iteration. So, I think the reason why it gets slower each iteration is the fact that the problem gets tighter each iteration.

     

    Thanks,

    Hossein