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

James Cussens james.cussens at york.ac.uk
Thu Jun 7 21:34:19 MEST 2012


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



-- 
James Cussens
Dept of Computer Science &
York Centre for Complex Systems Analysis
Room 326, The Hub, Deramore Lane            Tel    +44 (0)1904 325371
University of York                                        Fax  +44
(0)1904 500159
York YO10 5GE, UK                               http://www.cs.york.ac.uk/~jc



More information about the Scip mailing list