Shadow prices on binding constraints

[Kasparton]

Hi GAMS community!

I have a question about shadow prices on binding constraints.

In the model below, I am trying to simulate an entity’s decision on how to comply with a greenhouse gas emission limit law.

There are seven years in which this model is run. The entity can either choose to purchase one unit of offset at a cost of 3, or pay a penalty of 100 for exceeding the legal GHG emission limit, denoted by “emissionsCap.” Offsets expire yearly, so every subsequent year, entities must purchase new offsets. Each year, the entity emits 10 units (annualEmissions(t)). The cap (emissionsCap(t)) starts at 11 units and decreases by 1 unit per year. I’ve set the maximum number of offsets the entity can use to 3. So, I expect the entity to buy 0 offsets in year 1, but offsets in years 2, 3, and 4, and then pay a penalty in years 6 and 7.

When I calculate shadow prices on emissionsCap(t), I get [0, 0, 3, 3, 100, 100, 100]. However, I expect in year 5 to get a shadow price of 3, rather than 100, since we are taking the shadow price by relaxing the constraint. When I relax the offset usage limit to 3.5 units, the model does as I expect, namely I get shadow prices of [0, 0, 3, 3, 3, 100, 100].

Can someone help me understand what is going on here?

Here is my code below:

Code: Select all

Sets:
      t = [1, 2, 3, 4, 5, 6, 7];

Parameters:
       Cost = 3;
       Penalty = 100;
       annualEmissions(t)   = [10, 10, 10, 10, 10, 10, 10];
       emissionsCap(t)        = [11, 10, 9, 8, 7, 6, 5];

Variables:
Z;

Positive Variables:
        offsetsOwned(t)                      Offsets owned in year t
        offsetsLost(t)                            Expiration of offsets in time t                                    
        offsetsBought(t)                      Offsets bought in year t
        overEmissions(t)                      Amount of emissions over the emissions cap fined $100/tCO2e
        netEmissions(t)                        Entity emissions net of compliance options used
;

Equations:
        obj..                                             Z =e= sum(t, Cost * offsetsOwned(t) + overEmissions(t) * penalty);

        emissionCap(t)..                        overEmissions(t) + emissionsCap (t) =g= netEmissions(t);
        netEmissionsDefinition(t)..      netEmissions( t) =e= annualEmissions(t) - offsetsOwned(t);
        complianceConstraint(t)..        offsetsOwned(t) =e= offsetsOwned(t-1) + offsetsBought(t) – offsetsLost(t); 
        retirementLimit(t)..                   offsetsLost(t) =l= offsetsOwned(t-1);
        uptake(t)..                                   offsetsOwned(t) =l= 3;

Model sim / all /;
Solve sim using LP minimizing Z;

[bussieck]

Your model is dual degenerate, i.e. you have multiple dual solutions. Select different solvers and you (might) get different dual solutions. Both dual solutions are just fine:

BDMLP:

Code: Select all

---- EQU emissionCap  

         LOWER          LEVEL          UPPER         MARGINAL

1       -11.0000       -10.0000        +INF             .          
2       -10.0000       -10.0000        +INF            3.0000      
3        -9.0000        -9.0000        +INF            3.0000      
4        -8.0000        -8.0000        +INF            3.0000      
5        -7.0000        -7.0000        +INF            3.0000      
6        -6.0000        -6.0000        +INF          100.0000      
7        -5.0000        -5.0000        +INF          100.0000      

Cplex:

Code: Select all

         LOWER          LEVEL          UPPER         MARGINAL

1       -11.0000       -10.0000        +INF             .          
2       -10.0000       -10.0000        +INF             .          
3        -9.0000        -9.0000        +INF            3.0000      
4        -8.0000        -8.0000        +INF            3.0000      
5        -7.0000        -7.0000        +INF          100.0000      
6        -6.0000        -6.0000        +INF          100.0000      
7        -5.0000        -5.0000        +INF          100.0000      

-Michael

[Kasparton]

Thanks for your help - I have some follow up questions.

1) Is it possible to know whether we have a dual-degenerate solution without trying different solvers?
2) What does having dual-degenerate solutions mean for our problem and model?
3) How do you suggest getting around dual degenerate solutions?

[bussieck]

1) Yes. Look for EPS as a marginal. So if you have a non-basic (slack) variable with zero marginal. I like the description at https://glossary.informs.org/indexVer1.php?page=D.html
2) That you have multiple dual optimal solutions. A very natural thing especially for larger real world models (there is a hyposthesis that any "real" model of a certain size is degenerate). This means there are "ties" when it comes to who is setting the price and this ripples through. Again, no right or wrong.
3) I don't think there is a way around this.

There is lots of material on degeneracy in the web.

-Michael