[Scip] Added Variables missing in problem / solution
Jan Berling
berlingjan at gmail.com
Wed Feb 11 19:24:07 CET 2015
Dear Gerald,
following your comments, we changed our code, so that only some initial
variables are created & added at the beginning. In the pricing process,
variables with reduced cost are created and added to the problem. In this
way, all created and added variables appear in the solution SCIPprintSol().
The pricing process is now running fine.
Before the change of the pricing implementation, the objective
SCIPgetSolOrigObj(scip,
scipSol) did worsen in some iterations. Now the total objective improves in
every iteration. However, in some iterations the sum of the objective
values of the solution variables is smaller than the total objective. This
iterations have a relaxed solution, with the solution status "LP was solved
to optimality".
SCIP_VAR** pricerSolVars = SCIPgetVars(scip);
SCIP_Real pricerSolSum = 0;
for(int vi=0; vi<SCIPgetNVars(scip); vi++){
pricerSolSum += SCIPvarGetLPSol(pricerSolVars[vi]) *
SCIPvarGetObj(pricerSolVars[vi]);
}
My guess is, that SCIPgetSolOrigObj() always refers to the best overall
objective of the solution, wheras
SCIPvarGetLPSol() gets the solution value of the current relaxation. Is
there any way to get the relaxed objective directly? As far as I could see,
SCIPgetSolTransObj() always returns the same value as the original
objective.
At the end, the solution is optimal. We're just using binary variables in
settppc and knapsack constraints with a linear cost function. The log
shows, that a scip-supplied branching rule is used. I have disabled the
heuristic "shiftandpropagate", because it increases the solution time 10x.
How much could be gained from implementing a problem specific branching
rule? If have supplied some log information. Unfortunately, it wasn't
possible to print the SCIPprintDisplayLine(), probably because of the
Matlab-Mex message handler.
All the best & thanks one more time,
Jan
2015-02-06 11:59 GMT+01:00 Gerald Gamrath <gamrath at zib.de>:
> Dear Jan,
>
> sorry for the delayed reply. See my comments below.
>
>
>> My scheduling problem has one set partitioning constraint for every
>> vehicle and binary variables for every possible start-timeslot. All
>> variables are created at the beginning, but only two variables for every
>> vehicle/setppc-constraint are added to the problem and their constraints
>> right away. At the end, the solution must have one binary variable set to
>> one for every vehicle/setppc-constraint.
>>
>> In the pricing process, the reduced cost of the other variables (start
>> slots) are calculated and added to the problem with SCIPaddPricedVar() and
>> added to the transformed constraints afterwards. In the iteration process,
>> more and more variables are added to the problem. But sometimes the
>> objective value is rising slightly, which is odd because added variables
>> enlarge the solution space which should lead to a decreasing objective
>> value.
>>
> What do you mean with objective value? The optimum of the LP? By which
> amount (absolute and relative) does the objective change? Really small
> changes could just be caused by numerics.
>
>
> Unfortunately, some variables don't appear in the solution SCIPprintSol()
>> but in the solution SCIPprintTransSol(). Unsurprisingly, these are all
>> priced variables. The objective value of both solution-files are the same,
>> though. But if the objective value is calculated by all solution variables
>> (SCIPvarGetLPSol(vars(f,d)) == 1) and their objective function values
>> (SCIPvarGetObj(vars(f,d)), the result is a little bit lower than the
>> printed solution-objective-function-values.
>>
> Yes, since the priced variables have no equivalent in the original space,
> they are left out when printing an original solution. The objective,
> however, is the one of the transformed solution, so solution and objective
> do not necessarily fit together (on the other hand, printing a wrong
> objective value would be bad as well). So you need to get the transformed
> solution when you do branch-and-price. In most of the cases when doing
> branch-and-price, you even write your own solution printing method, since
> you rather want to write down the "meaning" of the variables instead of the
> names.
> Your case is very special, because you create all variables in the
> beginning, but since they are not added to the original problem, they
> cannot be printed in the original solution.
>
>
>> To summarize the matter, there is a serious problem in connection with
>> the pricing problem and the transformed problem.
>>
>> - Could the error stem from the fact that the variables are added from
>> pricerdata to the problem?
>>
> No, this should be ok.
>
> - Is it necessary to add the priced variables to the original problem,
>> too?
>>
> No, this is not possible, since the original problem cannot be changed
> during the solving process.
>
> - Is there some presolving/branch&bound/relaxation going on, which
>> interferes with the pricing?
>>
> If you marked your constraints to be modifiable, no presolving should
> interfere. Branch-and-bound is of course happening when the root LP was
> finally solved, and you should implement your problem-specific branching
> rule when doing branch-and-price.
>
> - Could numerical inconsistencies lead to such behaviour?
>>
> Yes, at least to small changes in the objective.
>
>
> If you send me your log file including statistics, I can have a look to
> check for problems.
>
> Best,
> Gerald
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20150211/5d6f22a1/attachment.html>
-------------- next part --------------
SCIP Status : problem is solved [optimal solution found]
Total Time : 28.77
solving : 28.77
presolving : 1.62 (included in solving)
reading : 0.00
copying : 0.65 (1 #copies) (minimal 0.65, maximal 0.65, average 0.65)
Original Problem :
Problem name : ATFM Problem
Variables : 53506 (53506 binary, 0 integer, 0 implicit integer, 0 continuous)
Constraints : 308254 initial, 308254 maximal
Objective sense : minimize
Presolved Problem :
Problem name : t_ATFM Problem
Variables : 93271 (93271 binary, 0 integer, 0 implicit integer, 0 continuous)
Constraints : 308254 initial, 308254 maximal
Presolvers : ExecTime SetupTime Calls FixedVars AggrVars ChgTypes ChgBounds AddHoles DelCons AddCons ChgSides ChgCoefs
boundshift : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
components : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
convertinttobin : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
domcol : 0.11 0.00 1 0 0 0 0 0 0 0 0 0
dualfix : 0.00 0.00 2 0 0 0 0 0 0 0 0 0
gateextraction : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
implics : 0.00 0.00 2 0 0 0 0 0 0 0 0 0
inttobinary : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
trivial : 0.00 0.00 2 0 0 0 0 0 0 0 0 0
genvbounds : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
probing : 1.02 0.00 1 0 0 0 0 0 0 0 0 0
pseudoobj : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
knapsack : 0.32 0.00 2 1039 0 0 0 0 0 0 0 0
setppc : 0.04 0.00 2 0 0 0 0 0 0 0 0 0
root node : - - - 40734 - - 40734 - - - - -
Constraints : Number MaxNumber #Separate #Propagate #EnfoLP #EnfoPS #Check #ResProp Cutoffs DomReds Cuts Applied Conss Children
integral : 0 0 0 0 2 0 26 0 0 0 0 0 0 4
knapsack : 282266 282266 0 108 0 0 25 0 0 15184 0 0 0 0
setppc : 25988 25988 0 108 0 0 24 0 0 712 0 0 0 0
countsols : 0 0 0 0 0 0 23 0 0 0 0 0 0 0
Constraint Timings : TotalTime SetupTime Separate Propagate EnfoLP EnfoPS Check ResProp
integral : 7.47 0.00 0.00 0.00 7.43 0.00 0.04 0.00
knapsack : 1.80 0.00 0.22 0.75 0.00 0.00 0.83 0.00
setppc : 0.20 0.00 0.03 0.07 0.00 0.00 0.10 0.00
countsols : 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
Propagators : #Propagate #ResProp Cutoffs DomReds
genvbounds : 0 0 0 0
obbt : 0 0 0 0
probing : 0 0 0 0
pseudoobj : 0 0 0 0
redcost : 5 0 0 32780
rootredcost : 1 0 0 0
vbounds : 10 0 0 0
Propagator Timings : TotalTime SetupTime Presolve Propagate ResProp
genvbounds : 0.00 0.00 0.00 0.00 0.00
obbt : 0.00 0.00 0.00 0.00 0.00
probing : 1.02 0.00 1.02 0.00 0.00
pseudoobj : 0.00 0.00 0.00 0.00 0.00
redcost : 0.08 0.00 0.00 0.08 0.00
rootredcost : 0.03 0.00 0.00 0.03 0.00
vbounds : 0.02 0.00 0.00 0.02 0.00
Conflict Analysis : Time Calls Success Conflicts Literals Reconvs ReconvLits LP Iters
propagation : 0.00 0 0 0 0.0 0 0.0 -
infeasible LP : 0.00 0 0 0 0.0 0 0.0 0
bound exceed. LP : 0.00 0 0 0 0.0 0 0.0 0
strong branching : 0.00 0 0 0 0.0 0 0.0 0
pseudo solution : 0.00 0 0 0 0.0 0 0.0 -
applied globally : - - - 0 0.0 - - -
applied locally : - - - 0 0.0 - - -
Separators : ExecTime SetupTime Calls Cutoffs DomReds Cuts Applied Conss
cut pool : 0.00 0 - - 0 - - (maximal pool size: 0)
cgmip : 0.00 0.00 0 0 0 0 0 0
clique : 0.00 0.00 0 0 0 0 0 0
closecuts : 0.00 0.00 0 0 0 0 0 0
cmir : 0.00 0.00 0 0 0 0 0 0
flowcover : 0.00 0.00 0 0 0 0 0 0
gomory : 0.00 0.00 0 0 0 0 0 0
impliedbounds : 0.00 0.00 0 0 0 0 0 0
intobj : 0.00 0.00 0 0 0 0 0 0
mcf : 0.00 0.00 0 0 0 0 0 0
oddcycle : 0.00 0.00 0 0 0 0 0 0
rapidlearning : 0.00 0.00 0 0 0 0 0 0
strongcg : 0.00 0.00 0 0 0 0 0 0
zerohalf : 0.00 0.00 0 0 0 0 0 0
Pricers : ExecTime SetupTime Calls Vars
problem variables: 0.15 - 23 24372
Atfm : 3.58 0.02 13 40804
Branching Rules : ExecTime SetupTime BranchLP BranchExt BranchPS Cutoffs DomReds Cuts Conss Children
allfullstrong : 0.00 0.00 0 0 0 0 0 0 0 0
fullstrong : 0.00 0.00 0 0 0 0 0 0 0 0
inference : 0.00 0.00 0 0 0 0 0 0 0 0
leastinf : 0.00 0.00 0 0 0 0 0 0 0 0
mostinf : 0.00 0.00 0 0 0 0 0 0 0 0
pscost : 0.00 0.00 0 0 0 0 0 0 0 0
random : 0.00 0.00 0 0 0 0 0 0 0 0
relpscost : 7.43 0.00 2 0 0 0 0 0 0 4
Primal Heuristics : ExecTime SetupTime Calls Found
LP solutions : 0.00 - - 0
pseudo solutions : 0.00 - - 0
actconsdiving : 0.00 0.00 0 0
clique : 0.00 0.00 0 0
coefdiving : 0.00 0.00 0 0
crossover : 0.00 0.00 0 0
dins : 0.00 0.00 0 0
feaspump : 2.45 0.00 1 0
fixandinfer : 0.00 0.00 0 0
fracdiving : 0.00 0.00 0 0
guideddiving : 0.00 0.00 0 0
intdiving : 0.00 0.00 0 0
intshifting : 0.00 0.00 0 0
linesearchdiving : 0.00 0.00 0 0
localbranching : 0.00 0.00 0 0
mutation : 0.00 0.00 0 0
nlpdiving : 0.00 0.00 0 0
objpscostdiving : 0.00 0.00 0 0
octane : 0.00 0.00 0 0
oneopt : 0.15 0.00 2 0
pscostdiving : 0.00 0.00 0 0
rens : 2.68 0.00 1 0
rins : 0.00 0.00 0 0
rootsoldiving : 0.00 0.00 0 0
rounding : 0.13 0.00 3 1
shiftandpropagate: 0.00 0.00 0 0
shifting : 0.03 0.00 2 0
simplerounding : 0.34 0.00 16 7
subnlp : 0.00 0.00 0 0
trivial : 0.10 0.00 2 0
trysol : 0.00 0.00 0 0
twoopt : 0.00 0.00 0 0
undercover : 0.00 0.00 0 0
vbounds : 0.00 0.00 0 0
veclendiving : 0.00 0.00 0 0
zeroobj : 0.00 0.00 0 0
zirounding : 0.04 0.00 0 0
LP : Time Calls Iterations Iter/call Iter/sec Time-0-It Calls-0-It
primal LP : 5.69 13 2840 315.56 499.12 0.50 4
dual LP : 2.19 12 2341 468.20 1068.95 0.75 7
lex dual LP : 0.00 0 0 0.00 -
barrier LP : 0.00 0 0 0.00 - 0.00 0
diving/probing LP: 1.43 7 822 117.43 574.83
strong branching : 7.43 23 62 2.70 8.34
(at root node) : - 8 24 3.00 -
conflict analysis: 0.00 0 0 0.00 -
B&B Tree :
number of runs : 1
nodes : 5
nodes (total) : 5
nodes left : 0
max depth : 2
max depth (total): 2
backtracks : 2 (40.0%)
delayed cutoffs : 0
repropagations : 0 (0 domain reductions, 0 cutoffs)
avg switch length: 2.40
switching time : 0.04
Solution :
Solutions found : 9 (9 improvements)
First Solution : +6.11925000000000e+005 (in run 1, after 1 nodes, 3.48 seconds, depth 0, found by <relaxation>)
Primal Bound : +5.20155000000000e+005 (in run 1, after 1 nodes, 11.75 seconds, depth 0, found by <rounding>)
Dual Bound : +5.20155000000000e+005
Gap : 0.00 %
Root Dual Bound : +5.20147500000000e+005
Root Iterations : 5998
-------------- next part --------------
A non-text attachment was scrubbed...
Name: finalBranchingStats.log
Type: application/octet-stream
Size: 10222 bytes
Desc: not available
URL: <http://listserv.zib.de/pipermail/scip/attachments/20150211/5d6f22a1/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: finalWorkspace.log
Type: application/octet-stream
Size: 6838 bytes
Desc: not available
URL: <http://listserv.zib.de/pipermail/scip/attachments/20150211/5d6f22a1/attachment-0001.obj>
More information about the Scip
mailing list