Tightening simple mixed-integer sets with guaranteed bounds
We extend work on generating relaxations of simple sets with guaranteed bounds. CitationUnpublished. Columbia University, July 2008.ArticleDownload View PDF
integer programming
Extended Formulations for Packing and Partitioning Orbitopes
We give compact extended formulations for the packing and partitioning orbitopes (with respect to the full symmetric group) described and analyzed in Kaibel and Pfetsch (Math. Program. 114 (1), 2008, 1-36). These polytopes are the convex hulls of all 0/1-matrices with lexicographically sorted columns and at most, resp. exactly, one 1-entry per row. They are … Read more
A Branch-and-Price Algorithm for Combined Location and Routing Problems Under Capacity Restrictions
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
Experiments with Branching using General Disjunctions
Branching is an important component of the branch-and-cut algorithm for solving mixed integer linear programs. Most solvers branch by imposing a disjunction of the form“$x_i \leq k \vee x_i \geq k+1$” for some integer $k$ and some integer-constrained variable $x_i$. A generalization of this branching scheme is to branch by imposing a more general disjunction … Read more
Modelling Hop-Constrained and Diameter-Constrained Minimum Spanning Tree Problems as Steiner Tree Problems over Layered Graphs
The Hop-Constrained Minimum Spanning Tree Problem (HMSTP) is a NP-hard problem arising in the design of centralized telecommunication networks with quality of service constraints. We show that the HMSTP is equivalent to a Steiner Tree Problem (STP) in an adequate layered graph. We prove that the directed cut formulation for the STP defined in the … Read more
Algorithms for stochastic lot-sizing problems with backlogging
As a traditional model in the operations research and management science domain, lot-sizing problem is embedded in many application problems such as production and inventory planning and has been consistently drawing attentions from researchers. There is significant research progress on polynomial time algorithm developments for deterministic uncapacitated lot-sizing problems based on Wagner-and-Whitin property. However, in … Read more
New Turnpike Theorems for the Unbounded Knapsack Problem
We develop sharp bounds on turnpike theorems for the unbounded knapsack problem. Turnpike theorems specify when it is optimal to load at least one unit of the best item (i.e., the one with the highest “bang-for-buck” ratio) and, thus can be used for problem preprocessing. The successive application of the turnpike theorems can drastically reduce … Read more
A p-Cone Sequential Relaxation Procedure for 0-1 Integer Programs
Given a 0-1 integer programming problem, several authors have introduced sequential relaxation techniques — based on linear and/or semidefinite programming — that generate the convex hull of integer points in at most $n$ steps. In this paper, we introduce a sequential relaxation technique, which is based on $p$-order cone programming ($1 \le p \le \infty$). … Read more
Size constrained graph partitioning polytope. Part I: Dimension and trivial facets
We consider the problem of clustering a set of items into subsets whose sizes are bounded from above and below. We formulate the problem as a graph partitioning problem and propose an integer programming model for solving it. This formulation generalizes several well-known graph partitioning problems from the literature like the clique partitioning problem, the … Read more
Size constrained graph partitioning polytope. Part II: Non-trivial facets
We consider the problem of clustering a set of items into subsets whose sizes are bounded from above and below. We formulate the problem as a graph partitioning problem and propose an integer programming model for solving it. This formulation generalizes several well-known graph partitioning problems from the literature like the clique partitioning problem, the … Read more