Abstract
We study a substructure appearing in mixed-integer programming reformulations of chance-constrained programs with stochastic right-hand-sides over a finite discrete distribution, which we call the mixing set with a knapsack constraint. Recently, Luedtke et al. (Math. Program. 122(2):247–272, 2010) and Küçükyavuz (Math Program 132(1):31–56, 2012) studied valid inequalities for such sets. However, most of their results were focused on the equal probabilities case (when the knapsack constraint reduces to a cardinality constraint). In this paper, we focus on the general probabilities case (general knapsack constraint). We characterize the valid inequalities that do not come from the knapsack polytope and use this characterization to generalize the results previously derived for the equal probabilities case. Our results allow for a deep understanding of the relationship that the set under consideration has with the knapsack polytope. Moreover, they allow us to establish benchmarks that can be used to identify when a relaxation will be useful for the considered types of reformulations of chance-constrained programs.
Similar content being viewed by others
Notes
Sometimes the finite discrete distribution given is an approximation of an unknown continuous distribution, obtained via a Sample Average Approximation (SAA) technique.
Prior to our work, the main focus seems to have been on the equal probabilities case, justified by employing the SAA technique. Our more general framework of the general probabilities case allows for more sophisticated techniques such as Importance Sampling. See the recent work of Barrera et al. [6] for further details.
As shown in Luedtke [13], some valid inequalities for Q are also of value in the extremely general case where each mixing constraint is replaced by a set of arbitrary linear constraints.
References
Atamtürk, A., Nemhauser, G.L., Savelsbergh, M.W.P.: The mixed vertex packing problem. Math. Program. 89, 35–53 (2000)
Balas, E.: Disjunctive programming: properties of the convex hull of feasible points. Discrete Appl. Math. 89, 1–44 (1998)
Balas, E.: Disjunctive programming and a hierarchy of relaxations for discrete optimization problems. SIAM J. Algebr. Discrete Methods 6, 466–486 (1985)
Balas, E.: Facets of the knapsack polytope. Math. Program. 8, 146–164 (1975)
Balas, E., Zemel, E.: Facets of the knapsack polytope from minimal covers. SIAM J. Appl. Math. 34, 119–148 (1978)
Barrera, J., Homem-de-Mello, T., Moreno, E., Pagnoncelli, B.K., Canessa, G.: Chance-constrained problems and rare events: an importance sampling approach. http://www.optimization-online.org/DB_HTML/2014/02/4250.html
Beraldi, P., Ruszczyński, A.: A branch and bound method for stochastic integer programs under probabilistic constraints. Optim. Methods Softw. 17, 359–382 (2002)
Bienstock, D.: Approximate formulations for 0–1 knapsack sets. Oper. Res. Lett. 36, 317–320 (2008)
Guan, Y., Ahmed, S., Nemhauser, G.L.: Sequential pairing of mixed integer inequalities. Discrete Optim. 4, 21–39 (2007)
Günlük, O., Pochet, Y.: Mixing mixed-integer inequalities. Math. Program. 90, 429–457 (2001)
Hammer, P.L., Johnson, E.L., Peled, U.N.: Facets of regular 0–1 polytopes. Math. Program. 8, 179–206 (1975)
Küçükyavuz, S.: On mixing sets arising in chance-constrained programming. Math. Program. 132(1), 31–56 (2012)
Luedtke, J.: A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support. Math. Program. 146, 219–244 (2014)
Luedtke, J., Ahmed, S., Nemhauser, G.: An integer programming approach for linear programs with probabilistic constraints. Math. Program. 122(2), 247–272 (2010)
Ruszczyński, A.: Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra. Math. Program. 93, 195–215 (2002)
Sen, S.: Relaxations for probabilistically constrained programs with discrete random variables. Oper. Res. Lett. 11, 81–86 (1992)
Wolsey, L.A.: Faces for linear inequality in 0–1 variables. Math. Program. 8, 165–178 (1975)
Author information
Authors and Affiliations
Corresponding author
Additional information
Partially supported by NSERC Discovery Grant RGPIN-05623.
Rights and permissions
About this article
Cite this article
Abdi, A., Fukasawa, R. On the mixing set with a knapsack constraint. Math. Program. 157, 191–217 (2016). https://doi.org/10.1007/s10107-016-0979-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-016-0979-5
Keywords
- Chance-constrained integer program
- Mixing set
- Knapsack constraint
- Polyhedral combinatorics
- Integer programming