Recently, several classes of cutting planes have been introduced for binary polynomial optimization. In this paper, we present the first results connecting the combinatorial structure of these inequalities with their Chvátal rank. We determine the Chvátal rank of all known cutting planes and show that almost all of them have Chvátal rank 1. We observe that these inequalities have an associated hypergraph that is βacyclic. Our second goal is to derive deeper cutting planes; to do so, we consider hypergraphs that admit βcycles. We introduce a novel class of valid inequalities arising from odd βcycles, that generally have Chvátal rank 2. These inequalities allow us to obtain the first characterization of the multilinear polytope for hypergraphs that contain βcycles. Namely, we show that the multilinear polytope for cycle hypergraphs is given by the standard linearization inequalities, flower inequalities, and odd βcycle inequalities. We also prove that odd βcycle inequalities can be separated in linear time when the hypergraph is a cycle hypergraph. This shows that instances represented by cycle hypergraphs can be solved in polynomial time. Last, to test the strength of odd βcycle inequalities, we perform numerical experiments that imply that they close a significant percentage of the integrality gap.
more »
« less
On the complexity of binary polynomial optimization over acyclic hypergraphs
In this work we advance the understanding of the fundamental limits of computation for Binary Polynomial Optimization (BPO), which is the problem of maximizing a given polynomial function over all binary points. In our main result we provide a novel class of BPO that can be solved efficiently both from a theoretical and computational perspective. In fact, we give a strongly polynomialtime algorithm for instances whose corresponding hypergraph is βacyclic. We note that the βacyclicity assumption is natural in several applications including relational database schemes and the lifted multicut problem on trees. Due to the novelty of our proving technique, we obtain an algorithm which is interesting also from a practical viewpoint. This is because our algorithm is very simple to implement and the running time is a polynomial of very low degree in the number of nodes and edges of the hypergraph. Our result completely settles the computational complexity of BPO over acyclic hypergraphs, since the problem is NPhard on αacyclic instances. Our algorithm can also be applied to any general BPO problem that contains βcycles. For these problems, the algorithm returns a smaller instance together with a rule to extend any optimal solution of the smaller instance to an optimal solution of the original instance.
more »
« less
 Award ID(s):
 1634768
 NSFPAR ID:
 10330008
 Date Published:
 Journal Name:
 Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
 ISSN:
 15579468
 Page Range / eLocation ID:
 2684  2699
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


We study the classic Maximum Independent Set problem under the notion of stability introduced by Bilu and Linial (2010): a weighted instance of Independent Set is γstable if it has a unique optimal solution that remains the unique optimal solution under multiplicative perturbations of the weights by a factor of at most γ ≥ 1. The goal then is to efficiently recover this “pronounced” optimal solution exactly. In this work, we solve stable instances of Independent Set on several classes of graphs: we improve upon previous results by solving \tilde{O}(∆/sqrt(log ∆))stable instances on graphs of maximum degree ∆, (k − 1)stable instances on kcolorable graphs and (1 + ε)stable instances on planar graphs (for any fixed ε > 0), using both combinatorial techniques as well as LPs and the SheraliAdams hierarchy. For general graphs, we give an algorithm for (εn)stable instances, for any fixed ε > 0, and lower bounds based on the planted clique conjecture. As a byproduct of our techniques, we give algorithms as well as lower bounds for stable instances of Node Multiway Cut (a generalization of Edge Multiway Cut), by exploiting its connections to Vertex Cover. Furthermore, we prove a general structural result showing that the integrality gap of convex relaxations of several maximization problems reduces dramatically on stable instances. Moreover, we initiate the study of certified algorithms for Independent Set. The notion of a γcertified algorithm was introduced very recently by Makarychev and Makarychev (2018) and it is a class of γapproximation algorithms that satisfy one crucial property: the solution returned is optimal for a perturbation of the original instance, where perturbations are again multiplicative up to a factor of γ ≥ 1 (hence, such algorithms not only solve γstable instances optimally, but also have guarantees even on unstable instances). Here, we obtain ∆certified algorithms for Independent Set on graphs of maximum degree ∆, and (1 + ε)certified algorithms on planar graphs. Finally, we analyze the algorithm of Berman and Fürer (1994) and prove that it is a ((∆+1)/3 + ε)certified algorithm for Independent Set on graphs of maximum degree ∆ where all weights are equal to 1.more » « less

Carbone, Alessandra ; ElKebir, Mohammed (Ed.)Cell signaling pathways, which are a series of reactions that start at receptors and end at transcription factors, are basic to systems biology. Properly modeling the reactions in such pathways requires directed hypergraphs, where an edge is now directed between two sets of vertices. Inferring a pathway by the most parsimonious series of reactions then corresponds to finding a shortest hyperpath in a directed hypergraph, which is NPcomplete. The state of the art for shortest hyperpaths in cellsignaling hypergraphs solves a mixedinteger linear program to find an optimal hyperpath that is restricted to be acyclic, and offers no efficiency guarantees. We present for the first time a heuristic for general shortest hyperpaths that properly handles cycles, and is guaranteed to be efficient. Its accuracy is demonstrated through exhaustive experiments on all instances from the standard NCIPID and Reactome pathway databases, which show the heuristic finds a hyperpath that matches the stateoftheart mixedinteger linear program on over 99% of all instances that are acyclic. On instances where only cyclic hyperpaths exist, the heuristic surpasses the stateoftheart, which finds no solution; on every such cyclic instance, enumerating all possible hyperpaths shows that the solution found by the heuristic is in fact optimal.more » « less

The offline pickup and delivery problem with time windows (PDPTW) is a classical combinatorial optimization problem in the transportation community, which has proven to be very challenging computationally. Due to the complexity of the problem, practical problem instances can be solved only via heuristics, which tradeoff solution quality for computational tractability. Among the various heuristics, a common strategy is problem decomposition, that is, the reduction of a largescale problem into a collection of smaller subproblems, with spatial and temporal decompositions being two natural approaches. While spatial decomposition has been successful in certain settings, effective temporal decomposition has been challenging due to the difficulty of stitching together the subproblem solutions across the decomposition boundaries. In this work, we introduce a novel temporal decomposition scheme for solving a class of PDPTWs that have narrow time windows, for which it is able to provide both fast and highquality solutions. We utilize techniques that have been popularized recently in the context of online dialaride problems along with the general idea of rolling horizon optimization. To the best of our knowledge, this is the first attempt to solve offline PDPTWs using such an approach. To show the performance and scalability of our framework, we use the optimization of paratransit services as a motivating example. Due to the lack of benchmark solvers similar to ours (i.e., temporal decomposition with an online solver), we compare our results with an offline heuristic algorithm using Google ORTools. In smaller problem instances (with an average of 129 requests per instance), the baseline approach is as competitive as our framework. However, in larger problem instances (approximately 2,500 requests per instance), our framework is more scalable and can provide good solutions to problem instances of varying degrees of difficulty, while the baseline algorithm often fails to find a feasible solution within comparable compute times.more » « less

Since the early days of relational databases, it was realized that acyclic hypergraphs give rise to database schemas with desirable structural and algorithmic properties. In a bynow classical paper, Beeri, Fagin, Maier, and Yannakakis established several different equivalent characterizations of acyclicity; in particular, they showed that the sets of attributes of a schema form an acyclic hypergraph if and only if the localtoglobal consistency property for relations over that schema holds, which means that every collection of pairwise consistent relations over the schema is globally consistent. Even though reallife databases consist of bags (multisets), there has not been a study of the interplay between local consistency and global consistency for bags. We embark on such a study here and we first show that the sets of attributes of a schema form an acyclic hypergraph if and only if the localtoglobal consistency property for bags over that schema holds. After this, we explore algorithmic aspects of global consistency for bags by analyzing the computational complexity of the global consistency problem for bags: given a collection of bags, are these bags globally consistent? We show that this problem is in NP, even when the schema is part of the input. We then establish the following dichotomy theorem for fixed schemas: if the schema is acyclic, then the global consistency problem for bags is solvable in polynomial time, while if the schema is cyclic, then the global consistency problem for bags is NPcomplete. The latter result contrasts sharply with the state of affairs for relations, where, for each fixed schema, the global consistency problem for relations is solvable in polynomial time.more » « less