[Symphony] testing infeasibility of an MILP problem

[Rudan János]

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
>