Session: Convex Relaxations for Discrete & Combinatorial Optimization
Chair: Soobin Choi
Cluster: nan
Talk 1: Rank-one Convexification for Convex Quadratic Optimization with Sign Indicators
Speaker: Soobin Choi
Abstract: We investigate convexification in convex quadratic optimization with sign indicators, where the sign of each continuous variable in the quadratic objective is controlled by a binary variable. First, we derive the convex hull for the epigraph of a quadratic function defined by a rank-one matrix. Using this rank-one convexification, we develop copositive and semi-definite relaxations for general convex quadratic functions. Leveraging these findings, we reformulate the support vector machine problem with 0--1 loss and conduct numerical experiments on synthetic and real instances.
Talk 2: Tightening Quadratic Convex Relaxations for the AC Optimal Transmission Switching Problem
Speaker: Cheng Guo
Abstract: The Alternating Current Optimal Transmission Switching (ACOTS) problem incorporates line switching decisions into the AC Optimal Power Flow framework, offering benefits in reducing costs and enhancing reliability. ACOTS optimization models contain discrete variables and nonlinear, non-convex constraints, which make it difficult to solve. We develop strengthened quadratic convex (QC) relaxations for ACOTS, where we tighten the relaxation with several new valid inequalities, including a novel kind of on/off cycle-based polynomial constraints by taking advantage of the network structure. We demonstrate theoretical tightness, and efficiently incorporate on/off cycle-based polynomial constraints through disjunctive programming-based cutting planes. Our method results in the tightest QC-based ACOTS relaxation to date. We additionally propose a novel maximum spanning tree-based heuristic to improve the computational performance by fixing certain lines to be switched on. Tests on large-scale instances with up to 2,312 buses demonstrate substantial performance gains. This work in under minor revision at INFORMS Journal on Computing, and is available on arXiv: https://arxiv.org/abs/2212.12097
Talk 3: Solving Large Flag Algebra Problems
Speaker: Bernard Lidický
Abstract: The Flag Algebra Method is a tool in extremal combinatorics, which has been very useful to tackle open problems for graphs, hypergraphs, permutations, pointsets and others. The method establishes combinatorial inequalities via sums of squares, which are usually obtained by a semidefinite relaxation of the original combinatorial problem. A typical application of the method in graph theory starts with fixing a parameter $n$ followed by constructing a semidefinite program based on the (subgraph) structure of all $n$-vertex graphs. In particular, the number of constraints in the resulting program is at least the number of all $n$-vertex graphs upto isomorphism. These numbers grow very quickly; for example, they are 12346, 274668 and 12005168 for $n$ being 8, 9 and 10, respectively. While solving the resulting program for $n=8$ is an easy task on any modern computer, the program for $n \geq 10$ seems out of reach, mainly because the SDP solvers need too much RAM. Yet solving such programs for as large $n$ as possible is desirable because they typically yield better bounds for the original combinatorial problems. We bypass the aforementioned memory requirements by linear programming with cutting-planes. Although solving semidefinite programs using this approach has no optimality guarantee, it turned out that in many flag algebra instances much less memory is needed to significantly improve bounds on numerous well-known hypergraph Turán problems. This is a joint work with Jan Volec.
