Extended Formulations for Control Languages Defined by Finite-State Automata

Many discrete optimal control problems feature combinatorial constraints on the possible switching patterns, a common example being minimum dwell-time constraints. After discretizing to a finite time grid, for these and many similar types of constraints, it is possible to give a description of the convex hull of feasible (finite-dimensional) binary controls via extended formulations. In … Read more

The if-then Polytope: Conditional Relations over Multiple Sets of Binary Variables

Inspired by its occurrence as a substructure in a stochastic railway timetabling model, we study in this work a special case of the bipartite boolean quadric polytope. It models conditional relations across three sets of binary variables, where selections within two “if” sets imply a choice in a corresponding “then” set. We call this polytope … Read more

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