[Scip] cutting plane questions

[Felix Breuer]

Hello Timo, Matteo and Tobias,

thank you very much for all your feedback! Your comments have been very
helpful!

@Timo: Thanks for the pointers! With these settings I have been able to
generate many more cutting planes than I was able to previously. I'll
experiment and see if this gets me anywhere.

@Tobias: I am impressed that CPLEX was able to find an optimal solution
this quickly with a standard setting. I'll get my hands on an academic
license for CPLEX as soon as I have moved to my new position in Austria
(@RISC in Linz).

I don't need the solution vector, as I can write down an optimal solution
(with optimal value 0) by hand. But it is very good to know how to use
standard tools to solve this type of problem quickly.

@Matteo:

1) Yes, I guess you are right that heuristics are much more effective than
cutting planes here. My reasoning was that, even though the optimal
solution has an optimal value of 0 (which I know for theoretical reasons),
separators would iteratively cut of rational solutions on the optimal facet
until an integral solution is found. But thanks to Timo's tip, I see that
this is not much more effective than branch-and-bound.

2) Your proximity search heuristic sounds very interesting. I'll be sure to
try it out as soon as I have obtained a copy of CPLEX. Please let me know
when your method becomes available on NEOS!

3) I did not declare ep* and em* binary because I thought fewer integrality
constraints might make things easier. I'll check if I notice when I make
them binary.

4) Thanks for the pointer to your note on SVMs. I'll get back to you when I
have taken a closer look at it.


Cheers,
Felix


On Mon, Jul 29, 2013 at 12:08 PM, Tobias Achterberg <achterberg at zib.de>wrote:

> Hi Felix,
>
> FYI: also for your parity_6.lp model, 0 is the optimal objective value.
> I solved this with CPLEX 12.5.1, letting it run for some time in default
> settings and then switching to polishing. Polishing itself only took 550
> seconds to improve the incumbent of objective value 7 to one with value 0.
>
> If you are interested in the x vector of the solution, just contact me
> privately.
>
>
> Regards,
>
> Tobias
>
>
>
> On 07/28/13 20:42, Felix Breuer wrote:
>
>> 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
>>
>>
>>
>> --
>> http://www.felixbreuer.net
>>
>>
>> ______________________________**_________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/**mailman/listinfo/scip<http://listserv.zib.de/mailman/listinfo/scip>
>>
>


-- 
http://www.felixbreuer.net
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/pipermail/scip/attachments/20130729/ca9d9703/attachment.html