[Cbc] Artificial variables

[Ted Ralphs]

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> 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 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> <chtsolak at gmail.com>  To:
> 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
> http://list.coin-or.org/mailman/listinfo/cbc
>
>
>
> _______________________________________________
> Cbc mailing list
> 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/7fd1d38d/attachment-0001.html>