Topic
  • 2 replies
  • Latest Post - ‏2012-11-21T09:48:36Z by SystemAdmin
SystemAdmin
SystemAdmin
623 Posts

Pinned topic *Adding* constraints to an infeasible model makes the model become feasible

‏2012-11-20T20:04:56Z |
Hi everybody, I just incurred in a weird behavior of the CP solver. Suppose I have a model M, i.e.: a conjunction of constraints with an objective function. M is said to be unfeasible by CP. Suppose now I add to the model some equality constraints on some variables, stating that they should be equal to an a-priori known solution of M. Let's call this model M' = M /\ c1 /\ c2 /\ ... /\ cn, where c1...cn are equality constraints of the form "x1 == 4", or "x3 == 7" coming from a known solution to M, with x1 and x3 being variables. When CP solves M', it finds a solution which of course has the values I forced via c1...cn (in this case, x1 = 4 and x3 = 7 ).

I just fail to see how can M not have any solution, while M' has one: first order logic says M /\ c1...cn => M, so if M' has a solution, M should also have at least one (possibly more since c1...cn could cut off some other solutions, and in this case being equality constraints for sure they do).

This same behavior happens if I remove the objective function from M, switching from a Constraint Optimization problem to a Constraint Satisfaction Problem. Let's call M'' the model derived from M by removing the objective function. Again, CP tells that M'' is feasible. It's pretty obvious to me that if M'' is feasible (having a solution x'' ), then M should be as well, having a solution x with objective value better or equal than x''.

How can this be?

Regards,
Stefano
Updated on 2012-11-21T09:48:36Z at 2012-11-21T09:48:36Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    623 Posts

    Re: *Adding* constraints to an infeasible model makes the model become feasible

    ‏2012-11-21T08:29:14Z  
    Hi Stefano,

    If a model M has no solution, adding constraints to that model cannot make it feasible. Unless you have a set a limit on CP Optimizer, you should not find any solution to the extended model if M does not have any. So this is a strange behavior.

    The best is that you send us a small model demonstrating the problem and we will have a look at it.

    Thanks

    Philippe
  • SystemAdmin
    SystemAdmin
    623 Posts

    Re: *Adding* constraints to an infeasible model makes the model become feasible

    ‏2012-11-21T09:48:36Z  
    Hi Stefano,

    If a model M has no solution, adding constraints to that model cannot make it feasible. Unless you have a set a limit on CP Optimizer, you should not find any solution to the extended model if M does not have any. So this is a strange behavior.

    The best is that you send us a small model demonstrating the problem and we will have a look at it.

    Thanks

    Philippe
    Forget about it: indeed you gave me a very precious hint. I found out that the problem was a configuration file with a time limit on the resolution which shouldn't have been on that run configuration. My apologies.

    Regards,
    Stefano