[Symphony] testing infeasibility of an MILP problem

[Ted Ralphs]

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!

Cheers,

Ted

On Thu, Jun 28, 2012 at 5:47 AM, Rudan János <rudanj at gmail.com> wrote:

> Hello,
>
> I'm working on a problem where we use MILP to restructure a given
> directed graph. The infeasibility of the formulated MILP problem tells
> us that the original graph has some special structural property.
>
> Based on these, we are quite interested in the following: is it
> possible to test the feasibility of a given MILP? We do not care about
> a specific solution, the only question is the existency of the
> solution.
>
> I tried to look after this topic in the literature, but I cannot find
> any relevant information.
> Could you offer me some papers or software tools which could be relevant?
>
> Thanks,
> János
>
> _______________________________________________
> Symphony mailing list
> Symphony at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/symphony
>



-- 
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/symphony/attachments/20120628/8490c223/attachment.html>