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). <br>
<br>Just to follow up with more references, here is a whole book on the topic of infeasibility:<br><br><a href="http://www.amazon.com/Feasibility-Infeasibility-Optimization-Computational-International/dp/0387749314">http://www.amazon.com/Feasibility-Infeasibility-Optimization-Computational-International/dp/0387749314</a><br>
<br>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:<br>
<br><cite><a href="http://www.cs.elte.hu/~illes/Tantargyak/.../Cikkek-1/MP-03-">http://www.cs.elte.hu/~illes/Tantargyak/.../Cikkek-1/MP-03-</a><b>IIS</b>.pdf</cite><br><br>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. <br>
<br>Good luck!<br><br>Ted<br><div class="gmail_quote"><br>On Fri, Aug 10, 2012 at 4:04 PM, Christos <span dir="ltr"><<a href="mailto:chtsolak@gmail.com" target="_blank">chtsolak@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<div>Your info was proved to be very useful!<br>
<br>
Is there any possibility the infeasibility to be caused from
another reason other than that you mentioned? (upper
bound<lower bound),<br>
<br>
and the "1 infeasibility" message means that there is problem only
with one number in the problem?<br>
<br>
I am reading many of the articles and hope to find a solution
soon..<br>
<br>
Your help is much appreciated!<div><div class="h5"><br>
<br>
<br>
On 10/8/2012 20:05, Ted Ralphs wrote:<br>
</div></div></div><div><div class="h5">
<blockquote type="cite">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.,<br>
<br>
x1 + x2 <=1<br>
<br>
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. <br>
<br>
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:<br>
<br>
<a href="http://goo.gl/qdqyU" target="_blank">http://goo.gl/qdqyU</a><br>
<br>
Cheers,<br>
<br>
Ted<br>
<br>
<div class="gmail_quote">On Fri, Aug 10, 2012 at 12:37 PM,
Christos <span dir="ltr"><<a href="mailto:chtsolak@gmail.com" target="_blank">chtsolak@gmail.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<div>I forgot to mention that it is a minimization problem ,
so i do not know if there is any point in limiting
objective.<br>
<br>
Sorry for the double mail.
<div><br>
<br>
On 10/8/2012 19:24, <a href="mailto:acw@ascent.com" target="_blank">acw@ascent.com</a>
wrote:<br>
</div>
</div>
<div>
<div>
<blockquote type="cite"><font face="sans-serif">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?</font> <br>
<br>
<font face="sans-serif">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.</font> <br>
<br>
<font face="sans-serif">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.</font> <br>
<br>
<br>
<table width="100%">
<tbody>
<tr valign="top">
<td><font color="#5f5f5f" face="sans-serif" size="1">From:</font> </td>
<td><font face="sans-serif" size="1">Christos <a href="mailto:chtsolak@gmail.com" target="_blank"><chtsolak@gmail.com></a></font>
</td>
</tr>
<tr valign="top">
<td><font color="#5f5f5f" face="sans-serif" size="1">To:</font> </td>
<td><font face="sans-serif" size="1"><a href="mailto:cbc@list.coin-or.org" target="_blank">cbc@list.coin-or.org</a></font>
</td>
</tr>
<tr valign="top">
<td><font color="#5f5f5f" face="sans-serif" size="1">Date:</font> </td>
<td><font face="sans-serif" size="1">08/10/2012
09:32 AM</font> </td>
</tr>
<tr valign="top">
<td><font color="#5f5f5f" face="sans-serif" size="1">Subject:</font> </td>
<td><font face="sans-serif" size="1">[Cbc]
Artificial variables</font></td>
</tr>
</tbody>
</table>
<br>
<hr noshade> <br>
<br>
<br>
<tt><font>Hi, i have a model with around 10000
variable and 1500 equations.<br>
<br>
But i get the messages on the photo when i run it:<br>
</font></tt><a href="http://imageshack.us/photo/my-images/39/dascd.png/" target="_blank"><tt><font>http://imageshack.us/photo/my-images/39/dascd.png/</font></tt></a><tt><font><br>
<br>
Is there any way to use artificial variable or
something else in order <br>
to find the problematic equation?<br>
<br>
Thank you in advance<br>
_______________________________________________<br>
Cbc mailing list<br>
<a href="mailto:Cbc@list.coin-or.org" target="_blank">Cbc@list.coin-or.org</a><br>
</font></tt><a href="http://list.coin-or.org/mailman/listinfo/cbc" target="_blank"><tt><font>http://list.coin-or.org/mailman/listinfo/cbc</font></tt></a><tt><font><br>
</font></tt> <br>
</blockquote>
<br>
</div>
</div>
</div>
<br>
_______________________________________________<br>
Cbc mailing list<br>
<a href="mailto:Cbc@list.coin-or.org" target="_blank">Cbc@list.coin-or.org</a><br>
<a href="http://list.coin-or.org/mailman/listinfo/cbc" target="_blank">http://list.coin-or.org/mailman/listinfo/cbc</a><br>
<br>
</blockquote>
</div>
<br>
<br clear="all">
<br>
-- <br>
Dr. Ted Ralphs<br>
Associate Professor, Lehigh University<br>
<a href="tel:%28610%29%20628-1280" value="+16106281280" target="_blank">(610) 628-1280</a><br>
ted 'at' lehigh 'dot' edu<br>
<a href="http://coral.ie.lehigh.edu/%7Eted" target="_blank">coral.ie.lehigh.edu/~ted</a><br>
<br>
</blockquote>
<br>
</div></div></div>
</blockquote></div><br><br clear="all"><br>-- <br>Dr. Ted Ralphs<br>Associate Professor, Lehigh University<br>(610) 628-1280<br>ted 'at' lehigh 'dot' edu<br><a href="http://coral.ie.lehigh.edu/%7Eted" target="_blank">coral.ie.lehigh.edu/~ted</a><br>
<br>