[Scip] cutting plane questions

Felix Breuer felix at fbreuer.de
Sun Jul 28 22:41:07 MEST 2013


Hi Thorsten,

thanks for your reply!

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.)

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.

Cheers,
Felix


On Sun, Jul 28, 2013 at 12:02 PM, Thorsten Koch <koch at zib.de> wrote:

> Hi Felix,
>
> could you provide us an LP file of the instance and a
> short discription what you are modelling?
>
> The number of variables has no clear connection to the
> effectiveness of B&C.
>
> Best regards,
> Thorsten
>
> Am 28.07.2013 20:42, schrieb Felix Breuer:
> > Hello everyone!
> >
> > I am trying to solve a hard mixed-integer program to optimality. However,
> > branch and bound seems to be largely ineffective at finding an optimal
> > solution, simply because the search space is way too large. (There are
> 512
> > binary variables in my program, and I know for theoretical reasons that
> all
> > 2^512 ways of fixing these variables lead to a feasible solution.) I'd
> like
> > to experiment with using cutting planes more aggressively to solve the
> > problem, and I have a couple of questions:
> >
> > 0) The "cuts" given by SCIP on the command line when solving the problem
> -
> > do these number give the number of cuts currently in the system, or do
> they
> > give the total number of cuts that have been added in the entire run?
> >
> > 1) I tried adjusting the many parameters the SCIP offers for controlling
> > separators. However, I have been unable to make SCIP use more than about
> > 150 cuts. How can make SCIP use even more cutting planes?
> >
> > 2) In particular, is there a way to configure SCIP not to use
> > branch-and-bound at all but only cutting planes to solve the problem? I
> > know that conventional wisdom says this is hopelessly inefficient. But
> I'd
> > like to investigate how this approach fares on my problems.
> >
> > Thank you!
> >
> > Felix
> >
> >
> >
> >
> >
> > _______________________________________________
> > Scip mailing list
> > Scip at zib.de
> > http://listserv.zib.de/mailman/listinfo/scip
> >
>
> --
> The important thing is not to stop questioning.
> Curiosity has its own reason for existing.          -- Albert Einstein
> ______________________________________________________________________
> Dr. Thorsten Koch / Konrad-Zuse-Zentrum für Informationstechnik Berlin
> www.zib.de/koch  /          Takustraße 7, 14195 Berlin-Dahlem, Germany
> koch at zib.de     /                     Phone +49-30-84185-213, Fax -269
> _______________/  DFG Research Center "Matheon"  http://www.matheon.de
>
> Kooperativer Bibliotheksverbund Berlin Brandenburg  http://www.kobv.de
> digiS: Servicestelle Digitalisierung Berlin
> http://www.servicestelle-digitalisierung.de
> ______________________________________________________________________
>



-- 
http://www.felixbreuer.net
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/pipermail/scip/attachments/20130728/e180a5b1/attachment.html
-------------- next part --------------
A non-text attachment was scrubbed...
Name: parity_5.lp
Type: application/octet-stream
Size: 99065 bytes
Desc: not available
Url : http://listserv.zib.de/pipermail/scip/attachments/20130728/e180a5b1/parity_5.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: parity_6.lp
Type: application/octet-stream
Size: 231475 bytes
Desc: not available
Url : http://listserv.zib.de/pipermail/scip/attachments/20130728/e180a5b1/parity_6.obj


More information about the Scip mailing list