LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization

DOI10.1007/978-3-031-06901-7_17MaRDI QIDQ2164699zbMATH OpenOpenAlexFDO

Authors Omar El Housni, Ayoub Foussoul, Vineet Goyal

Publication date 16 August 2022

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

zbMATH Keywords

approximation algorithmsdisjoint bilinear programmingtwo-stage robust optimization

Mathematics Subject Classification ID

Robustness in mathematical programming (90C17) Nonlinear programming (90C30)

Abstract: We consider the class of disjoint bilinear programs $max,mathbf{x}^{T}mathbfymidmathbfxinmathcalX,;mathbfyinmathcalY$ where $mathcalX$ and $mathcalY$ are packing polytopes. We present an $O(fracloglog{m}_{1}log{m}_{1}fracloglog{m}_{2}log{m}_2)$-approximation algorithm for this problem where $m_1$ and $m_2$ are the number of packing constraints in $mathcalX$ and $mathcalY$ respectively. In particular, we show that there exists a near-optimal solution $(ildemathbfx,ildemathbfy)$ such that $ildemathbfx$ and $ildemathbfy$ are ``near-integral". We give an LP relaxation of the problem from which we obtain the near-optimal near-integral solution via randomized rounding. We show that our relaxation is tightly related to the widely used reformulation linearization technique (RLT). As an application of our techniques, we present a tight approximation for the two-stage adjustable robust optimization problem with covering constraints and right-hand side uncertainty where the separation problem is a bilinear optimization problem. In particular, based on the ideas above, we give an LP restriction of the two-stage problem that is an $O(fraclognloglognfraclogLloglogL)$-approximation where $L$ is the number of constraints in the uncertainty set. This significantly improves over state-of-the-art approximation bounds known for this problem. Furthermore, we show that our LP restriction gives a feasible affine policy for the two-stage robust problem with the same (or better) objective value. As a consequence, affine policies give an $O(fraclognloglognfraclogLloglogL)$-approximation of the two-stage problem, significantly generalizing the previously known bounds on their performance.

Recommendations

• Disjoint Bilinear Optimization: A Two-Stage Robust Optimization Perspective
• Discrete approximation of two-stage stochastic and distributionally robust linear complementarity problems
• Decomposition and discrete approximation methods for solving two-stage distributionally robust optimization problems
• On 2-stage robust LP with RHS uncertainty: complexity results and applications
• Robust approximate bilinear programming for value function approximation
• A Lagrangian dual method for two-stage robust optimization with binary uncertainties
• A tight characterization of the performance of static solutions in two-stage adjustable robust linear optimization
• Linearized Robust Counterparts of Two-Stage Robust Optimization Problems with Applications in Operations Management
• A primal-dual lifting scheme for two-stage robust optimization
• Decomposition-Based Approaches for a Class of Two-Stage Robust Binary Optimization Problems

Cites work

• A copositive approach for two-stage adjustable robust optimization with uncertain right-hand sides
• A cutting plane algorithm for solving bilinear programs
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A note on the solution of bilinear programming problems by reduction to concave minimization
• A tractable approach for designing piecewise affine policies in two-stage adjustable robust optimization
• Adjustable robust optimization via Fourier-Motzkin elimination
• Adjustable robust solutions of uncertain linear programs
• Bilinear modeling solution approach for fixed charge network flow problems
• Different transformations for solving non-convex trim-loss problems by MINLP
• Duality in two-stage adaptive linear optimization: faster computation and stronger bounds
• Generalized Benders decomposition
• Matching Drivers to Riders: A Two-Stage Robust Approach
• On the optimality of affine policies for budgeted uncertainty sets
• On the performance of affine policies for two-stage adaptive optimization: a geometric perspective
• On the power and limitations of affine policies in two-stage adaptive optimization
• On the power of static assignment policies for robust facility location problems
• Optimal Facility Location with Concave Costs
• Relaxations and discretizations for the pooling problem
• Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets
• Robust Combinatorial Optimization with Exponential Scenarios
• Settling the complexity of computing two-player Nash equilibria
• The bilinear assignment problem: complexity and polynomially solvable special cases
• The bilinear programming problem
• The Price of Robustness
• Theory and applications of robust optimization
• Thresholded covering algorithms for robust and max-min optimization
• Tractable stochastic analysis in high dimensions via robust optimization
• Two-person nonzero-sum games and quadratic programming

Cited in

(5)

• Disjoint Bilinear Optimization: A Two-Stage Robust Optimization Perspective
• Linearized Robust Counterparts of Two-Stage Robust Optimization Problems with Applications in Operations Management
• On 2-stage robust LP with RHS uncertainty: complexity results and applications
• LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization
• Adjustability in robust linear optimization

This page was built for publication: LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization

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