[Cbc] Artificial variables

Fri Aug 10 17:48:32 EDT 2012

I think that the method you are describing in your last paragraph means 
to use something like 1.2 Measuring infeasibility chapter of the book 
you suggested me, right?

The second link doesn't work ...

I was looking all the info you gave me, and wait before sending this 
email in case of finding new questions, that's why my late response.

Thank you!

On 10/8/2012 23:36, Ted Ralphs wrote:
> The "1 infeasibility" means (as far as I can tell) simply that there 
> was only variable for which the implied bounds lead to infeasibility. 
> However, the implied bounds on the single variable could have arisen 
> from any one or some combination of multiple constraints. Commercial 
> solvers, such as CPLEX, will determine IIS's for you automatically 
> (using a heuristic).
>
> Just to follow up with more references, here is a whole book on the 
> topic of infeasibility:
>
> http://www.amazon.com/Feasibility-Infeasibility-Optimization-Computational-International/dp/0387749314
>
> Just looking at the first few pages will give you some ideas. If you 
> check the authors home page, you will find papers and other materials. 
> Another group that has done a lot of work in this area is Edoardo 
> Amaldi et al. This paper here contains a good overview and summary of 
> what is known:
>
> http://www.cs.elte.hu/~illes/Tantargyak/.../Cikkek-1/MP-03- 
> <http://www.cs.elte.hu/%7Eilles/Tantargyak/.../Cikkek-1/MP-03->*IIS*.pdf
>
> You can try adding a slack variable to every constraint that 
> represents the degree of violation of that constraint and then try to 
> minimize the sum of infeasibilities, for example. You could also 
> associate these with binary variables and in a similar fashion try to 
> determine the smallest number of constraints that can be violated and 
> still maintain feasibility. This would, of course be a rather large 
> (and probably difficult_ integer program, but formulating it would be 
> easy and you might find a good heuristic solution fairly quickly.
>
> Good luck!
>
> Ted
>
> On Fri, Aug 10, 2012 at 4:04 PM, Christos <chtsolak at gmail.com 
> <mailto:chtsolak at gmail.com>> wrote:
>
>     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 <tel:%28610%29%20628-1280>
>>     ted 'at' lehigh 'dot' edu
>>     coral.ie.lehigh.edu/~ted <http://coral.ie.lehigh.edu/%7Eted>
>>
>
>
>
>
> -- 
> 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/20120811/4ee2f213/attachment-0001.html>