An SDP Approach for Multiperiod Mixed 0–1 Linear Programming Models with Stochastic Dominance Constraints for Risk Management

Laureano F. Escudero, Juan Francisco Monge, Dolores Romero Morales

Research output: Working paperResearchpeer-review

Abstract

In this paper we consider multiperiod mixed 0–1 linear programming models under uncertainty. We propose a risk averse strategy using stochastic dominance constraints (SDC) induced by mixed-integer linear recourse as the risk measure. The SDC strategy extends the existing literature to the multistage case and includes both first-order and second-order constraints. We propose a stochastic dynamic programming (SDP) solution approach, where one has to overcome the negative impact the cross-scenario constraints, due to SDC, have on the decomposability of the model. In our computational experience we compare our SDP against a commercial optimization package, in terms of solution accuracy and elapsed time. We use supply chain planning instances, where procurement, production, inventory, and distribution decisions need to be made under demand uncertainty. We confirm the hardness of the testbed, where the benchmark cannot find a feasible solution for half of the test instances while we always find one, and show the appealing tradeoff of SDP, in terms of solution accuracy and elapsed time, when solving medium-to-large instances.
In this paper we consider multiperiod mixed 0–1 linear programming models under uncertainty. We propose a risk averse strategy using stochastic dominance constraints (SDC) induced by mixed-integer linear recourse as the risk measure. The SDC strategy extends the existing literature to the multistage case and includes both first-order and second-order constraints. We propose a stochastic dynamic programming (SDP) solution approach, where one has to overcome the negative impact the cross-scenario constraints, due to SDC, have on the decomposability of the model. In our computational experience we compare our SDP against a commercial optimization package, in terms of solution accuracy and elapsed time. We use supply chain planning instances, where procurement, production, inventory, and distribution decisions need to be made under demand uncertainty. We confirm the hardness of the testbed, where the benchmark cannot find a feasible solution for half of the test instances while we always find one, and show the appealing tradeoff of SDP, in terms of solution accuracy and elapsed time, when solving medium-to-large instances.
LanguageEnglish
Place of Publicationwww
PublisherMathematical Optimization Society
Number of pages24
StatePublished - 2014
Externally publishedYes
SeriesOptimization Online
Number4524
Volume08

Keywords

    Cite this

    Escudero, L. F., Monge, J. F., & Morales, D. R. (2014). An SDP Approach for Multiperiod Mixed 0–1 Linear Programming Models with Stochastic Dominance Constraints for Risk Management. www: Mathematical Optimization Society. Optimization Online, No. 4524, Vol.. 08
    Escudero, Laureano F. ; Monge, Juan Francisco ; Morales, Dolores Romero. / An SDP Approach for Multiperiod Mixed 0–1 Linear Programming Models with Stochastic Dominance Constraints for Risk Management. www : Mathematical Optimization Society, 2014. (Optimization Online; No. 4524, ???volume??? 08).
    @techreport{73d2c644a86647419e98a1f0a48914e2,
    title = "An SDP Approach for Multiperiod Mixed 0–1 Linear Programming Models with Stochastic Dominance Constraints for Risk Management",
    abstract = "In this paper we consider multiperiod mixed 0–1 linear programming models under uncertainty. We propose a risk averse strategy using stochastic dominance constraints (SDC) induced by mixed-integer linear recourse as the risk measure. The SDC strategy extends the existing literature to the multistage case and includes both first-order and second-order constraints. We propose a stochastic dynamic programming (SDP) solution approach, where one has to overcome the negative impact the cross-scenario constraints, due to SDC, have on the decomposability of the model. In our computational experience we compare our SDP against a commercial optimization package, in terms of solution accuracy and elapsed time. We use supply chain planning instances, where procurement, production, inventory, and distribution decisions need to be made under demand uncertainty. We confirm the hardness of the testbed, where the benchmark cannot find a feasible solution for half of the test instances while we always find one, and show the appealing tradeoff of SDP, in terms of solution accuracy and elapsed time, when solving medium-to-large instances.",
    keywords = "Multiperiod stochastic mixed 0–1 linear programming, Risk averse, Stochastic dominance constraints, Stochastic dynamic programming, Cross-scenario constraints",
    author = "Escudero, {Laureano F.} and Monge, {Juan Francisco} and Morales, {Dolores Romero}",
    year = "2014",
    language = "English",
    publisher = "Mathematical Optimization Society",
    address = "United States",
    type = "WorkingPaper",
    institution = "Mathematical Optimization Society",

    }

    An SDP Approach for Multiperiod Mixed 0–1 Linear Programming Models with Stochastic Dominance Constraints for Risk Management. / Escudero, Laureano F.; Monge, Juan Francisco; Morales, Dolores Romero.

    www : Mathematical Optimization Society, 2014.

    Research output: Working paperResearchpeer-review

    TY - UNPB

    T1 - An SDP Approach for Multiperiod Mixed 0–1 Linear Programming Models with Stochastic Dominance Constraints for Risk Management

    AU - Escudero,Laureano F.

    AU - Monge,Juan Francisco

    AU - Morales,Dolores Romero

    PY - 2014

    Y1 - 2014

    N2 - In this paper we consider multiperiod mixed 0–1 linear programming models under uncertainty. We propose a risk averse strategy using stochastic dominance constraints (SDC) induced by mixed-integer linear recourse as the risk measure. The SDC strategy extends the existing literature to the multistage case and includes both first-order and second-order constraints. We propose a stochastic dynamic programming (SDP) solution approach, where one has to overcome the negative impact the cross-scenario constraints, due to SDC, have on the decomposability of the model. In our computational experience we compare our SDP against a commercial optimization package, in terms of solution accuracy and elapsed time. We use supply chain planning instances, where procurement, production, inventory, and distribution decisions need to be made under demand uncertainty. We confirm the hardness of the testbed, where the benchmark cannot find a feasible solution for half of the test instances while we always find one, and show the appealing tradeoff of SDP, in terms of solution accuracy and elapsed time, when solving medium-to-large instances.

    AB - In this paper we consider multiperiod mixed 0–1 linear programming models under uncertainty. We propose a risk averse strategy using stochastic dominance constraints (SDC) induced by mixed-integer linear recourse as the risk measure. The SDC strategy extends the existing literature to the multistage case and includes both first-order and second-order constraints. We propose a stochastic dynamic programming (SDP) solution approach, where one has to overcome the negative impact the cross-scenario constraints, due to SDC, have on the decomposability of the model. In our computational experience we compare our SDP against a commercial optimization package, in terms of solution accuracy and elapsed time. We use supply chain planning instances, where procurement, production, inventory, and distribution decisions need to be made under demand uncertainty. We confirm the hardness of the testbed, where the benchmark cannot find a feasible solution for half of the test instances while we always find one, and show the appealing tradeoff of SDP, in terms of solution accuracy and elapsed time, when solving medium-to-large instances.

    KW - Multiperiod stochastic mixed 0–1 linear programming

    KW - Risk averse

    KW - Stochastic dominance constraints

    KW - Stochastic dynamic programming

    KW - Cross-scenario constraints

    M3 - Working paper

    BT - An SDP Approach for Multiperiod Mixed 0–1 Linear Programming Models with Stochastic Dominance Constraints for Risk Management

    PB - Mathematical Optimization Society

    CY - www

    ER -