[Scip] best solution is not feasible in original problem
michael.winkler@zib.de
michael.winkler at zib.de
Wed Jul 25 19:38:04 MEST 2012
Hi,
> k 0.3s| 1 | 0 | 34 | - | 377k| 0 | 4 | 97 | 38 |
> 97 | 56 | 16 | 0 | 0 | 6.725550e+01 | 6.725550e+01 | 0.00%
the above line indicate that the heuristic with the display character 'k'
found this solution. Can you please check, which heuristic this is? (You
can display all heuristics in the interactive shell via 'display
heuristics'.)
It might be that inside this heuristic, a SCIPtrySol() or SCIPtrySolFree()
call has not correct values on the checking flags, or even it is used
SCIPaddSol() which does not check the created solution at all but adds it
directly to SCIP.
( see also:
http://scip.zib.de/doc/html/scip_8h.html#ae4041777d638e0bcbbb592946b520f15
http://scip.zib.de/doc/html/scip_8h.html#af00de2379f996445b4497db79e7449f0
http://scip.zib.de/doc/html/scip_8h.html#a9b51e1c9e28d3f6f9f45f37bfdb77897
)
The other possible explanation that comes in mind, is that your added
constraints are wrongly?! removed. (Which does not need to happen in
presolving but also during branch and bound, due to some global
information.)
Best, Michael
> Hi there,
>
> I'm solving a series of MIP problems as follows. When an optimal
> solution is found for problem i, a constraint ruling out that solution
> is added
> and that's problem i+1.
>
> I do this by repeatedly:
> 1) storing information about the optimal solution
> 2) doing freetransform
> 3) creating, adding and releasing the constraint to rule out the
> just-found optimal solution
> 4) solving
>
> This works entirely as expected on the first few iterations, the
> number of constraints increments on each iteration and different
> optimal solutions are found (to the different problems).
> but then I get an optimal solution which is the one (I thought) I had
> just ruled out. SCIP agrees telling me
> best solution is not feasible in original problem.
>
> I've removed presolving and set
> limits/maxsol = 1
> limits/maxorigsol = 0
> to see if that helps, but the problem remained.
>
> There's some output below. The 5 linear constraints are the 'ruling
> out previously found optimal solutions' constraints. 5 is the correct
> number.
>
> Can anyone indicate what might be going wrong here?
>
> James
>
> feasible solution found by trivial heuristic, objective value
> 0.000000e+00
> 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 97 variables (97 bin, 0 int, 0 impl, 0 cont) and
> 39 constraints
> 1 constraints of type <linearordering>
> 32 constraints of type <setppc>
> 1 constraints of type <dagcluster>
> 5 constraints of type <linear>
> Presolving Time: 0.01
>
> time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons
> |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
> t 0.0s| 1 | 0 | 0 | - | 363k| 0 | 0 | 97 | 38 |
> 97 | 40 | 0 | 0 | 0 | 1.087396e+02 |-0.000000e+00 | Inf
> k 0.0s| 1 | 0 | 0 | - | 364k| 0 | 0 | 97 | 38 |
> 97 | 40 | 0 | 0 | 0 | 1.087396e+02 | 6.561041e+01 | 65.74%
> 0.0s| 1 | 0 | 1 | - | 364k| 0 | 0 | 97 | 38 |
> 97 | 41 | 1 | 0 | 0 | 9.442973e+01 | 6.561041e+01 | 43.92%
> 0.0s| 1 | 0 | 2 | - | 365k| 0 | 0 | 97 | 38 |
> 97 | 42 | 2 | 0 | 0 | 8.860709e+01 | 6.561041e+01 | 35.05%
> 0.1s| 1 | 0 | 3 | - | 365k| 0 | 0 | 97 | 38 |
> 97 | 43 | 3 | 0 | 0 | 8.860709e+01 | 6.561041e+01 | 35.05%
> 0.1s| 1 | 0 | 4 | - | 366k| 0 | 0 | 97 | 38 |
> 97 | 44 | 4 | 0 | 0 | 8.573660e+01 | 6.561041e+01 | 30.68%
> 0.1s| 1 | 0 | 6 | - | 367k| 0 | 0 | 97 | 38 |
> 97 | 45 | 5 | 0 | 0 | 8.503228e+01 | 6.561041e+01 | 29.60%
> k 0.1s| 1 | 0 | 6 | - | 367k| 0 | 0 | 97 | 38 |
> 97 | 45 | 5 | 0 | 0 | 8.503228e+01 | 6.724083e+01 | 26.46%
> 0.1s| 1 | 0 | 7 | - | 368k| 0 | 0 | 97 | 38 |
> 97 | 46 | 6 | 0 | 0 | 8.454296e+01 | 6.724083e+01 | 25.73%
> 0.1s| 1 | 0 | 8 | - | 368k| 0 | 0 | 97 | 38 |
> 97 | 47 | 7 | 0 | 0 | 8.454296e+01 | 6.724083e+01 | 25.73%
> 0.1s| 1 | 0 | 9 | - | 369k| 0 | 0 | 97 | 38 |
> 97 | 48 | 8 | 0 | 0 | 8.440381e+01 | 6.724083e+01 | 25.52%
> 0.1s| 1 | 0 | 10 | - | 369k| 0 | 0 | 97 | 38 |
> 97 | 49 | 9 | 0 | 0 | 8.440381e+01 | 6.724083e+01 | 25.52%
> 0.1s| 1 | 0 | 11 | - | 370k| 0 | 0 | 97 | 38 |
> 97 | 50 | 10 | 0 | 0 | 7.079853e+01 | 6.724083e+01 | 5.29%
> 0.2s| 1 | 0 | 20 | - | 371k| 0 | 0 | 97 | 38 |
> 97 | 51 | 11 | 0 | 0 | 6.787422e+01 | 6.724083e+01 | 0.94%
> k 0.2s| 1 | 0 | 20 | - | 371k| 0 | 0 | 97 | 38 |
> 97 | 51 | 11 | 0 | 0 | 6.787422e+01 | 6.724083e+01 | 0.94%
> time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons
> |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
> 0.2s| 1 | 0 | 20 | - | 371k| 0 | 0 | 97 | 38 |
> 97 | 51 | 11 | 0 | 0 | 6.787422e+01 | 6.724083e+01 | 0.94%
> 0.2s| 1 | 0 | 21 | - | 373k| 0 | 0 | 97 | 38 |
> 97 | 52 | 12 | 0 | 0 | 6.787422e+01 | 6.724083e+01 | 0.94%
> 0.2s| 1 | 0 | 21 | - | 373k| 0 | 0 | 97 | 38 |
> 97 | 52 | 12 | 0 | 0 | 6.787422e+01 | 6.724083e+01 | 0.94%
> k 0.2s| 1 | 0 | 21 | - | 373k| 0 | 0 | 97 | 38 |
> 97 | 52 | 12 | 0 | 0 | 6.787422e+01 | 6.724083e+01 | 0.94%
> 0.2s| 1 | 0 | 23 | - | 373k| 0 | 3 | 97 | 38 |
> 97 | 53 | 13 | 0 | 0 | 6.780219e+01 | 6.724083e+01 | 0.83%
> 0.2s| 1 | 0 | 25 | - | 374k| 0 | 9 | 97 | 38 |
> 97 | 54 | 14 | 0 | 0 | 6.769914e+01 | 6.724083e+01 | 0.68%
> 0.3s| 1 | 0 | 28 | - | 377k| 0 | 3 | 97 | 38 |
> 97 | 55 | 15 | 0 | 0 | 6.755507e+01 | 6.724083e+01 | 0.47%
> 0.3s| 1 | 0 | 28 | - | 377k| 0 | 3 | 97 | 38 |
> 97 | 55 | 15 | 0 | 0 | 6.755507e+01 | 6.724083e+01 | 0.47%
> 0.3s| 1 | 0 | 34 | - | 377k| 0 | 4 | 97 | 38 |
> 97 | 56 | 16 | 0 | 0 | 6.725550e+01 | 6.724083e+01 | 0.02%
> k 0.3s| 1 | 0 | 34 | - | 377k| 0 | 4 | 97 | 38 |
> 97 | 56 | 16 | 0 | 0 | 6.725550e+01 | 6.725550e+01 | 0.00%
> 0.3s| 1 | 0 | 34 | - | 377k| 0 | 4 | 97 | 38 |
> 97 | 56 | 16 | 0 | 0 | 6.725550e+01 | 6.725550e+01 | 0.00%
>
> SCIP Status : problem is solved [optimal solution found]
> Solving Time (sec) : 0.28
> Solving Nodes : 1
> Primal Bound : +6.72555038970200e+01 (6 solutions)
> Dual Bound : +6.72555038970200e+01
> Gap : 0.00 %
> [linear] <ruleout#0>: <I(0<-{2,5,})>[B] +<I(1<-{6,})>[B]
> +<I(2<-{6,5,})>[B] +<I(3<-{2,})>[B] -<I(4<-{5,})>[B] +<I(5<-{4,})>[B]
> -<I(6<-{2,1,})>[B] -<I(6<-{0,1,})>[B] -<I(6<-{1,})>[B]
> -<I(6<-{2,7,})>[B] -<I(6<-{0,7,})>[B] -<I(6<-{2,})>[B]
> -<I(6<-{0,})>[B] -<I(6<-{7,})>[B] -<I(6<-{3,})>[B] +<I(7<-{1,})>[B] <=
> 5;
> violation: right hand side is violated by 1
> best solution is not feasible in original problem
>
> --
> 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
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>
More information about the Scip
mailing list