All MILP solvers detect infeasibility as a by-product of the solution algorithm. Simply put, if no solution has been found when the algorithm terminates, the given problem is declared infeasible. If you are only interested in knowing whether a given instance is feasible or not, most solvers will allow you to stop when the first solution is found (and hence the instance is proven feasible). This way, you won't waste time searching for a better solution. Alternatively, you can use an objective function that is identically zero, but this will probably result in slightly longer running times, as there is some clean-up that occurs in the latter case. In some cases, giving a non-zero objective function could make the process faster, but this is hard to predict and would depend on the specific application. Hope this answers your question!<br>
<br>Cheers,<br><br>Ted<br><br><div class="gmail_quote">On Thu, Jun 28, 2012 at 5:47 AM, Rudan János <span dir="ltr"><<a href="mailto:rudanj@gmail.com" target="_blank">rudanj@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hello,<br>
<br>
I'm working on a problem where we use MILP to restructure a given<br>
directed graph. The infeasibility of the formulated MILP problem tells<br>
us that the original graph has some special structural property.<br>
<br>
Based on these, we are quite interested in the following: is it<br>
possible to test the feasibility of a given MILP? We do not care about<br>
a specific solution, the only question is the existency of the<br>
solution.<br>
<br>
I tried to look after this topic in the literature, but I cannot find<br>
any relevant information.<br>
Could you offer me some papers or software tools which could be relevant?<br>
<br>
Thanks,<br>
János<br>
<br>
_______________________________________________<br>
Symphony mailing list<br>
<a href="mailto:Symphony@list.coin-or.org">Symphony@list.coin-or.org</a><br>
<a href="http://list.coin-or.org/mailman/listinfo/symphony" target="_blank">http://list.coin-or.org/mailman/listinfo/symphony</a><br>
</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>