# Poster Session 2 – Thursday, May 20th

Poster

## Compact Formulations of Network Flow Problems

Presenter: Yulan Bai
Affiliation: Southern Methodist University
Co-authors: Eli Olinick, Ronald Rardin,Yuanyuan Dong, Andrew Yu
Abstract:

## A Benders-Type Approach For Robust Kidney Exchanges under Recourse

Presenter: Danny Blom
Affiliation: Eindhoven University of Technology
Co-authors: Christopher Hojny
Bart Smeulders
Abstract:
Kidney exchange programs (KEPs) play an important role in solving the shortage of the supply of kidney donors.
A graph problem related to KEPs is the problem of finding a packing of (bounded) cycles and chains in a digraph.
We consider a robust optimization model with recourse proposed by Carvalho et al. (2020) based on vertex failure, and propose a Benders approach for a specific subproblem
Computational results show a significant reduction of the running time compared to the state-of-the-art.

## On the Complexity of Recognizing Integrality and Total Dual Integrality of the {0,1/2}-Closure

Presenter: Matthias Brugger
Affiliation: Technische Universität München
Co-authors: Andreas S. Schulz
Abstract:
The {0,1/2}-closure of a rational polyhedron is obtained by adding all Gomory-Chvátal cuts that can be derived from the linear description of the polyhedron using multipliers 0 and 1/2 only. We show that deciding whether the {0,1/2}-closure coincides with the integer hull is strongly NP-hard. A direct consequence of our proof is that, testing whether the linear description of the {0,1/2}-closure is totally dual integral, is strongly NP-hard.

## Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints

Presenter: Ryan Cory-Wright
Affiliation: MIT
Co-authors: Dimitris Bertsimas, Jean Pauphilet
Abstract:
We propose a framework for modeling and solving low-rank optimization problems to certifiable optimality. We introduce symmetric projection matrices that satisfy Y^2=Y, the matrix analog of binary variables that satisfy z^2=z, to model rank constraints. By leveraging regularization and strong duality, we prove that this modeling paradigm yields tractable convex optimization problems over the non-convex set of orthogonal projection matrices. Furthermore, we design outer-approximation algorithms to solve low-rank problems to certifiable optimality, compute lower bounds via their semidefinite relaxations, and provide near-optimal solutions through rounding and local search techniques.

## Stable Set Congestion Games on Chordal Graphs

Presenter: Federico D’Onofrio
Affiliation: Sapienza University of Rome
Co-authors: Carla Michini
Abstract:
Let G = (V,E) be an undirected graph with positive weights w_v for each node v . A stable set in G is a subset of nodes any two of which are nonadjacent, and the Maximum Weighted Stable Set (MWSS) problem is the problem of finding the stable set in G of maximum weight. Stable Set Congestion (SSC) games are games of N players, each solving a MWSS problem on G. In such games each node weight is a nonincreasing function w_v : {1,…,N} → Z^+ over the number of players that select node v ∈ V , expressing the fact that a node might lose its value if many players use it. Our goal is to compute a Pure Nash Equilibrium (PNE) of SSC games, i.e., a strategy profile where no player has an incentive to unilaterally deviate from the stable set she selected.
The MWSS problem is NP-hard for general graphs, so the single players’ problems are NP-hard in the general case. In the special case of bipartite graphs, Del Pia et al. (2017) propose an aggregation/decomposition algorithm that computes a PNE of a SSC game in time polynomial in |V| and N . This algorithm crucially relies on the polyhedral description of the stable set polytope of G. In fact, the strategies of each player correspond to the binary vectors in a polytope P = {x : Ax ≤ b}, where A is a totally unimodular (TU) matrix. The original algorithm by Del Pia et al. has later been generalized by Kleer and Shafer (2020) to the case in which P is box totally dual integral (box-TDI) and has the Integer Decomposition Property.
Our main contribution is a further extension of this two-phase approach to the case of chordal graphs with bounded treewidth. We remark that the TU and box-TDI properties might not hold in this case. Precisely, we design an aggregation/decomposition algorithm that finds a PNE of a SSC game on a chordal graph with (fixed) treewidth k and runs in time polynomial in |V| and N . Our new aggregation algorithm is based on a dynamic programming approach that exploits a tree decomposition of the chordal graph, which can be computed in polynomial time. At the end of the aggregation phase, we obtain an aggregated strategy profile z* ∈ {0,1,…,N}^V which indicates how many players use each node (but does not specify the players’ identities). In the decomposition phase, we decompose z* into N stable sets. To do so, we formulate a weighted coloring problem, which for chordal graphs can be solved in polynomial time (Hoang, 1994).

## Fairmandering: A Column Generation Heuristic for Fairness Optimized Political Redistricting – Honorable Mention

Presenter: Wes Gurnee
Affiliation: Cornell
Co-authors: David B. Shmoys
Abstract:
We introduce a novel column generation heuristic for the political districting problem that is capable of optimizing for arbitrary political or demographic notions of fairness at unprecedented scales. In the largest ever ensemble study of congressional districts, we use our method to understand the range of possible expected outcomes and the implications of this range on potential definitions of fairness.

## Simple Iterative Methods for Linear Optimization over Convex Sets

Presenter: Sophie Huiberts
Affiliation: CWI
Co-authors: Daniel Dadush, Christopher Hojny, Stefan Weltge
Abstract:
We give simple iterative methods for computing approximately optimal primal and dual solutions for the problem of maximizing a linear functional over a convex set K given by a separation oracle. In contrast to prior work, our algorithms directly output primal and dual solutions and avoid a common requirement of binary search on the objective value.
Under the assumption that K contains a ball of radius r and is contained inside the origin centered ball of radius R, using O(R^4/r^2ε^2) iterations and calls to the oracle, our main method outputs a point x∈K together with a non-negative combination of the inequalities outputted by the oracle and one inequality of the R-ball certifying that x is an additive ε-approximate solution. In the setting where the inner r-ball is centered at the origin, we give a simplified variant which outputs a multiplicative (1+ε)-approximate primal and dual solutions using O(R^2/r^2ε^2) iterations and calls to the oracle. Similar results hold for packing type problems. Our methods are based on variants of the classical Von Neumann and Frank-Wolfe algorithms.
Our algorithms are also easy to implement, and we provide an experimental evaluation of their performance on a testbed of maximum matching and stable set instances. We further compare variations of our method to the standard cut loop implemented using Gurobi.This comparison reveals that in terms of iteration count, our methods converge on average faster than the standard cut loop on our test set.

## Exact and Approximation Algorithms for Sparse PCA

Presenter: Yongchun Li
Affiliation: Virginia Tech
Co-authors: Weijun Xie

## Early Termination of Convex QP Solvers in Mixed-Integer Programming for Real-Time Decision Making

Presenter: Jiaming Liang
Affiliation: Georgia Institute of Technology
Co-authors: Stefano Di Cairano, Rien Quirynen
Abstract:
The branch-and-bound optimization algorithm for mixed-integer model predictive control (MI-MPC) solves several convex quadratic program relaxations, but often the solutions are discarded based on already known integer feasible solutions. This work presents a projection and early termination strategy for infeasible interior point methods to reduce the computational effort of finding a globally optimal solution for MI-MPC. The method is shown to be also effective for infeasibility detection of the convex relaxations. We present numerical simulation results with a reduction of the total number of solver iterations by 42% for an MI-MPC example of decision making for automated driving with obstacle avoidance constraints.

## On perfect Roman domination in graphs

Presenter: Leonard Paleta
Affiliation: University of Southern Mindanao
Co-authors: Ferdinand P. Jamil
Abstract:
In this paper, we continue the study of perfect Roman domination on the join, corona, complementary prism, edge corona and composition in graphs.

## Memory-efficient approximation algorithms for Max-Cut and Max-k-Cut

Presenter: Nimita Shinde
Co-authors: Prof. Vishnu Narayanan, Indian Institute of Technology Bombay
Dr. James Saunderson, Monash University
Abstract:
Semidefinite programs (SDPs) are a special class of convex optimization problems that have wide applicability in combinatorial optimization. With increasing problem size, the memory required to solve SDPs becomes a key computational bottleneck. For a particularly large-scale problem, it might be prohibitive to even store the entire n x n dense matrix decision variable in core memory. To solve SDPs in this regime, we develop a randomized algorithm that returns a random vector whose covariance matrix is near-feasible and near-optimal for the SDP. We show how to develop such an algorithm by modifying the Frank-Wolfe algorithm to systematically replace the matrix iterates with random vectors. This essentially reduces the memory required to represent the decision variable from n^2 to n.

As an application of this approach, we show how to implement the Goemans-Williamson approximation algorithm for MaxCut using O(n) memory in addition to the memory required to store the problem instance. The proposed randomized algorithm generates a cut in polynomial time such that it satisfies the Goemans-Williamson approximation guarantees. We further show that it is possible to extend our approach to generate an approximate solution to Max-k-Cut, where the problem is to generate a k-cut on a graph G = (V,E) that maximizes the number of edges crossing the cut and whose natural SDP relaxation has n^2 constraints. More specifically, we apply an adaptation of our randomized algorithm to Max-k-Cut to generate a k-cut in polynomial time using O(|V|+|E|) memory. The generated k-cut satisfies the Frieze-Jerrum approximation guarantees. In general, we are also able to successfully generate and represent a near-optimal and near-feasible solution to an SDP with linear objective function and d linear constraints using O(n+d) memory.

## Sum of Squares Hierarchies for the Stability Number of a Graph – Competition Winner

Presenter: Luis Felipe Vargas
Affiliation: CWI
Co-authors: Monique Laurent
Abstract:
We investigate a hierarchy of semidefinite bounds $\vartheta^{(r)}(G)$ for the stability number $\alpha(G)$ of a graph $G$, based on its copositive programming formulation and introduced by de Klerk and Pasechnik [{\em SIAM J. Optim.} 12 (2002), pp.875–892], who conjectured convergence to $\alpha(G)$ in $r=\alpha(G)-1$ steps. Even the weaker conjecture claiming finite convergence is still open. We establish links between this hierarchy and sum-of-squares hierarchies based on the Motzkin-Straus formulation of $\alpha(G)$, which we use to show finite convergence when $G$ is acritical, i.e., when $\alpha(G\setminus e)=\alpha(G)$ for all edges $e$ of $G$. This relies, in particular, on understanding the structure of the minimizers of Motzkin-Straus formulation and showing that their number is finite precisely when $G$ is acritical. As a byproduct we show that deciding whether a standard quadratic program has finitely many minimizers does not admit a polynomial-time algorithm unless P=NP.

## Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints

Presenter: Qimeng Yu
Affiliation: Northwestern University
Co-authors: Simge Küçükyavuz

## On the Polyhedrality of Chvatal-Gomory Closure

Presenter: Haoran Zhu