<div dir="ltr">Hi Thorsten,<div><br></div><div>thanks for your reply! </div><div><br></div><div>The MIP instances I am working on arise from a research project on training neural networks with MIP techniques. If you want, I can send a PDF explaining the details of the model. For now, I have just attached two MIP instances that I have not been able to solve to optimality with SCIP. (Gurobi can handle the smaller one, parity_5.lp, very quickly using lots of heuristics. But even Gurobi did not manage to find an optimal solution to parity_6.lp in a day of computation.)</div>
<div><br></div><div>The reason I think branch-and-bound is not effective with this model, is that not only almost all ways of fixing the binary variables have a feasible solution, but also all the corresponding LP relaxations have an objective value that is close to optimal, so the "bound" step is not that effective at pruning branches. Hence my curiosity about how to work more with cutting planes.</div>
<div><br></div><div>Cheers,</div><div>Felix</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Sun, Jul 28, 2013 at 12:02 PM, Thorsten Koch <span dir="ltr"><<a href="mailto:koch@zib.de" target="_blank">koch@zib.de</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Felix,<br>
<br>
could you provide us an LP file of the instance and a<br>
short discription what you are modelling?<br>
<br>
The number of variables has no clear connection to the<br>
effectiveness of B&C.<br>
<br>
Best regards,<br>
Thorsten<br>
<br>
Am 28.07.2013 20:42, schrieb Felix Breuer:<br>
<div><div class="h5">> Hello everyone!<br>
><br>
> I am trying to solve a hard mixed-integer program to optimality. However,<br>
> branch and bound seems to be largely ineffective at finding an optimal<br>
> solution, simply because the search space is way too large. (There are 512<br>
> binary variables in my program, and I know for theoretical reasons that all<br>
> 2^512 ways of fixing these variables lead to a feasible solution.) I'd like<br>
> to experiment with using cutting planes more aggressively to solve the<br>
> problem, and I have a couple of questions:<br>
><br>
> 0) The "cuts" given by SCIP on the command line when solving the problem -<br>
> do these number give the number of cuts currently in the system, or do they<br>
> give the total number of cuts that have been added in the entire run?<br>
><br>
> 1) I tried adjusting the many parameters the SCIP offers for controlling<br>
> separators. However, I have been unable to make SCIP use more than about<br>
> 150 cuts. How can make SCIP use even more cutting planes?<br>
><br>
> 2) In particular, is there a way to configure SCIP not to use<br>
> branch-and-bound at all but only cutting planes to solve the problem? I<br>
> know that conventional wisdom says this is hopelessly inefficient. But I'd<br>
> like to investigate how this approach fares on my problems.<br>
><br>
> Thank you!<br>
><br>
> Felix<br>
><br>
><br>
><br>
><br>
><br>
</div></div>> _______________________________________________<br>
> Scip mailing list<br>
> <a href="mailto:Scip@zib.de">Scip@zib.de</a><br>
> <a href="http://listserv.zib.de/mailman/listinfo/scip" target="_blank">http://listserv.zib.de/mailman/listinfo/scip</a><br>
><br>
<br>
--<br>
The important thing is not to stop questioning.<br>
Curiosity has its own reason for existing. -- Albert Einstein<br>
______________________________________________________________________<br>
Dr. Thorsten Koch / Konrad-Zuse-Zentrum für Informationstechnik Berlin<br>
<a href="http://www.zib.de/koch" target="_blank">www.zib.de/koch</a> / Takustraße 7, 14195 Berlin-Dahlem, Germany<br>
<a href="mailto:koch@zib.de">koch@zib.de</a> / Phone <a href="tel:%2B49-30-84185-213" value="+493084185213">+49-30-84185-213</a>, Fax -269<br>
_______________/ DFG Research Center "Matheon" <a href="http://www.matheon.de" target="_blank">http://www.matheon.de</a><br>
<br>
Kooperativer Bibliotheksverbund Berlin Brandenburg <a href="http://www.kobv.de" target="_blank">http://www.kobv.de</a><br>
digiS: Servicestelle Digitalisierung Berlin<br>
<a href="http://www.servicestelle-digitalisierung.de" target="_blank">http://www.servicestelle-digitalisierung.de</a><br>
______________________________________________________________________<br>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><a href="http://www.felixbreuer.net">http://www.felixbreuer.net</a>
</div>