[Scip] Problem with using non linear constraint handler
Ahmad Moradi
ahmad.moradi at gmail.com
Tue Dec 11 13:45:25 MET 2012
Dear all,
I have a network design problem with nonlinear objective function and
linear constraints. Let x_e be some variable defined on edge e, then the
objective function looks like \sum_e f(x_e) where f is a concave
function. I added the objective function as a nonlinear constraint, 0 =< z
- \sum_e f(x_e) <= +inf to SCIP through the following code in which I
considered f = SQRT(x_e)
----------------------------------------------------------------------------------------------------
SCIP_CONS* zcon;
char zcon_name[255];
SCIPsnprintf(zcon_name, 255, "z_constraint");
SCIP_Real coef;
coef = 1.0;
SCIP_CALL( SCIPcreateConsNonlinear( scip, &zcon, zcon_name, 1, &z,
&coef, 0, NULL, NULL, 0.0, SCIPinfinity(scip),
TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
coef = -1.0;
for ( int i = 0; i < g.num_edges; i++) {
SCIP_EXPR* varexpr;
SCIP_EXPR* expr;
SCIP_EXPRTREE* exprtree;
SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &varexpr, SCIP_EXPR_VARIDX, 0)
);
(*) SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr, SCIP_EXPR_SQRT,
varexpr) );
SCIP_CALL( SCIPexprtreeCreate(SCIPblkmem(scip), &exprtree, expr, 1, 0,
NULL) );
SCIP_CALL( SCIPexprtreeSetVars(exprtree, 1, &(g.fwd_arc_var[i]) ) );
SCIP_CALL( SCIPaddExprtreesNonlinear(scip, zcon, 1, &exprtree , &coef) );
SCIP_CALL( SCIPexprtreeFree(&exprtree) );
}
SCIP_CALL_EXC( SCIPaddCons(scip, zcon) );
SCIP_CALL_EXC( SCIPreleaseCons(scip, &zcon) );
----------------------------------------------------------------------------------------------------------
However, After running the code, SCIP's optimal solution violates the
z_constraint and I could not figure out why? The same probles happend while
using
SCIP_CALL( SCIPexprCreate(SCIPblkmem(scip), &expr,
SCIP_EXPR_REALPOWER, varexpr, 0.5) );
instead of (*). Other than that I noticed, SCIP will write the z_constraint
while using SCIPprintOrigProblem() and omit it while using
SCIPprintTransProblem(). I am confusing whether the constraint is deleted
by presolving or not?
Bests,
Ahmad
PS: I have already attached the log file to this email and an instance of
the problem in .cip format
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20121211/24267732/attachment.html
-------------- next part --------------
presolving:
(round 1) 0 del vars, 0 del conss, 0 add conss, 48 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(0.0s) probing: 51/144 (35.4%) - 0 fixings, 0 aggregations, 0 implications, 0 bound changes
(0.0s) probing aborted: 50/50 successive totally useless probings
presolving (2 rounds):
0 deleted vars, 0 deleted constraints, 0 added constraints, 48 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
0 implications, 0 cliques
presolved problem has 199 variables (144 bin, 0 int, 0 impl, 55 cont) and 115 constraints
114 constraints of type <linear>
1 constraints of type <nonlinear>
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
y 0.0s| 1 | 0 | 13 | - | 696k| 0 | - | 199 | 115 | 199 | 114 | 0 | 0 | 0 | -- | 1.121583e+01 | Inf
0.0s| 1 | 0 | 71 | - | 696k| 0 | 0 | 199 | 115 | 199 | 114 | 0 | 0 | 0 | 0.000000e+00 | 1.121583e+01 | Inf
0.0s| 1 | 0 | 237 | - | 696k| 0 | 28 | 199 | 115 | 199 | 115 | 1 | 0 | 0 | 3.031431e+00 | 1.121583e+01 | 269.98%
0.0s| 1 | 0 | 256 | - | 727k| 0 | 0 | 199 | 115 | 199 | 122 | 8 | 0 | 0 | 3.833868e+00 | 1.121583e+01 | 192.55%
0.0s| 1 | 0 | 256 | - | 727k| 0 | 0 | 199 | 115 | 199 | 122 | 8 | 0 | 0 | 3.833868e+00 | 1.121583e+01 | 192.55%
0.0s| 1 | 2 | 256 | - | 727k| 0 | 0 | 199 | 115 | 199 | 122 | 8 | 0 | 0 | 3.833868e+00 | 1.121583e+01 | 192.55%
* 0.0s| 3 | 0 | 257 | 7.0 | 733k| 2 | - | 199 | 115 | 199 | 121 | 9 | 0 | 0 | 3.833868e+00 | 3.833868e+00 | 0.00%
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 0.02
Solving Nodes : 3
Primal Bound : +3.83386822719347e+00 (2 solutions)
Dual Bound : +3.83386822719347e+00
Gap : 0.00 %
objective value: 3.83386822719347
Y_0_1_0_1 1 (obj:0)
Y_0_1_2_1 1 (obj:0)
Y_0_1_3_1 1 (obj:0)
Y_0_2_0_2 1 (obj:0)
Y_0_2_1_2 1 (obj:0)
Y_0_2_3_2 1 (obj:0)
Y_0_3_0_3 1 (obj:0)
Y_0_3_1_3 1 (obj:0)
Y_0_3_2_3 1 (obj:0)
Y_1_0_1_0 1 (obj:0)
Y_1_0_1_2 1 (obj:0)
Y_1_0_1_3 1 (obj:0)
Y_2_0_2_0 1 (obj:0)
Y_2_0_2_1 1 (obj:0)
Y_2_0_2_3 1 (obj:0)
Y_3_0_3_0 1 (obj:0)
Y_3_0_3_1 1 (obj:0)
Y_3_0_3_2 1 (obj:0)
Wp_0_3_3 1 (obj:0)
Wm_0_3_3 1 (obj:0)
Wp_0_2_2 1 (obj:0)
Wm_0_2_2 1 (obj:0)
Wp_0_1_1 1 (obj:0)
Wm_0_1_1 1 (obj:0)
X_0_1 11 (obj:0)
X_0_2 21 (obj:0)
X_0_3 11 (obj:0)
zvar 3.83386822719347 (obj:1)
SCIP Status : problem is solved [optimal solution found]
Total Time : 0.02
solving : 0.02
presolving : 0.01 (included in solving)
reading : 0.00
copying : 0.00 (0 times copied the problem)
Original Problem :
Problem name : rnd
Variables : 199 (144 binary, 0 integer, 0 implicit integer, 55 continuous)
Constraints : 115 initial, 115 maximal
Objective sense : minimize
Presolved Problem :
Problem name : t_rnd
Variables : 199 (144 binary, 0 integer, 0 implicit integer, 55 continuous)
Constraints : 115 initial, 115 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.01 0.00 1 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.00 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 : 0.00 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
linear : 0.00 0.00 1 0 0 0 48 0 0 0 0 0
nonlinear : 0.00 0.00 1 0 0 0 0 0 0 0 0 0
root node : - - - 0 - - 8 - - - - -
Constraints : Number MaxNumber #Separate #Propagate #EnfoLP #EnfoPS #Check #ResProp Cutoffs DomReds Cuts Applied Conss Children
integral : 0 0 0 0 3 0 9 0 0 0 0 0 0 0
linear : 114 114 0 238 3 0 8 0 0 4 0 0 0 0
nonlinear : 1 1 7 4 3 0 4 0 0 6 2 2 0 0
countsols : 0 0 0 0 3 0 2 0 0 0 0 0 0 0
Constraint Timings : TotalTime SetupTime Separate Propagate EnfoLP EnfoPS Check ResProp
integral : 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
linear : 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
nonlinear : 0.00 0.00 0.00 0.00 0.00 0.00 0.00 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 : 10 0 0 2
redcost : 7 0 0 0
rootredcost : 1 0 0 0
vbounds : 0 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 : 0.00 0.00 0.00 0.00 0.00
pseudoobj : 0.00 0.00 0.00 0.00 0.00
redcost : 0.00 0.00 0.00 0.00 0.00
rootredcost : 0.00 0.00 0.00 0.00 0.00
vbounds : 0.00 0.00 0.00 0.00 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 2 - - 0 - - (maximal pool size: 23)
cgmip : 0.00 0.00 0 0 0 0 0 0
clique : 0.00 0.00 1 0 0 0 0 0
closecuts : 0.00 0.00 0 0 0 0 0 0
cmir : 0.00 0.00 1 0 0 0 0 0
flowcover : 0.00 0.00 1 0 0 0 0 0
gomory : 0.00 0.00 1 0 0 28 7 0
impliedbounds : 0.00 0.00 1 0 0 0 0 0
intobj : 0.00 0.00 0 0 0 0 0 0
mcf : 0.00 0.00 1 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 1 0 0 0 0 0
zerohalf : 0.00 0.00 0 0 0 0 0 0
Pricers : ExecTime SetupTime Calls Vars
problem variables: 0.00 - 0 0
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 2 0 0 0 0 0 4
random : 0.00 0.00 0 0 0 0 0 0 0 0
relpscost : 0.00 0.00 0 0 0 0 0 0 0 0
Primal Heuristics : ExecTime SetupTime Calls Found
LP solutions : 0.00 - - 1
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 : 0.00 0.00 0 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.00 0.00 1 0
pscostdiving : 0.00 0.00 0 0
rens : 0.00 0.00 0 0
rins : 0.00 0.00 0 0
rootsoldiving : 0.00 0.00 0 0
rounding : 0.00 0.00 1 0
shiftandpropagate: 0.00 0.00 1 0
shifting : 0.00 0.00 1 0
simplerounding : 0.00 0.00 0 0
subnlp : 0.00 0.00 0 0
trivial : 0.00 0.00 2 0
trysol : 0.00 0.00 1 1
twoopt : 0.00 0.00 0 0
undercover : 0.00 0.00 1 0
vbounds : 0.00 0.00 0 0
veclendiving : 0.00 0.00 0 0
zeroobj : 0.00 0.00 0 0
zirounding : 0.00 0.00 0 0
LP : Time Calls Iterations Iter/call Iter/sec Time-0-It Calls-0-It
primal LP : 0.00 1 0 0.00 - 0.00 1
dual LP : 0.01 7 244 61.00 - -0.00 3
lex dual LP : 0.00 0 0 0.00 -
barrier LP : 0.00 0 0 0.00 - 0.00 0
diving/probing LP: 0.00 1 13 13.00 -
strong branching : 0.00 0 0 0.00 -
(at root node) : - 0 0 0.00 -
conflict analysis: 0.00 0 0 0.00 -
NLP : Time Calls
all NLPs : 0.00 0
B&B Tree :
number of runs : 1
nodes : 3
nodes (total) : 3
nodes left : 0
max depth : 2
max depth (total): 2
backtracks : 0 (0.0%)
delayed cutoffs : 0
repropagations : 0 (0 domain reductions, 0 cutoffs)
avg switch length: 2.00
switching time : 0.00
Solution :
Solutions found : 2 (2 improvements)
First Solution : +1.12158252756666e+01 (in run 1, after 1 nodes, 0.01 seconds, depth 110, found by <trysol>)
Primal Bound : +3.83386822719347e+00 (in run 1, after 3 nodes, 0.02 seconds, depth 2, found by <relaxation>)
Dual Bound : +3.83386822719347e+00
Gap : 0.00 %
Root Dual Bound : +3.83386822719347e+00
Root Iterations : 243
More information about the Scip
mailing list