MIP reformulations of the probabilistic set covering problem

DOI10.1007/s10107-008-0224-yzbMath1184.90116OpenAlexW2167201389MaRDI QIDQ847820

Vineet Goyal, Anureet Saxena, Miguel A. Lejeune

Publication date: 19 February 2010

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

Full work available at URL: http://edoc.hu-berlin.de/18452/9026

zbMATH Keywords

Cutting planesSet coveringProbabilistic programming

Mathematics Subject Classification ID

Integer programming (90C10) Stochastic programming (90C15) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Decomposition algorithms for two-stage chance-constrained programs, Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations, Cutting plane versus compact formulations for uncertain (integer) linear programs, Robust min-max regret covering problems, Chance-Constrained Binary Packing Problems, Proportional and maxmin fairness for the sensor location problem with chance constraints, An exact method for constrained maximization of the conditional value-at-risk of a class of stochastic submodular functions, Easy distributions for combinatorial optimization problems with probabilistic constraints, A polyhedral study on chance constrained program with random right-hand side, An algorithm for binary linear chance-constrained problems using IIS, A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support, Disjunctive Cuts for Non-convex Mixed Integer Quadratically Constrained Programs, Chance-constrained optimization under limited distributional information: a review of reformulations based on sampling and distributional robustness, Improved handling of uncertainty and robustness in set covering problems, Chance-constrained set covering with Wasserstein ambiguity, On mixing sets arising in chance-constrained programming, Mixed integer linear programming formulations for probabilistic constraints, Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations, Probabilistic Partial Set Covering with an Oracle for Chance Constraints, Optimization models of anti-terrorist protection, Robust strategic planning for mobile medical units with steerable and unsteerable demands, An efficient computational method for large scale surgery scheduling problems with chance constraints, Algorithm to optimize the quantile criterion for the polyhedral loss function and discrete distribution of random parameters, Mathematical programming approaches for generating \(p\)-efficient points, General properties of two-stage stochastic programming problems with probabilistic criteria, Reformulations in Mathematical Programming: Definitions and Systematics, Branch-and-cut approaches for chance-constrained formulations of reliable network design problems, A new approach for solving set covering problem using jumping particle swarm optimization method, AN IMPROVED CONVEX 0-1 QUADRATIC PROGRAM REFORMULATION FOR CHANCE-CONSTRAINED QUADRATIC KNAPSACK PROBLEMS

Uses Software

• OR-Library
• PORTA
• VRP

Cites Work

• Unnamed Item
• Unnamed Item
• Optimizing over the first Chvátal closure
• An exact algorithm for the capacitated facility location problems with single sourcing
• Relaxations for probabilistically constrained programs with discrete random variables
• Disjunctive programming: Properties of the convex hull of feasible points
• Balanced \(0,\pm 1\)-matrices, bicoloring and total dual integrality
• Optimizing over the split closure
• The vertex separator problem: algorithms and computations
• An Efficient Trajectory Method for Probabilistic Production-Inventory-Distribution Problems
• The Probabilistic Set-Covering Problem
• Cyclic Scheduling via Integer Programs with Circular Ones
• A branch and bound method for stochastic integer problems under probabilistic constraints
• Dual method for the solution of a one-stage stochastic programming problem with random RHS obeying a discrete probability distribution
• Probabilistic Symmetries and Invariance Principles
• Concavity and efficient points of discrete distributions in probabilistic programming.