[Cbc] Artificial variables

[Christos]

Your info was proved to be very useful!

Is there any possibility the infeasibility to be caused from another 
reason other than that you mentioned? (upper bound<lower bound),

and the "1 infeasibility" message means that there is problem only with 
one number in the problem?

I am reading many of the articles and hope to find a solution soon..

Your help is much appreciated!


On 10/8/2012 20:05, Ted Ralphs wrote:
> As far as I can tell from the output and from a brief perusal of the 
> source, the model is being found infeasible by the pre-solve during 
> the process of tightening bounds. In a nutshell, the solver tries to 
> determine if there are "implied bounds" for any of the variables that 
> are tighter than the ones actually given in the problem description. 
> The logic is that if you have, e.g.,
>
> x1 + x2 <=1
>
> and x1 and x2 are non-negative variables, then they each have an 
> implied upper bound of 1, even if this is not given as part of the 
> input. You can get implied bounds from the each constraint for each 
> variable and these can be tightened in multiple rounds---one round of 
> tightening leads to further implications in the next round. If the 
> result of this tightening is that the lower bound of a given variable 
> ends up higher than its upper bound, the model is infeasible. As far 
> as I can tell, the number that is being reported there is the number 
> of such violations, but to be honest, this number is very hard to 
> interpret. The single infeasibility could have been caused by any 
> number of the actual linear constraints.
>
> Determining what constraints are causing infeasibility is a difficult 
> problem in general and has been the subject of much research. A good 
> place to start to find out about this area is to put "irreducible 
> inconsistent system" in Google Scholar:
>
> http://goo.gl/qdqyU
>
> Cheers,
>
> Ted
>
> On Fri, Aug 10, 2012 at 12:37 PM, Christos <chtsolak at gmail.com 
> <mailto:chtsolak at gmail.com>> wrote:
>
>     I forgot to mention that it is a minimization problem , so i do
>     not know if there is any point in limiting objective.
>
>     Sorry for the double mail.
>
>
>     On 10/8/2012 19:24, acw at ascent.com <mailto:acw at ascent.com> wrote:
>>     No single constraint is responsible for an infeasibility.
>>      Consider a system with one variable, and two constraints, X >= 7
>>     and X <= 4.  This system is obviously infeasible, but which of
>>     the two constraints is at fault?
>>
>>     In your case I suspect that the problem is unbounded rather than
>>     infeasible, because you have so few constraints and so many
>>     variables.  Unless the problem has a very special structure, a
>>     problem with fewer constraints than variables is likely to be
>>     unbounded.
>>
>>     You can check this by adding a constraint that limits your
>>     objective to, say, 1e6.  If the problem now solves, then
>>     unboundedness is almost certainly your difficulty.
>>
>>
>>     From: 	Christos <chtsolak at gmail.com> <mailto:chtsolak at gmail.com>
>>     To: 	cbc at list.coin-or.org <mailto:cbc at list.coin-or.org>
>>     Date: 	08/10/2012 09:32 AM
>>     Subject: 	[Cbc] Artificial variables
>>
>>
>>     ------------------------------------------------------------------------
>>
>>
>>
>>     Hi, i have a model with around 10000 variable and 1500 equations.
>>
>>     But i get the messages on the photo when i run it:
>>     http://imageshack.us/photo/my-images/39/dascd.png/
>>
>>     Is there any way to use artificial variable or something else in
>>     order
>>     to find the problematic equation?
>>
>>     Thank you in advance
>>     _______________________________________________
>>     Cbc mailing list
>>     Cbc at list.coin-or.org <mailto:Cbc at list.coin-or.org>
>>     http://list.coin-or.org/mailman/listinfo/cbc
>>
>
>
>     _______________________________________________
>     Cbc mailing list
>     Cbc at list.coin-or.org <mailto:Cbc at list.coin-or.org>
>     http://list.coin-or.org/mailman/listinfo/cbc
>
>
>
>
> -- 
> Dr. Ted Ralphs
> Associate Professor, Lehigh University
> (610) 628-1280
> ted 'at' lehigh 'dot' edu
> coral.ie.lehigh.edu/~ted <http://coral.ie.lehigh.edu/%7Eted>
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20120810/58d2eb6f/attachment-0001.html>