[Scip] Problem with using non linear constraint handler

Stefan Vigerske stefan at math.hu-berlin.de
Tue Dec 11 15:14:59 MET 2012


Hi,

the problem is the infinite gradient of the sqrt(.) function when x_e 
gets 0. This confuses SCIP when it tries to qualify the violation of the 
"objective constraint" in a point where some of the x_e are 0.
We have some ideas on how to improve this, but no solution ready yet.

However, you can work around it by specifying nonzero lower bounds for 
the x_e (if you have some), or by rewriting the objective as sum_e z_e 
with constraints x_e =l= z_e^2, z_e >= 0. In both cases, performance for 
proving optimality isn't great, I've to admit.

Stefan


On 12/11/2012 01:45 PM, Ahmad Moradi wrote:
> 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
>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>



More information about the Scip mailing list