<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">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?<br>
<br>
The second link doesn't work ...<br>
<br>
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.<br>
<br>
Thank you!<br>
<br>
<br>
<br>
On 10/8/2012 23:36, Ted Ralphs wrote:<br>
</div>
<blockquote
cite="mid:CA+GYycs2YEpYWVxubt_WAt=Oj_Zj=iY7zqCsFWMG3uvrrfO3iw@mail.gmail.com"
type="cite">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 moz-do-not-send="true"
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 moz-do-not-send="true"
href="http://www.cs.elte.hu/%7Eilles/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
moz-do-not-send="true" 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 moz-do-not-send="true" 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
moz-do-not-send="true"
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
moz-do-not-send="true"
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 moz-do-not-send="true"
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
moz-do-not-send="true"
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="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 moz-do-not-send="true"
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 moz-do-not-send="true"
href="mailto:Cbc@list.coin-or.org"
target="_blank">Cbc@list.coin-or.org</a><br>
</font></tt><a moz-do-not-send="true"
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 moz-do-not-send="true"
href="mailto:Cbc@list.coin-or.org"
target="_blank">Cbc@list.coin-or.org</a><br>
<a moz-do-not-send="true"
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 moz-do-not-send="true"
href="tel:%28610%29%20628-1280" value="+16106281280"
target="_blank">(610) 628-1280</a><br>
ted 'at' lehigh 'dot' edu<br>
<a moz-do-not-send="true"
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 moz-do-not-send="true" href="http://coral.ie.lehigh.edu/%7Eted"
target="_blank">coral.ie.lehigh.edu/~ted</a><br>
<br>
</blockquote>
<br>
</body>
</html>