LP-Based Approximations for Disjoint Bilinear and Two-Stage Adjustable Robust Optimization

Omar El Housni, Ayoub Foussoul, Vineet GoyalMath. Program 2022 · DOI · OpenReview

TL;DR

This paper introduces novel LP-based approximation algorithms for two challenging optimization problems: disjoint bilinear programming (PDB) and two-stage adjustable robust optimization (AR). The authors achieve significant improvements in approximation guarantees and computational efficiency, particularly for AR, by developing new LP relaxations and leveraging structural properties of the problems.

What Problem Does This Paper Address?

The paper tackles two classes of optimization problems that are notoriously difficult to solve exactly:

  1. Disjoint Bilinear Programs (PDB): These problems involve maximizing a bilinear objective function (a product of two variables) over packing polytopes. While PDB is NP-hard, existing literature lacks approximation algorithms with provable guarantees. The authors aim to bridge this gap by developing efficient approximation algorithms.
  2. Two-Stage Adjustable Robust Optimization (AR): This framework deals with decision-making under uncertainty where decisions can be adjusted after some uncertainty is revealed. A key challenge in AR is solving the "separation problem," which often takes the form of a PDB variant. Existing approximation bounds for AR, especially for general uncertainty sets, are often weak or scale poorly with problem size. The authors seek to improve these bounds and provide a more efficient approach.

Methods

The core of the paper lies in developing novel LP relaxations and randomized rounding techniques:

  • For PDB: The authors introduce a new LP relaxation (LP-PDB) and show its connection to the Reformulation Linearization Technique (RLT). A key insight is proving the existence of a "near-integral" near-optimal solution, which is then obtained via randomized rounding of the LP solution. This leads to a polylogarithmic approximation guarantee.
  • For AR: The authors leverage ideas from their PDB approximation to develop a compact linear restriction of AR. This restriction, derived from the separation problem of AR, provides a polylogarithmic approximation guarantee for AR, significantly improving upon prior results.
  • Connection to Affine Policies: A surprising finding is the tight relationship between their LP restriction for AR and affine policies. They show that their LP relaxation can be used to construct a near-optimal affine policy, providing a faster way to compute such policies and establishing a strong theoretical bound for them.

Datasets

Not discussed in the paper. The authors focus on theoretical algorithm development and numerical evaluation using randomly generated instances.

Key Insights and Ideas

  • Structural Property of PDB: The existence of a "near-integral" near-optimal solution for PDB is a crucial structural insight that enables the development of the approximation algorithm. This means that an optimal or near-optimal solution can be found where variables are close to either 0 or a specific scaled value.
  • LP Relaxation for AR: The paper demonstrates that a carefully constructed LP relaxation of the AR problem, inspired by PDB techniques, can yield significant improvements in approximation guarantees. This highlights the power of LP-based methods even for problems with complex uncertainty structures.
  • Affine Policies as a Bridge: The unexpected link between the LP restriction for AR and affine policies is a significant contribution. It shows that a theoretically derived LP can directly lead to practical, efficient policies with strong performance guarantees.
  • RLT Equivalence: Establishing the equivalence between their LP relaxation for PDB and a specific RLT formulation provides a deeper theoretical understanding and connects their work to established techniques in optimization.

Key Results

  • PDB Approximation: An O(log log m₁ log log m₂) approximation algorithm for disjoint bilinear programs with packing constraints.
  • AR Approximation: An O(log n log L / log log n log log L) approximation algorithm for two-stage adjustable robust optimization with packing uncertainty sets. This significantly improves upon previous bounds.
  • Affine Policy Performance: The paper proves that affine policies achieve the same O(log n log L / log log n log log L) approximation bound for AR.
  • Computational Efficiency: Numerical experiments show that the proposed algorithms are significantly faster than existing methods, especially for larger problem instances, while achieving competitive or better objective values. For instance, their PDB algorithm is orders of magnitude faster than the Gurobi solver for larger dimensions.

Limitations and Future Work

  • Assumption 1 for AR: The paper makes an assumption (Ax ≥ 0) for simplicity in the AR analysis, though they note it can be handled without loss of generality.
  • Generalization of AR: While the paper provides strong results for packing uncertainty sets, further research could explore extensions to other types of uncertainty sets.
  • Empirical vs. Theoretical Gap: While the algorithms are computationally efficient, further work could explore tighter theoretical bounds or analyze the gap between theoretical guarantees and empirical performance more deeply.
  • Hardness of Covering Programs: The paper notes that the covering disjoint bilinear program is NP-hard to approximate within any finite factor, suggesting that different approaches might be needed for such variants.

Summary updated

Abstract

We consider the class of disjoint bilinear programs $$ \max \; \{ \mathbf {x}^T\mathbf {y} \mid \mathbf {x} \in \mathcal {X}, \;\mathbf {y} \in \mathcal {Y}\}$$ where $$\mathcal {X}$$ and $$\mathcal {Y}$$ are packing polytopes. We present an $$O(\frac{\log \log m_1}{\log m_1} \frac{\log \log m_2}{\log m_2})$$ -approximation algorithm for this problem where $$m_1$$ and $$m_2$$ are the number of packing constraints in $$\mathcal {X}$$ and $$\mathcal {Y}$$ respectively. In particular, we show that there exists a near-optimal solution $$(\mathbf {x}, \mathbf {y})$$ such that $$\mathbf {x}$$ and $$\mathbf {y}$$ are “near-integral”. We give an LP relaxation of this problem from which we obtain the near-optimal near-integral solution via randomized rounding. 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(\frac{\log n}{\log \log n} \frac{\log L}{\log \log L})$$ -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.
BibTeX
@article{housni2022lp,
  author = {Omar El Housni and Ayoub Foussoul and Vineet Goyal},
  title = {{LP-Based Approximations for Disjoint Bilinear and Two-Stage Adjustable Robust Optimization}},
  journal = {Math. Program.},
  year = {2022},
  doi = {10.1007/s10107-023-02004-9},
}
Figure