Multiple solutions in stylized flood planning model

For a project I was looking at a simple two stage stochastic integer programming problem (1).

I find it always very rewarding to reproduce the results in  the paper. Re-implementing the model forces me to not skip the details. Compared to superficial reading it requires to pay attention to all aspects. Of course in many cases journal papers do not allow to reproduce results because crucial details or data are left out. Presenting a stylized model illustrating and illuminating the concepts is only done sporadically, may be because it is actually hard to create such a “simple” model, and it may look less “scientific”.

The model is a fairly standard 2 stage SLP. In stage 1 we can implement so-called permanent floodplain management actions (raising structures, implement warning systems, etc.) The realizations are floods of different sizes. In stage 2 we can apply certain emergency measures (evacuations, issue sandbags etc.).

After re-implementing the model I saw the same objective function values, but the stage 2 variables differed a bit.

The paper shows a table with the stage 2 results:

In GAMS we do not see any of the levee monitoring being implemented:

----    145 VARIABLE xe.L  stage 2 decisions: emergency options              peak5-6     peak6-8    peak8-10     peak10+ evacuate                   1.000       1.000       1.000 sandbag        2.000       2.000

GAMS will report marginals (duals and reduced costs) even for a MIP. They fix the integer variables and resolve as an LP to get these. Here are the relevant marginals:

----    145 VARIABLE xe.M  stage 2 decisions: emergency options              peak0-5     peak5-6     peak6-8    peak8-10     peak10+ evacuate   80000.000    7900.000  -12000.000   -8000.000   -9000.000 sandbag    24000.000  -12200.000  -46200.000     600.000     300.000 monitor        0.800       0.079         EPS       0.020       0.010

This EPS means this variable is non-basic with a zero reduced cost. This can indicate the presence of multiple optima. Indeed when using a different MIP solver I see:

----    145 VARIABLE xe.L  stage 2 decisions: emergency options              peak5-6     peak6-8    peak8-10     peak10+ evacuate                   1.000       1.000       1.000 sandbag        2.000       2.000 monitor                20000.000

which is the same as the results in the paper.

Digging a little bit further, we can see that the damage reduction by implementing emergency measure “monitor” is the same as its cost. This means we are indifferent whether to apply this option in this scenario.

----    154 PARAMETER red2  damage reduction b(j,s)*xe.l(j,s)              peak5-6     peak6-8    peak8-10     peak10+ evacuate              300000.000  500000.000 1000000.000 sandbag  2000000.000 1600000.000 monitor                20000.000 ----    154 PARAMETER c2  emergency option cost ce(j)*xe.l(j,s)              peak5-6     peak6-8    peak8-10     peak10+ evacuate              100000.000  100000.000  100000.000 sandbag    60000.000   60000.000 monitor                20000.000

I would guess the chance this will happen with real data is smaller than with these nicely rounded invented data.

The model itself is implemented as a fairly standard deterministic equivalent formulation:

References

1. Jay R. Lund, Floodplain Planning with Risk-based Optimization, Journal of Water Resources Planning and Management, Vol. 127, No. 3, May 2002