Branching is an important component of branch-and-bound algorithms for solving mixed integer linear programs. We consider the problem of selecting, at each iteration of the branch-and-bound algorithm, a general branching disjunction of the form $“\pi x \leq \pi_0 \vee \pi x \geq \pi_0 + 1”$, where $\pi, \pi_0$ are integral. We show that the problem … Read more
We discuss two formulations of the Pattern Minimization Problem: (1) introduced by Vanderbeck, and (2) obtained adding setup variables to the cutting stock formulation by Gilmore-Gomory. Let $z_i^{LP}(u)$ be the bound given by the linear relaxation of ($i$) under a given vector $u = (u_k)$ of parameters. We show that $z_2^{LP}(u}) \ge z_1^{LP}(u)$ and provide … Read more
We study the modeling of non-convex piecewise linear functions as Mixed Integer Programming (MIP) problems. We review several new and existing MIP formulations for continuous piecewise linear functions with special attention paid to multivariate non-separable functions. We compare these formulations with respect to their theoretical properties and their relative computational performance. In addition, we study … Read more
In this note, we present a simple geometric argument to determine a lower bound on the split rank of intersection cuts. As a first step of this argument, a polyhedral subset of the lattice-free convex set that is used to generate the intersection cut is constructed. We call this subset the restricted lattice-free set. It … Read more
We study the mixing inequalities which were introduced by Gunluk and Pochet (2001). We show that a mixing inequality which mixes n MIR inequalities has MIR rank at most n if it is a type I mixing inequality and at most n-1 if it is a type II mixing inequality. We also show that these … Read more
Within the context of solving Mixed-Integer Linear Programs by a Branch-and-Cut algorithm, we propose a new strategy for branching. Computational experiments show that, on the majority of our test instances, this approach enumerates fewer nodes than traditional branching. On average, on instances that contain both integer and continuous variables the number of nodes in the … Read more
Integer programs defined by two equations with two free integer variables and nonnegative continuous variables have three types of nontrivial facets: split, triangle or quadrilateral inequalities. In this paper, we compare the strength of these three families of inequalities. In particular we study how well each family approximates the integer hull. We show that, in … Read more
We investigate the problem of simultaneously determining the location of facilities and the design of vehicle routes to serve customer demands under vehicle and facility capacity restrictions. We present a set-partitioning-based formulation of the problem and study the relationship between his formulation and the graph-based formulations that have been used in previous studies of this … Read more
Recently, Andersen et al.(2007), Borozan and Cornuejols (2007) and Cornuejols and Margot(2007) characterized extreme inequalities of a system of two rows with two free integer variables and nonnegative continuous variables. These inequalities are either split cuts or intersection cuts (Balas (1971)) derived using maximal lattice-free convex sets. In order to use these inequalities to obtain … Read more
This paper shows how valid inequalities based on the mixing set can be used in a mixed integer programming (MIP) solver. It discusses the relation of mixing inequalities to flow path and mixed integer rounding in- equalities and how currently used separation algorithms already generate cuts implicitly that can be seen as mixing cuts. Further … Read more