Poster Session 2 – Thursday, May 20th


Compact Formulations of Network Flow Problems

Presenter: Yulan Bai
Affiliation: Southern Methodist University
Co-authors: Eli Olinick, Ronald Rardin,Yuanyuan Dong, Andrew Yu
The topic of my research is a compact formulation of network flow problems, called the triples formulation, applied to two combinatorial optimization problems: backhaul profit maximization problem and fixed charge network flow problem. Let’s imagine, you are a truck driver in a logistics company. Your normal job is to deliver cargo from Dallas to Houston. After finishing your last job in Houston, you need to come back to Dallas within 8 hours. With an empty truck and 8 hour time, what do you do? There are a lot of customers between Houston and Dallas. You can make extra money by making deliveries for them. But how to choose the customers and route to maximize your profit? Give me your data and I will give you the answer. This is the first part of my research: backhaul profit maximization problem, which is a routing problem with a goal of finding a route to maximize the total profit within limited capacity and time. To solve such a problem, we need to establish a mathematical model. Using the traditional network flow formulation, it takes hours to solve a 20-customer problem. Our contribution is made by building a more efficient model based on the triples formulation. In this way, we are able to reduce the general model size greatly and thus shorten the solving time tremendously. Furthermore, we develop effective algorithms to improve the performance of our model. Our experimental results show that our model can solve the 20-customer problems in just 20 seconds, which is hundreds of times faster than the traditional model. We can also solve a 30-customer problem, which is beyond the reach of the traditional model, in just 8 minutes. In conclusion, our compact model is much stronger and faster than the traditional model for the backhaul profit maximization problem. The second part of my research is compact formulation of the fixed charge network flow problem, which is a minimum cost network flow problem with variable and fixed costs on arcs with positive flow. There are two traditional formulations for this kind of problem, Base formulation and the multicommodity extended (MCE) formulation. By adding a singleton node to all of the demand nodes, we proved that our compact formulation is equivalent to the MCE formulation. We propose that by adding singleton nodes to some selected demand nodes, it is quite possible that our compact formulation can be faster than traditional MCE model, especially in large size problems. We have tested up to 500 benchmark instances on both single commodity and multiple commodity fixed charge network flow problems and concluded that our compact formulation is at least as good as the traditional advanced MCE formulation. In the future, we will explore singleton-selection strategies to further accelerate our solution approach.

A Benders-Type Approach For Robust Kidney Exchanges under Recourse

Presenter: Danny Blom
Affiliation: Eindhoven University of Technology
Co-authors: Christopher Hojny
Bart Smeulders
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
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
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
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
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
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
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
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
Affiliation: IITB-Monash Research Academy
Co-authors: Prof. Vishnu Narayanan, Indian Institute of Technology Bombay
Dr. James Saunderson, Monash University
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
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
Affiliation: University of Wisconsin-Madison
Chvatal-Gomory (CG) procedure was the first cutting-plane procedure has ever been introduced, and has been extensively investigated since then. Seminal result of Shrijver in 1980 showed that, for a rational polyhedron, its CG closure is also a rational polyhedron. Shrijver further asked, whether the CG closure of any irrational polytope is still a rational polytope? This long-standing open problem was answered in the affirmative by two groups of authors independently a few years ago. In fact, Dadush et al. proved that the CG closure of any compact convex set is a rational polytope. In this paper, we proposed an equivalent condition for the CG closure of any general closed convex set to be a rational polyhedron. Using such result, we are able to show that, for any closed convex set that can be written as the Minkowski sum of a compact convex set and a rational polyhedral cone, then its CG closure must be a rational polyhedron. This result naturally implies all the currently known results about the polyhedrality of CG closure.

On stability number of some Markovian random graphs

Presenter: Yiran Zhu
Affiliation: The University of Edinburgh
Co-authors: Dr. Akshay Gupte