[SCIP] About dual solution in a column generation approach
dponce at us.es
dponce at us.es
Tue Apr 17 17:20:04 CEST 2018
Dear SCIP,
Developing a B&P project, we have some questions about the behavior we
have among the different iterations of the pricer.
Attached you have the output of a set partitioning formulation for which
eventually the optimal solution is reached. But still I see a couple of
things I don't understand:
* Line 109. Why the first solution of the dual problem is not -24.0?
With the initial variables the dual problem should have constraints to
avoid solution -10.0.
* Line 279. If previously the solution was -114.0, why suddenly goes
back to -112.0?
Regarding this previous question
http://listserv.zib.de/pipermail/scip/2017-July/003156.html
and the binpacking example, we have disabled the preprocessing. Is it
disabled in the VRP example?
Dual solution has been handily calculated from the dual multiplier. Are
there some SCIP function to make this for the current solution? And for
primal? Anyway, we trust on our calculation and this is a way to check
the correctness of the dual multiplier values.
We are debugging our code, but right now, we don't have more ideas. We
have thought in DELAY and removable option in the variables as an
explanation of this behavior, but nothing.
Thanks in advance for the help.
Best.
Diego Ponce.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20180417/ba989c34/attachment.html>
-------------- next part --------------
Heuristic parameter: h
argheu, 1
LP Solver <SoPlex 3.1.1>: barrier convergence tolerance cannot be set -- tolerance of SCIP and LP solver may differ
LP Solver <SoPlex 3.1.1>: fastmip setting not available -- SCIP parameter has no effect
LP Solver <SoPlex 3.1.1>: number of threads settings not available -- SCIP parameter has no effect
PROBTRANS
transformed problem has 50 variables (50 bin, 0 int, 0 impl, 0 cont) and 20 constraints
20 constraints of type <linear>
original problem has 80 active (8%) nonzeros and 80 (8%) check nonzeros
STATISTICS
Problem name : t_clustering
Variables : 50 (50 binary, 0 integer, 0 implicit integer, 0 continuous)
Constraints : 0 initial, 20 maximal
OBJECTIVE
Sense : minimize
VARIABLES
[binary] <t_Y_1>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_2>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_3>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_4>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_5>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_6>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_7>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_8>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_9>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_10>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_11>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_12>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_13>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_14>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_15>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_16>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_17>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_18>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_19>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_20>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_1,2>: obj=4, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_1,10>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_2,3>: obj=4, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_3,7>: obj=4, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_3,10>: obj=-4, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_4,8>: obj=-4, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_4,9>: obj=-2, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_4,13>: obj=2, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_5,10>: obj=-4, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_5,14>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_6,7>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_6,9>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_6,10>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_6,15>: obj=-2, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_7,8>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_7,9>: obj=-2, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_8,11>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_9,10>: obj=-6, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_11,14>: obj=2, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_11,16>: obj=2, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_12,13>: obj=2, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_12,15>: obj=-4, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_12,16>: obj=-2, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_13,17>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_13,18>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_13,19>: obj=-8, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_14,16>: obj=-2, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_15,20>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_16,19>: obj=0, global bounds=[-0,1], local bounds=[-0,1]
[binary] <t_Y_16,20>: obj=2, global bounds=[-0,1], local bounds=[-0,1]
CONSTRAINTS
[linear] <I1>: 0 <= <t_Y_1>[B] +<t_Y_1,2>[B] +<t_Y_1,10>[B] <= 1;
[linear] <I2>: 0 <= <t_Y_2>[B] +<t_Y_1,2>[B] +<t_Y_2,3>[B] <= 1;
[linear] <I3>: 0 <= <t_Y_3>[B] +<t_Y_2,3>[B] +<t_Y_3,7>[B] +<t_Y_3,10>[B] <= 1;
[linear] <I4>: 0 <= <t_Y_4>[B] +<t_Y_4,8>[B] +<t_Y_4,9>[B] +<t_Y_4,13>[B] <= 1;
[linear] <I5>: 0 <= <t_Y_5>[B] +<t_Y_5,10>[B] +<t_Y_5,14>[B] <= 1;
[linear] <I6>: 0 <= <t_Y_6>[B] +<t_Y_6,7>[B] +<t_Y_6,9>[B] +<t_Y_6,10>[B] +<t_Y_6,15>[B] <= 1;
[linear] <I7>: 0 <= <t_Y_7>[B] +<t_Y_3,7>[B] +<t_Y_6,7>[B] +<t_Y_7,8>[B] +<t_Y_7,9>[B] <= 1;
[linear] <I8>: 0 <= <t_Y_8>[B] +<t_Y_4,8>[B] +<t_Y_7,8>[B] +<t_Y_8,11>[B] <= 1;
[linear] <I9>: 0 <= <t_Y_9>[B] +<t_Y_4,9>[B] +<t_Y_6,9>[B] +<t_Y_7,9>[B] +<t_Y_9,10>[B] <= 1;
[linear] <I10>: 0 <= <t_Y_10>[B] +<t_Y_1,10>[B] +<t_Y_3,10>[B] +<t_Y_5,10>[B] +<t_Y_6,10>[B] +<t_Y_9,10>[B] <= 1;
[linear] <I11>: 0 <= <t_Y_11>[B] +<t_Y_8,11>[B] +<t_Y_11,14>[B] +<t_Y_11,16>[B] <= 1;
[linear] <I12>: 0 <= <t_Y_12>[B] +<t_Y_12,13>[B] +<t_Y_12,15>[B] +<t_Y_12,16>[B] <= 1;
[linear] <I13>: 0 <= <t_Y_13>[B] +<t_Y_4,13>[B] +<t_Y_12,13>[B] +<t_Y_13,17>[B] +<t_Y_13,18>[B] +<t_Y_13,19>[B] <= 1;
[linear] <I14>: 0 <= <t_Y_14>[B] +<t_Y_5,14>[B] +<t_Y_11,14>[B] +<t_Y_14,16>[B] <= 1;
[linear] <I15>: 0 <= <t_Y_15>[B] +<t_Y_6,15>[B] +<t_Y_12,15>[B] +<t_Y_15,20>[B] <= 1;
[linear] <I16>: 0 <= <t_Y_16>[B] +<t_Y_11,16>[B] +<t_Y_12,16>[B] +<t_Y_14,16>[B] +<t_Y_16,19>[B] +<t_Y_16,20>[B] <= 1;
[linear] <I17>: 0 <= <t_Y_17>[B] +<t_Y_13,17>[B] <= 1;
[linear] <I18>: 0 <= <t_Y_18>[B] +<t_Y_13,18>[B] <= 1;
[linear] <I19>: 0 <= <t_Y_19>[B] +<t_Y_13,19>[B] +<t_Y_16,19>[B] <= 1;
[linear] <I20>: 0 <= <t_Y_20>[B] +<t_Y_15,20>[B] +<t_Y_16,20>[B] <= 1;
END
PRICERINIT
presolving:
clique table cleanup detected 0 bound changes
presolved problem has 80 active (8%) nonzeros and 80 (8%) check nonzeros
presolving (0 rounds: 0 fast, 0 medium, 0 exhaustive):
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 50 variables (50 bin, 0 int, 0 impl, 0 cont) and 20 constraints
20 constraints of type <linear>
Presolving Time: 0.00
time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
* 0.0s| 1 | 0 | 4 | - | 780k| 0 | 0 | 50 | 20 | 50 | 20 | 0 | 0 | 0 | -- |-2.400000e+01 | Inf
PRICERREDCOST. 1 times.
Current Depth:0
Current Depth:0
Dual solution: -10.000000
**** PRICER HEURISTIC *****
Variable Y_3,4,5,6,7,8,9,10,12,14,15,20(cs = -102.000000)
**** Nindividuals=12
Number of added vars=1
we add variable (1) for the 1-th solution.
H: Subproblem solution: cs = -102.000000; pix = -8.000000<<<<<<<<<<<<<<<<<
**** PRICER HEURISTIC *****
Variable Y_13,16,17,19(cs = -12.000000)
**** Nindividuals=4
Number of added vars=2
we add variable (2) for the 2-th solution.
H: Subproblem solution: cs = -12.000000; pix = -2.000000<<<<<<<<<<<<<<<<<
0.0s| 1 | 0 | 9 | - | 786k| 0 | 0 | 52 | 20 | 52 | 20 | 0 | 0 | 0 | -- |-2.400000e+01 | Inf
PRICERREDCOST. 2 times.
Current Depth:0
Current Depth:0
Dual solution: -24.000000
**** PRICER HEURISTIC *****
Variable Y_3,4,5,6,7,8,9,10,12,14,15,20(cs = -102.000000)
**** Nindividuals=12
Number of added vars=1
we add variable (3) for the 1-th solution.
H: Subproblem solution: cs = -102.000000; pix = -14.000000<<<<<<<<<<<<<<<<<
0.0s| 1 | 0 | 10 | - | 786k| 0 | 0 | 53 | 20 | 53 | 20 | 0 | 0 | 0 | -- |-2.400000e+01 | Inf
PRICERREDCOST. 3 times.
Current Depth:0
Current Depth:0
Dual solution: -112.000000
**** PRICER HEURISTIC *****
Variable Y_3,4,5,6,7,8,9,10,12,14,15(cs = -74.000000)
**** Nindividuals=11
Number of added vars=1
we add variable (4) for the 1-th solution.
H: Subproblem solution: cs = -74.000000; pix = -14.000000<<<<<<<<<<<<<<<<<
0.0s| 1 | 0 | 11 | - | 786k| 0 | 0 | 54 | 20 | 54 | 20 | 0 | 0 | 0 | -- |-2.400000e+01 | Inf
PRICERREDCOST. 4 times.
Current Depth:0
Current Depth:0
Dual solution: -112.000000
**** PRICER HEURISTIC *****
Variable Y_3,4,5,6,7,8,9,10,14(cs = -56.000000)
**** Nindividuals=9
Number of added vars=1
we add variable (5) for the 1-th solution.
H: Subproblem solution: cs = -56.000000; pix = -10.000000<<<<<<<<<<<<<<<<<
0.0s| 1 | 0 | 12 | - | 792k| 0 | 0 | 55 | 20 | 55 | 20 | 0 | 0 | 0 | -- |-2.400000e+01 | Inf
PRICERREDCOST. 5 times.
Current Depth:0
Current Depth:0
Dual solution: -112.000000
**** PRICER HEURISTIC *****
Variable Y_3,4,5,6,8,9,10(cs = -46.000000)
**** Nindividuals=7
Number of added vars=1
we add variable (6) for the 1-th solution.
H: Subproblem solution: cs = -46.000000; pix = -10.000000<<<<<<<<<<<<<<<<<
0.0s| 1 | 0 | 13 | - | 792k| 0 | 0 | 56 | 20 | 56 | 20 | 0 | 0 | 0 | -- |-2.400000e+01 | Inf
PRICERREDCOST. 6 times.
Current Depth:0
Current Depth:0
Dual solution: -112.000000
**** PRICER HEURISTIC *****
Variable Y_4,6,8,9(cs = -20.000000)
**** Nindividuals=4
Number of added vars=1
we add variable (7) for the 1-th solution.
H: Subproblem solution: cs = -20.000000; pix = -6.000000<<<<<<<<<<<<<<<<<
0.0s| 1 | 0 | 14 | - | 792k| 0 | 0 | 57 | 20 | 57 | 20 | 0 | 0 | 0 | -- |-2.400000e+01 | Inf
PRICERREDCOST. 7 times.
Current Depth:0
Current Depth:0
Dual solution: -112.000000
Current Depth:0
SCIPsolve(subscip) has taken 1.098639 seconds
nsols: 8
**** PRICER EXACT *****
Variable Y_3,4,5,6,7,8,11,12,14,15(cs = -48.000000)
**** Nindividuals=10
Number of added vars=1
we add variable (8) for the 1-th solution.
E: Subproblem solution: cs = -48.000000; pix = -32.000000<<<<<<<<<<<<<<<<<
**** PRICER EXACT *****
Variable Y_3,4,5,6,7,8,11,12,14,15,20(cs = -62.000000)
**** Nindividuals=11
Number of added vars=2
we add variable (9) for the 2-th solution.
E: Subproblem solution: cs = -62.000000; pix = -60.000000<<<<<<<<<<<<<<<<<
1.1s| 1 | 0 | 16 | - | 800k| 0 | 0 | 59 | 20 | 59 | 20 | 0 | 0 | 0 | -- |-2.400000e+01 | Inf
PRICERREDCOST. 8 times.
Current Depth:0
Current Depth:0
Dual solution: -112.000000
**** PRICER HEURISTIC *****
Variable Y_4,8,9(cs = -10.000000)
**** Nindividuals=3
Number of added vars=1
we add variable (10) for the 1-th solution.
H: Subproblem solution: cs = -10.000000; pix = -6.000000<<<<<<<<<<<<<<<<<
1.1s| 1 | 0 | 17 | - | 800k| 0 | 0 | 60 | 20 | 60 | 20 | 0 | 0 | 0 | -- |-2.400000e+01 | Inf
PRICERREDCOST. 9 times.
Current Depth:0
Current Depth:0
Dual solution: -112.000000
Current Depth:0
SCIPsolve(subscip) has taken 1.241726 seconds
nsols: 4
**** PRICER EXACT *****
Variable Y_3,4,5,9,10,13,17,19(cs = -44.000000)
**** Nindividuals=8
Number of added vars=1
we add variable (11) for the 1-th solution.
E: Subproblem solution: cs = -44.000000; pix = -36.000000<<<<<<<<<<<<<<<<<
2.3s| 1 | 0 | 19 | - | 802k| 0 | 0 | 61 | 20 | 61 | 20 | 0 | 0 | 0 | -- |-2.400000e+01 | Inf
PRICERREDCOST. 10 times.
Current Depth:0
Current Depth:0
Dual solution: -114.000000
Current Depth:0
SCIPsolve(subscip) has taken 1.412581 seconds
nsols: 9
**** PRICER EXACT *****
Variable Y_2,3,4,5,7,9,12,13,14,16,17,20(cs = -42.000000)
**** Nindividuals=12
Number of added vars=1
we add variable (12) for the 1-th solution.
E: Subproblem solution: cs = -42.000000; pix = -28.000000<<<<<<<<<<<<<<<<<
3.7s| 1 | 0 | 22 | - | 802k| 0 | 0 | 62 | 20 | 62 | 20 | 0 | 0 | 0 | -- |-2.400000e+01 | Inf
PRICERREDCOST. 11 times.
Current Depth:0
Current Depth:0
Dual solution: -114.000000
Current Depth:0
SCIPsolve(subscip) has taken 1.602032 seconds
nsols: 13
**** PRICER EXACT *****
Variable Y_4,7,9,12,13,14,16,17(cs = -18.000000)
**** Nindividuals=8
Number of added vars=1
we add variable (13) for the 1-th solution.
E: Subproblem solution: cs = -18.000000; pix = -10.000000<<<<<<<<<<<<<<<<<
**** PRICER EXACT *****
Variable Y_4,9,13,16,17,19(cs = -18.000000)
**** Nindividuals=6
Number of added vars=2
we add variable (14) for the 2-th solution.
E: Subproblem solution: cs = -18.000000; pix = -14.000000<<<<<<<<<<<<<<<<<
**** PRICER EXACT *****
Variable Y_3,4,5,9,10,13,17(cs = -34.000000)
**** Nindividuals=7
Number of added vars=3
we add variable (15) for the 3-th solution.
E: Subproblem solution: cs = -34.000000; pix = -32.000000<<<<<<<<<<<<<<<<<
**** PRICER EXACT *****
Variable Y_3,4,5,7,8,9,11,14(cs = -22.000000)
**** Nindividuals=8
Number of added vars=4
we add variable (16) for the 4-th solution.
E: Subproblem solution: cs = -22.000000; pix = -21.000000<<<<<<<<<<<<<<<<<
**** PRICER EXACT *****
Variable Y_4,5,7,9,12,13,14,16,17,20(cs = -38.000000)
**** Nindividuals=10
Number of added vars=5
we add variable (17) for the 5-th solution.
E: Subproblem solution: cs = -38.000000; pix = -37.000000<<<<<<<<<<<<<<<<<
5.2s| 1 | 0 | 25 | - | 827k| 0 | 0 | 67 | 20 | 29 | 20 | 0 | 0 | 0 | -- |-2.400000e+01 | Inf
5.2s| 1 | 0 | 25 | - | 827k| 0 | 0 | 67 | 20 | 40 | 20 | 0 | 0 | 0 | -- |-2.400000e+01 | Inf
PRICERREDCOST. 12 times.
Current Depth:0
Current Depth:0
Dual solution: -112.000000
Current Depth:0
SCIPsolve(subscip) has taken 1.155086 seconds
nsols: 7
**** PRICER EXACT *****
Variable Y_3,4,6,7,8(cs = -16.000000)
**** Nindividuals=5
Number of added vars=1
we add variable (18) for the 1-th solution.
E: Subproblem solution: cs = -16.000000; pix = -13.000000<<<<<<<<<<<<<<<<<
6.4s| 1 | 0 | 27 | - | 827k| 0 | 0 | 68 | 20 | 41 | 20 | 0 | 0 | 0 | -- |-2.400000e+01 | Inf
PRICERREDCOST. 13 times.
Current Depth:0
Current Depth:0
Dual solution: -113.000000
Current Depth:0
SCIPsolve(subscip) has taken 1.467528 seconds
nsols: 13
**** PRICER EXACT *****
Variable Y_3,4,5,8,9,10,13,17(cs = -40.000000)
**** Nindividuals=8
Number of added vars=1
we add variable (19) for the 1-th solution.
E: Subproblem solution: cs = -40.000000; pix = -38.000000<<<<<<<<<<<<<<<<<
**** PRICER EXACT *****
Variable Y_3,4,6,7,8,9(cs = -24.000000)
**** Nindividuals=6
Number of added vars=2
we add variable (20) for the 2-th solution.
E: Subproblem solution: cs = -24.000000; pix = -23.000000<<<<<<<<<<<<<<<<<
7.8s| 1 | 0 | 28 | - | 827k| 0 | 0 | 70 | 20 | 43 | 20 | 0 | 0 | 0 | -- |-2.400000e+01 | Inf
PRICERREDCOST. 14 times.
Current Depth:0
Current Depth:0
Dual solution: -112.000000
Current Depth:0
SCIPsolve(subscip) has taken 1.236845 seconds
nsols: 7
**** PRICER EXACT *****
Variable Y_13,16,18,19(cs = -12.000000)
**** Nindividuals=4
Number of added vars=1
we add variable (21) for the 1-th solution.
E: Subproblem solution: cs = -12.000000; pix = -10.000000<<<<<<<<<<<<<<<<<
time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
9.0s| 1 | 0 | 29 | - | 827k| 0 | 0 | 71 | 20 | 44 | 20 | 0 | 0 | 0 | -- |-2.400000e+01 | Inf
PRICERREDCOST. 15 times.
Current Depth:0
Current Depth:0
Dual solution: -114.000000
Current Depth:0
SCIPsolve(subscip) has taken 1.471991 seconds
nsols: 11
10.4s| 1 | 0 | 29 | - | 827k| 0 | 0 | 71 | 20 | 44 | 20 | 0 | 0 | 0 |-1.140000e+02 |-2.400000e+01 | 375.00%
*10.4s| 1 | 0 | 29 | - | 836k| 0 | 0 | 71 | 20 | 44 | 20 | 0 | 0 | 0 |-1.140000e+02 |-1.140000e+02 | 0.00%
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 10.43
Solving Nodes : 1
Primal Bound : -1.14000000000000e+02 (2 solutions)
Dual Bound : -1.14000000000000e+02
Gap : 0.00 %
objective value: -114
Y_3,4,5,6,7,8,9,10,12,14,15,20 1 (obj:-102)
Y_13,16,18,19 1 (obj:-12)
SCIPsolve has taken 10.764516 seconds
PROBDELTRANS
PROBDELORIG
More information about the Scip
mailing list