Poster Session 2 – Thursday, May 20th

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.

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.

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).

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.

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.

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.