We define the inclusion certificate as a measure that expresses each point in the domain of a collection of functions as a convex combination of other points in the domain. Using inclusion certificates, we extend the convex extensions theory to enable simultaneous convexification of functions. We discuss conditions under which the domain of the functions … Read more
Ryser’s conjecture postulates that, for $r$-partite hypergraphs, $\tau \leq (r-1) \nu$ where $\tau$ is the covering number of the hypergraph and $\nu$ is the matching number. Although this conjecture has been open since the 1960s, researchers have resolved it for special cases such as for intersecting hypergraphs where $r \leq 5$. In this paper, we … Read more
We compute a complete linear description of the bipartite subgraph polytope, for up to seven nodes, and a conjectured complete description for eight nodes. We then show how these descriptions were used to compute the integrality ratio of various relaxations of the max-cut problem, again for up to eight nodes. CitationL. Galli & A.N. Letchford … Read more
Given a directed graph $G$ with non negative cost on the arcs, a directed tree cover of $G$ is a directed tree such that either head or tail (or both of them) of every arc in $G$ is touched by $T$. The minimum directed tree cover problem (DTCP) is to find a directed tree cover … Read more
We present in this paper new results on the duality gap between the binary quadratic optimization problem and its Lagrangian dual or semidefinite programming relaxation. We first derive a necessary and sufficient condition for the zero duality gap and discuss its relationship with the polynomial solvability of the primal problem. We then characterize the zeroness … Read more
In recent years, there has been an increased literature on so-called Generalized Network Design Problems, such as the Generalized Minimum Spanning Tree Problem and the Generalized Traveling Salesman Problem. In such problems, the node set of a graph is partitioned into clusters, and the feasible solutions must contain one node from each cluster. Up to … Read more
We consider the positive semidefinite (psd) matrices with binary entries, along with the corresponding integer polytopes. We begin by establishing some basic properties of these matrices and polytopes. Then, we show that several families of integer polytopes in the literature — the cut, boolean quadric, multicut and clique partitioning polytopes — are faces of binary … Read more
We study the version of the asymmetric prize collecting traveling salesman problem, where the objective is to find a directed tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. In \cite{Amico}, the authors … Read more
The NP-hard Maximum Monomial Agreement (MMA) problem consists of finding a single logical conjunction that best fits a weighted dataset of “positive” and “negative” binary vectors. Computing classifiers using boosting methods involves a maximum agreement subproblem at each iteration, although such subproblems are typically solved by heuristic methods. Here, we describe an exact branch and … Read more
Computing the 1-width of the incidence matrix of a Steiner Triple System gives rise to small set covering instances that provide a computational challenge for integer programming techniques. One major source of difficulty for instances of this family is their highly symmetric structure, which impairs the performance of most branch-and-bound algorithms. The largest instance in … Read more