Why the linearized, binding equation has a zero shadow price? Topic is solved

Problems with modeling
Post Reply
EconZ
User
User
Posts: 5
Joined: 2 years ago

Why the linearized, binding equation has a zero shadow price?

Post by EconZ »

Hello all,

I have a simple quadratic model that requires NLP solvers to solve (this is a simple version of my actual model). However, I have linearized this model to solve it with MIP solvers. The linearized model works well and gives the exact same solution as the quadratic model. My problem is that one of the linearized equations (constraint BALANCE in my model) that seems to be binding has a zero shadow price, level, and Upper values. I am wondering what is the explanation for this and how I can obtain a shadow price for this constraint. My guess is that the zero level and shadow price are due to grid points values that I have used for linearization. I have attached the model.

I will appreciate any help,

Thanks,
Sirin

Code: Select all

$OFFSYMLIST OFFSYMXREF
 OPTION LIMCOL = 0;
 OPTION LIMROW = 0;

 SETS       CURVEPARM  CURVE PARAMETERS  /INTERCEPT,SLOPE/
            CURVES     TYPES OF CURVES   /DEMAND,SUPPLY/

 SETS   DK    'SEGMENTS FOR DEMAND'         /DK1*DK21/
 SETS   SK    'SEGMENTS FOR SUPPLY'         /SK1*SK21/

 TABLE      DATA(CURVES,CURVEPARM) SUPPLY DEMAND DATA

                   INTERCEPT    SLOPE
  DEMAND               6        -0.30
  SUPPLY               1         0.20

 PARAMETERS  SIGN(CURVES)  SIGN ON CURVES IN OBJECTIVE FUNCTION
                          /SUPPLY -1,  DEMAND 1/

 PARAMETER  DHVALUE(DK)  VALUES OF GRID POINTS FOR DEMAND
            SHVALUE(SK)  VALUES OF GRID POINTS FOR SUPPLY ;

 DHVALUE(DK)   =  10 * (ORD(DK) - 1)/10;
 SHVALUE(SK)   =  10 * (ORD(SK) - 1)/10;

 SOS2 VARIABLES   LAMH1(DK), LAMH2(SK);

 POSITIVE VARIABLES    QUANTITY(CURVES) ACTIVITY LEVEL

 VARIABLES             OBJ                 NUMBER TO BE MAXIMIZED

 EQUATIONS             OBJJ                OBJECTIVE FUNCTION
                       BALANCE             COMMODITY BALANCE
                       LAML1CONVEX         WEIGHTS OF GRID POINTS USED IN LINEARIZATION OF DEMAND
                       LAML2CONVEX         WEIGHTS OF GRID POINTS USED IN LINEARIZATION OF SUPPLY
;

$ONTEXT
 THE FOLLOWING EQUATIONS OUTSIDE THE ONTEXT AND OFFTEXT ARE LINEARIZATION OF THIS SIMPLE QUADRATIC MODEL
 OBJJ..   OBJ =E= SUM(CURVES, SIGN(CURVES)*
                        (DATA(CURVES,"INTERCEPT")*QUANTITY(CURVES)
                        +0.5*DATA(CURVES,"SLOPE")*QUANTITY(CURVES)**2)) ;

 BALANCE..    SUM(CURVES, SIGN(CURVES)*QUANTITY(CURVES)) =L= 0 ;

$OFFTEXT


 OBJJ..
    OBJ =E=
    SUM(DK,(DATA("DEMAND","INTERCEPT")          + 0.5 * DATA("DEMAND","SLOPE") * DHVALUE(DK)) * DHVALUE(DK) * LAMH1(DK))
    - (SUM(SK,(DATA("SUPPLY","INTERCEPT")       + 0.5 * DATA("SUPPLY","SLOPE") * SHVALUE(SK)) * SHVALUE(SK) * LAMH2(SK)))
 ;

*** DEMAND AND SUPPLY BALANCE
 BALANCE..  SUM(DK,DHVALUE(DK) * LAMH1(DK)) =L= SUM(SK,SHVALUE(SK) * LAMH2(SK));

*** CONVEX HULL COMBINATON OF THE GRID POINTS USED IN LINEARIZATION OF DEMAND
 LAML1CONVEX..   SUM(DK,LAMH1(DK)) =E= 1;

*** CONVEX HULL COMBINATON OF THE GRID POINT USED IN LINEARIZATION OF SUPPLY
 LAML2CONVEX..   SUM(SK,LAMH2(SK)) =E= 1;


 MODEL PRICEEND /ALL/ ;

 SOLVE PRICEEND USING MIP MAXIMIZING OBJ ;

 PARAMETER DIFFERENCE;
 DIFFERENCE = SUM(DK,DHVALUE(DK) * LAMH1.L(DK)) - SUM(SK,SHVALUE(SK) * LAMH2.L(SK));
 DISPLAY DIFFERENCE;

User avatar
bussieck
Moderator
Moderator
Posts: 1033
Joined: 7 years ago

Re: Why the linearized, binding equation has a zero shadow price?

Post by bussieck »

The duals produced by a MIP are the duals of the "fixed" problem. So the MIP solver link fixes your SOS variables and then solves the resulting LP. These marginals might have little to do with your original model. The fixed SOS variables LAMH1 and LAMH2 make the BALANCE equation a fixed equation (nothing can move), so increasing the rhs by 1 will not allow us to change the objective and hence the dual of this constraint is 0. A reformulation often works in the primal space but not so much in the dual... You can try to get a primal/dual pair from your solution returned by the mip solver by calling conopt on the rmip and set the iterlim to 4.

Moreover, don't write **2 use sqr() then you can solve as qcp and since your qp is convex you can also solve with cplex, xpress, gurobi, mosek, ...

-Michael
EconZ
User
User
Posts: 5
Joined: 2 years ago

Re: Why the linearized, binding equation has a zero shadow price?

Post by EconZ »

Thank you very much.
Post Reply