[Scip] best solution is not feasible in original problem
James Cussens
james.cussens at york.ac.uk
Thu Jul 26 10:29:46 MEST 2012
Hi Michael (and Timo),
Ah you're quite right, my fault entirely. The k heuristic is one of my
own and I had indeed not set the flags correctly.
(They were correct when I was not doing this sort of repeated solving.)
I've set the checking flags to TRUE and all is fine now.
Many thanks for your help.
Btw, all I'm doing here is finding feasible solutions in descending
order of objective value (ie optimal solution first).
Would it be possible to do this sort of thing using the countsols
constraint? My set of feasible solutions will be truly
astronomical so simply collecting all of them is impractical - hence
my interest in collecting the k best of them (for a modest value of
k).
If it is not directly/currently possible using countsols, might it be
possible with a bit of work?
James
On 25 July 2012 18:38, <michael.winkler at zib.de> wrote:
> 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
>>
>
--
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