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

• 成果类型: Article
• 署名作者: El Housni, Omar; Foussoul, Ayoub; Goyal, Vineet
• 署名单位: Cornell University; Columbia University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-02004-9
• 发表日期: 2024
• 页码: 239-281
• 关键词: reformulation-linearization technique; Facility Location; affine policies; relaxations; algorithms; REPRESENTATIONS; hierarchy; discrete; games

摘要

We consider the class of disjoint bilinear programs max {x(T) y | x is an element of X, y is an element of Y} where X and Y are packing polytopes. We present an O( log logm1 /logm1 log logm2/ logm2)-approximation algorithm for this problem where m1 and m2 are the number of packing constraints in X and Y respectively. In particular, we show that there exists a near-optimal solution ( (x) over tilde, (y) over tilde) such that (x) over tilde and (y) over tilde 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. 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( log n /log log n 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. 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( log n log log n/ log L log log L)-approximation of the two-stage problem, significantly generalizing the previously known bounds on their performance.