In this paper, we focus on a subclass of quadratic optimization problems, that is, disjoint bilinear programming problems. We show that disjoint bilinear programming problems can be cast as two-stage robust linear optimization problems with fixed-recourse and right-hand-side uncertainty, and techniques for two-stage robust optimization can be used to solve the resulting problems. To this end, a scheme based on a blending of Fourier-Motzkin elimination and linear decision rules is used. Moreover, we show that the approximation via linear decision rules for the two-stage robust optimization reformulation is equivalent to applying a reformulation-linearization technique to the original disjoint bilinear problem. We then extend our approach to solve general bilinear problems. Numerical experiments on bimatrix games and concave quadratic minimization problems show that the proposed method is superior to the off-the-shelf solvers SCIP and CPLEX.

In this paper we consider uncertain second-order cone (SOC) and semidefinite programming (SDP) constraints with polyhedral uncertainty, which are in general computationally intractable. We propose to reformulate an uncertain SOC or SDP constraint as a set of adjustable robust linear optimization constraints withan ellipsoidal or semidefinite representable uncertainty set, respectively. The resulting adjustable problem can then (approximately) be solved by using adjustable robust linear optimization techniques. For example, we show that if linear decision rules are used, then the final robust counterpart consists of SOC or SDP constraints, respectively, which have the same computational complexity as the nominal version of the original constraints. We propose an efficient method to obtain good lower bounds. Moreover, we extend our approach to other classes of robust optimization problems, such as nonlinear problems that contain waitand-see variables or linear problems that contain bilinear uncertainty. Numerically, we apply our approach to reformulate the problem on finding the minimum volume circumscribing ellipsoid of a polytope, and solvethe resulting reformulation with linear and quadratic decision rules as well as Fourier-Motzkin elimination. We demonstrate the effectiveness and efficiency of the proposed approach by comparing it with the state-ofthe-art copositive approach. Moreover, we apply the proposed approach to a robust regression problem and a robust sensor network problem, and use linear decision rules to solve the resulting adjustable robust linear optimization problems, which solves the problem to (near) optimality.

We introduce a novel scheme based on a blending of Fourier-Motzkin elimination (FME) and adjustable robust optimization techniques to compute the maximum volume inscribed ellipsoid (MVE) in a polytopic projection. It is well-known that deriving an explicit description of a projected polytope is NP-hard. Our approach does not require an explicit description of the projection, and can easily be generalized to find a maximally sized convex body of a polytopic projection. Our obtained MVE is an inner approximation of the projected polytope, and its center is a centralized relative interior point of the projection. Since FME may produce many redundant constraints, we apply an LP-based procedure to keep the description of the projected polytopes at its minimal size. Furthermore, we propose an upper bounding scheme to evaluate the quality of the inner approximations. We test our approach on a simple polytope and a color tube design problem, and observe that as more auxiliary variables are eliminated, our inner approximations and upper bounds converge to optimal solutions. The online supplement is available at https://doi.org/10.1287/ijoc.2017.0763 .