[Scip] finding cutting planes is scip2.0.1 and scip2.1.0

Gerald Gamrath gamrath at zib.de
Fri Jun 8 09:24:28 MEST 2012


Hi James,

one of the new features of the SCIP 2.1 release was the solution pool. 
That means, that the best K (= 10 per default) solutions are stored in 
the solution pool after you solved a sub-SCIP. If you then change the 
objective function or some constraints/bounds and reoptimize in your 
next separation round, these 10 solutions are tested for feasibility in 
the modified problem and added as solutions if they are feasible.
They are also added if they are worse than the objective limit you 
specified, but that is intended because even these solutions can be used 
by improvement heuristics to construct better solutions. By the way, 
this was also the case in older SCIP versions, i.e., if a heuristic 
found a solution worse than the objective limit, it was added, but it 
did not occur so often, while now, there are these 10 candidates and 
many of them are probably feasible.
You do not need to add the objective limit as an explicit constraint, 
that will probably decrease the performance. However, you can just check 
the objective value of the solutions with SCIPgetSolOrigObj(). Since the 
array of solutions that SCIP returns is decreasingly ordered by the 
quality of the solutions, you can just stop when one solution has a 
value >= 1 and do not have to check the remaining ones.

I hope that solves your issue.

Best,
Gerald

Am 07.06.2012 21:34, schrieb James Cussens:
> Hi Stefan,
>
> I think I might have found the problem. My subscip that searches for
> cutting planes is only interested in solutions with an objective value
> less than 1. So I have this:
>
> SCIP_CALL( SCIPsetObjlimit(subscip, 1.0) );
>
> But (sometimes) I get this:
>
> [src/cons_dagcluster.c:657] debug: checking DAG cluster constraint<DagCluster>.
> 10 feasible solutions given by solution candidate storage
> presolving:
> presolving (0 rounds):
>   0 deleted vars, 0 deleted constraints, 0 added constraints, 0
> tightened bounds, 0 added holes, 0 changed sides, 0 changed
> coefficients
>   0 implications, 0 cliques
> presolved problem has 41 variables (41 bin, 0 int, 0 impl, 0 cont) and
> 34 constraints
>       33 constraints of type<and>
>        1 constraints of type<linear>
> transformed objective value is always integral (scale: 1)
> Presolving Time: 0.00
>
>   time | node  | left  |LP iter|LP it/n| mem |mdpt |vars |cons |
> estimate   |  dualbound   | primalbound  | cutoffbound  |  gap
> |nsols
> # 0.0s|     1 |     0 |     0 |     - | 222k|   0 |  41 |  10 |
> --      | 1.000000e+00 | 1.000000e+00 | 1.000000e-04 |   0.00%|   10
>
> SCIP Status        : problem is solved [optimal solution found]
> Solving Time (sec) : 0.00
> Solving Nodes      : 1
> Primal Bound       : +1.00000000000000e+00 (10 solutions)
> Dual Bound         : +1.00000000000000e+00
> Gap                : 0.00 %
> [src/cons_dagcluster.c:706] debug: primal solution DOES NOT satify the
> DAG cluster constrain.
>
> My guess is that these '10 feasible solutions' which appear to be
> provided to the subscip ahead of solving are seen as OK solutions even
> though
> they have objective value of 1 (too high). This seems a probable cause
> of my problem since I note that the code doing this (in scip.c) is
> there in 2.1.0 but not 2.0.1.
>
> This makes sense, an objective value of 1 (or above) translates to a
> useless cutting plane, and I'm getting a lot of those.
>
> I suppose I could put the ObjLimit in as an explicit constraint, but
> that's a bit messy.
>
> What do you (or anyone else) think?
>
> James
>
>
> On 6 June 2012 07:39, Stefan Heinz<heinz at zib.de>  wrote:
>> Hi James,
>>
>> to ge an idea what happens, could ypu please rerun the example and call
>>
>> SCIP_CALL( SCIPprintStatistics(scip, NULL) );
>> http://scip.zib.de/doc/html/scip_8h.html#a6e7eb26b996d4466493a504a0924a35d
>>
>> before you kill SCIP. These statistics might give us a hint.
>>
>> Stefan
>>
>>
>> On 06/05/12 09:43, James Cussens wrote:
>>> I have a constraint handler which includes some code for finding
>>> cutting planes for a machine learning problem (Bayesian net learning).
>>> With SCIP 2.0.1 this works well. The routine for finding the cutting
>>> planes (a sub-MIP which uses a depth-first search, no linear
>>> relaxation finds (usually several) good cutting planes. Moving to SCIP
>>> 2.1.0 the story is very different. On even very easy problems vast
>>> numbers of useless cutting planes are found.
>>>
>>> The two attached files tell the story. With SCIP 2.0.1 13 cutting
>>> planes are enough to solve the problem. With SCIP 2.1.0 I had to
>>> terminate the process after very many (mostly bad) cutting planes had
>>> been generated.
>>>
>>> My code is the same in both cases, except to account for the extra
>>> constraint handler argument in SCIP 2.1.0. The attached files were
>>> produced just after a fresh install of the two SCIPs just to be sure.
>>>
>>> Perhaps there is a simple explanation. Some crucial change to a
>>> default value, perhaps.
>>>
>>> Any ideas? I'm happy to send out my source(s) if that would help anyone.
>>>
>>>
>>>
>>> _______________________________________________
>>> Scip mailing list
>>> Scip at zib.de
>>> http://listserv.zib.de/mailman/listinfo/scip
>>
>
>


More information about the Scip mailing list