[Symphony] testing infeasibility of an MILP problem

[Ted Ralphs]

Yes, there can be dramatic differences between solvers in solution time and
even the result of the computation. It is entirely possible for one solver
to find a model feasible while another finds the same model infeasible.

Differences in solution time are usually due to differences in the
algorithmic "bells and whistles" available with the solver. In the case of
quickly finding feasible solutions, good primal heuristics are important
and the commercial solvers are likely to excel there. Generally speaking,
CPLEX will find the first feasible solution much more quickly than
SYMPHONY, for example. Proving infeasibility is likely to be a bit less
variable, but there can still be substantial variation, even there.

Differences in the result of the procedure are almost always due to
numerical errors. Ultimately, the solution process involves approximation
due to the use of floating point computation (the results of calculations
have to be rounded off due to limits on numerical precision imposed by
processors). This can most often be avoided by following good practices for
modeling. Primarily, make sure your model is "well scaled" (the
coefficients are not of wildly different magnitudes). For some insight and
tips, see the recent thread on the CLP mailing list with the subject "Clp
finds feasible model infeasible" here:

http://list.coin-or.org/pipermail/clp/2012-June/thread.html#1281

The SYMPHONY parameter setting for stopping after the first feasible
solution is "find_first_feasible". There is no command-line switch for it,
but if you create a file name "symphony.par" (or what ever you like) with
the single line

find_first_feasible 1

and then invoke SYMPHONY with

symphony -f symphony.par

it should work. As far as I recall, DIP doesn't have a similar setting, but
this could be added. You could also check out Cbc, which is likely to be a
bit better than SYMPHONY for what you are trying to do.

Cheers,

Ted

On Fri, Jun 29, 2012 at 8:08 AM, Rudan János <rudanj at gmail.com> wrote:

> Thank you for your answer.
>
> I have two more questions:
>
> - in case of solving MILPs, sometimes it can happen that one solver
> can't find the optimal solution (or it works for a year to find it)
> while another solver can quickly find it. As far as I know this can
> happen because of some numerical issues e.g. settings of the used
> heuristics, tree exploration parameters etc. If I want to use an MILP
> solver to test the feasibility of a problem on a way you propsed (by
> stopping after the first solution) should I consider these kind of
> issues? (To put it simpler: is it possible that one solver will
> process a feasible problem for a long time while looking for a
> solution while another can quickly return with a first solution and by
> this prove the feasibility?)
>
> - with which command line parameter can I limit the number of
> solutions in case of using SYMPHONY (and/or DIP)? I found this only
> for CPLEX: "option cplex_options 'solutionlim=1'; "
>
> Thanks,
> János
>
> 2012/6/29 Ted Ralphs <ted at lehigh.edu>:
> > 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>
> >
>



-- 
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/20120629/f44cc8ed/attachment.html>