A proof for multilinear error bounds

\(\) We derive the error bounds for multilinear terms in $[0,1]^n$ using a proof methodology based on the polyhedral representation of the convex hull. We extend the result for multilinear terms in $[\boldsymbol{L},\boldsymbol{0}] \times [\boldsymbol{0},\boldsymbol{U}]\subset\mathbb{R}^n$. Article Download View A proof for multilinear error bounds

Tightening Quadratic Convex Relaxations for the AC Optimal Transmission Switching Problem

The Alternating Current Optimal Transmission Switching (ACOTS) problem incorporates line switching decisions into the fundamental AC optimal power flow (ACOPF) problem. The advantages of the ACOTS problem are well-known in terms of reducing the operational cost and improving system reliability. ACOTS optimization models contain discrete variables and nonlinear, non-convex constraints, which make it difficult to … Read more

A Note on Semidefinite Representable Reformulations for Two Variants of the Trust-Region Subproblem

Motivated by encouraging numerical results in the literature, in this note we consider two specific variants of the trust-region subproblem and provide exact semidefinite representable reformulations. The first is over the intersection of two balls; the second is over the intersection of a ball and a special second-order conic representable set. Different from the technique … Read more

On Constrained Mixed-Integer DR-Submodular Minimization

DR-submodular functions encompass a broad class of functions which are generally non-convex and non-concave. We study the problem of minimizing any DR-submodular function, with continuous and general integer variables, under box constraints and possibly additional monotonicity constraints. We propose valid linear inequalities for the epigraph of any DR-submodular function under the constraints. We further provide … Read more

Explicit convex hull description of bivariate quadratic sets with indicator variables

\(\) We consider the nonconvex set \(S_n = \{(x,X,z): X = x x^T, \; x (1-z) =0,\; x \geq 0,\; z \in \{0,1\}^n\}\), which is closely related to the feasible region of several difficult nonconvex optimization problems such as the best subset selection and constrained portfolio optimization. Utilizing ideas from convex analysis and disjunctive programming, … Read more

Superadditive duality and convex hulls for mixed-integer conic optimization

We present an infinite family of linear valid inequalities for a mixed-integer conic program, and prove that these inequalities describe the convex hull of the feasible set when this set is bounded and described by integral data. The main element of our proof is to establish a new strong superadditive dual for mixed-integer conic programming … Read more

Relaxations and Cutting Planes for Linear Programs with Complementarity Constraints

We study relaxations for linear programs with complementarity constraints, especially instances whose complementary pairs of variables are not independent. Our formulation is based on identifying vertex covers of the conflict graph of the instance and generalizes the extended reformulation-linearization technique of Nguyen, Richard, and Tawarmalani to instances with general complementarity conditions between variables. We demonstrate … Read more

Multiple-Periods Locally-Facet-Based MIP Formulations for the Unit Commitment Problem

The thermal unit commitment (UC) problem has historically been formulated as a mixed integer quadratic programming (MIQP), which is difficult to solve efficiently, especially for large-scale systems. The tighter characteristic reduces the search space, therefore, as a natural consequence, significantly reduces the computational burden. In literatures, many tightened formulations for a single unit with parts … Read more

A Graph-based Decomposition Method for Convex Quadratic Optimization with Indicators

In this paper, we consider convex quadratic optimization problems with indicator variables when the matrix Q defining the quadratic term in the objective is sparse. We use a graphical representation of the support of Q, and show that if this graph is a path, then we can solve the associated problem in polynomial time. This … Read more

On the Formulation Dependence of Convex Hull Pricing

Convex hull pricing provides a potential solution for reducing out-of-market payments in wholesale electricity markets. This paper revisits the theoretical construct of convex hull pricing and explores its important but underappreciated formulation-dependence property. Namely, convex hull prices may change for different formulations of the same unit commitment problem. After a conceptual exposition of the property, … Read more