Column generation for solving linear programs with a huge number of variables alternates between solving a master problem and a pricing subproblem to add variables to the master problem as needed. The method is known to suffer from degeneracy of the master problem, exposing what is called the tailing-off effect. Inspired by recent advances in … Read more
We introduce the n-step conic MIR inequalities for the so-called polyhedral second-order conic (PSOC) mixed integer sets. PSOC sets arise in the polyhedral reformulation of the second-order conic mixed integer programs. Moreover, they are an equivalent representation for any mixed integer set defined by two linear constraints. The simple conic MIR inequalities of Atamtürk and … Read more
In this paper we study the t-branch split cuts introduced by Li and Richard (2008). They presented a family of mixed-integer programs with n integer variables and a single continuous variable and conjectured that the convex hull of integer solutions for any n has unbounded rank with respect to (n-1)-branch split cuts. It was shown … Read more
The corner relaxation of a mixed-integer linear program is a central concept in cutting plane theory. In a recent paper Fischetti and Monaci provide an empirical assessment of the strength of the corner and other related relaxations on benchmark problems. In this paper we give a precise characterization of the bounds given by these relaxations … Read more
Gunluk and Pochet [O. Gunluk, Y. Pochet: Mixing mixed integer inequalities. Mathematical Programming 90(2001) 429-457] proposed a procedure to mix mixed integer rounding (MIR) inequalities. The mixed MIR inequalities define the convex hull of the mixing set $\{(y^1,\ldots,y^m,v) \in Z^m \times R_+:\alpha_1 y^i + v \geq \b_i,i=1,\ldots,m\}$ and can also be used to generate valid … Read more
This paper introduces the PuLP library, an open source package that allows mathematical programs to be described in the Python computer programming language. PuLP is a high-level modelling library that leverages the power of the Python language and allows the user to create programs using expressions that are natural to the Python language, avoiding special … Read more
In this paper we study the relationship between valid inequalities for mixed-integer sets, lattice-free sets associated with these inequalities and the multi-branch split cuts introduced by Li and Richard (2008). By analyzing $n$-dimensional lattice-free sets, we prove that for every integer $n$ there exists a positive integer $t$ such that every facet-defining inequality of the … Read more
We study a mixed integer linear program with $m$ integer variables and $k$ non-negative continuous variables in the form of the relaxation of the corner polyhedron that was introduced by Andersen, Louveaux, Weismantel and Wolsey [\emph{Inequalities from two rows of a simplex tableau}, Proc.\ IPCO 2007, LNCS, vol.~4513, Springer, pp.~1–15]. We describe the facets of … Read more
In this paper, we examine a mixed integer linear programming (MIP) reformulation for mixed integer bilinear problems where each bilinear term involves the product of a nonnegative integer variable and a nonnegative continuous variable. This reformulation is obtained by first replacing a general integer variable with its binary expansion and then using McCormick envelopes to … Read more
In a recent paper, Dash, Dey and Gunluk (2010) showed that many families of inequalities for the two-row continuous group relaxation and variants of this relaxation are cross cuts or crooked cross cuts, both of which generalize split cuts. Li and Richard (2008) recently studied t-branch split cuts for mixed-integer programs for integers t >= … Read more