Joint chance-constrained programs and the intersection of mixing sets through a submodularity lens

DOI10.1007/S10107-021-01688-1MaRDI QIDQ2089774zbMATH OpenOpenAlexFDO

Authors Fatma Kılınç-Karzan, Simge Küçükyavuz, Dabeen Lee

Publication date 24 October 2022

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.01353

Mathematics Subject Classification ID

Integer programming (90C10) Mixed integer programming (90C11) Stochastic programming (90C15) Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Abstract: A particularly important substructure in modeling joint linear chance-constrained programs with random right-hand sides and finite sample space is the intersection of mixing sets with common binary variables (and possibly a knapsack constraint). In this paper, we first revisit basic mixing sets by establishing a strong and previously unrecognized connection to submodularity. In particular, we show that mixing inequalities with binary variables are nothing but the polymatroid inequalities associated with a specific submodular function. This submodularity viewpoint enables us to unify and extend existing results on valid inequalities and convex hulls of the intersection of multiple mixing sets with common binary variables. Then, we study such intersections under an additional linking constraint lower bounding a linear function of the continuous variables. This is motivated from the desire to exploit the information encoded in the knapsack constraint arising in joint linear CCPs via the quantile cuts. We propose a new class of valid inequalities and characterize when this new class along with the mixing inequalities are sufficient to describe the convex hull.

Recommendations

• On intersection of two mixing sets with applications to joint chance-constrained programs
• On mixing sets arising in chance-constrained programming
• On the mixing set with a knapsack constraint
• Submodularity in Conic Quadratic Mixed 0–1 Optimization
• A polyhedral study on chance constrained program with random right-hand side

Cites work

• A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support
• A polyhedral study of the static probabilistic lot-sizing problem
• A polyhedral study on chance constrained program with random right-hand side
• A Sample Approximation Approach for Optimization with Probabilistic Constraints
• Ambiguous Chance-Constrained Binary Programs under Mean-Covariance Information
• An Efficient Trajectory Method for Probabilistic Production-Inventory-Distribution Problems
• An integer programming approach for linear programs with probabilistic constraints
• Chance-Constrained Binary Packing Problems
• Covering linear programming with violations
• Decomposition algorithms for two-stage chance-constrained programs
• Exact algorithms for combinatorial optimization problems with submodular objective functions
• scientific article; zbMATH DE number 1688594 (Why is no real title available?)
• scientific article; zbMATH DE number 3904328 (Why is no real title available?)
• scientific article; zbMATH DE number 2121076 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Mixing MIR inequalities with two divisible coefficients
• Mixing mixed-integer inequalities
• Nonanticipative duality, relaxations, and formulations for chance-constrained stochastic programs
• On intersection of two mixing sets with applications to joint chance-constrained programs
• On mixing sets arising in chance-constrained programming
• On quantile cuts and their closure for chance constrained optimization problems
• On the mixing set with a knapsack constraint
• Optimization of a continuous distillation process under random inflow rate.
• Polyhedra for lot-sizing with Wagner-Whitin costs
• Polyhedral results for a class of cardinality constrained submodular minimization problems
• Polymatroids and mean-risk minimization in discrete optimization
• Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra
• Solution of a product substitution problem using stochastic programming
• Submodularity in Conic Quadratic Mixed 0–1 Optimization
• The mixed vertex packing problem.
• The Mixing Set with Flows
• The mixing-MIR set with divisible capacities
• The Scenario Approach to Robust Control Design
• Tight formulations for some simple mixed integer programs and convex objective integer programs
• Uncertain convex programs: randomized solutions and confidence levels

Cited in

(9)

• A polyhedral study on chance constrained program with random right-hand side
• Sequence independent lifting for a set of submodular maximization problems
• On intersection of two mixing sets with applications to joint chance-constrained programs
• On mixing sets arising in chance-constrained programming
• On the mixing set with a knapsack constraint
• Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints
• Chance-constrained optimization under limited distributional information: a review of reformulations based on sampling and distributional robustness
• Supermodularity and valid inequalities for quadratic optimization with indicators
• Adaptive partitioning for chance-constrained problems with finite support

Describes a project that uses

Uses Software

• PORTA

This page was built for publication: Joint chance-constrained programs and the intersection of mixing sets through a submodularity lens

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2089774)