[Scip] best solution is not feasible in original problem
James Cussens
james.cussens at york.ac.uk
Wed Jul 25 18:05:58 MEST 2012
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
More information about the Scip
mailing list