As an alternative to traditional integer programming (IP), decision diagrams (DDs) provide a new solution technology for discrete problems based on their combinatorial structure and dynamic programming representation. While the literature mainly focuses on the competitive aspects of DDs as a stand-alone solver, we investigate their complementary role by studying IP techniques that can be … Read more
We investigate new convex relaxations for the pooling problem, a classic nonconvex production planning problem in which input materials are mixed in intermediate pools, with the outputs of these pools further mixed to make output products meeting given attribute percentage requirements. Our relaxations are derived by considering a set which arises from the formulation by … Read more
Making cut generating functions (CGFs) computationally viable is a central question in modern integer programming research. One would like to nd CGFs that are simultaneously good, i.e., there are good guarantees for the cutting planes they generate, and ecient, meaning that the values of the CGFs can be computed cheaply (with procedures that have some … Read more
We study network models where flows cannot be split or merged when passing through certain nodes, i.e., for such nodes, each incoming arc flow must be matched to an outgoing arc flow of identical value. This requirement, which we call “no-split no-merge” (NSNM), appears in railroad applications where train compositions can only be modified at … Read more
Extreme events such as disasters cause partial or total disruption of basic services such as water, energy, communication and transportation. In particular, roads can be damaged or blocked by debris, thereby obstructing access to certain affected areas. Thus, restoration of the damaged roads is necessary to evacuate victims and distribute emergency commodities to relief centers … Read more
We present a new tool for generating cutting planes for NP-hard combinatorial optimisation problems. It is based on the concept of gadgets — small subproblems that are “glued” together to form hard problems — which we borrow from the literature on computational complexity. Using gadgets, we are able to derive huge (exponentially large) new families … Read more
We analyze different ways of constructing binary extended formulations of polyhedral mixed-integer sets with bounded integer variables and compare their relative strength with respect to split cuts. We show that among all binary extended formulations where each bounded integer variable is represented by a distinct collection of binary variables, what we call “unimodular” extended formulations … Read more
In this paper, we study the strength of aggregation cuts for sign-pattern integer programs (IPs). Sign-pattern IPs are a generalization of packing IPs and are of the form {x \in Z^n | Ax = 0} where for a given column j, A_{ij} is either non-negative for all i or non-positive for all i. Our first … Read more
We study quantitative criteria for evaluating the strength of valid inequalities for Gomory and Johnson’s finite and infinite group models and we describe the valid inequalities that are optimal for these criteria. We justify and focus on the criterion of maximizing the volume of the nonnegative orthant cut off by a valid inequality. For the … Read more
In a recent paper, Basu, Hildebrand, and Molinaro established that the set of continuous minimal functions for the 1-dimensional Gomory-Johnson infinite group relaxation possesses a dense subset of extreme functions. The n-dimensional version of this result was left as an open question. In the present paper, we settle this query in the affirmative: for any … Read more