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
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
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
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
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
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
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
We analyze two integer programming reformulations of the n-dimensional knapsack feasibility problem without assuming any structure on the weight vector $a.$ Both reformulations have a constraint matrix in which the columns form a reduced basis in the sense of Lenstra, Lenstra, and Lov\’asz. The nullspace reformulation of Aardal, Hurkens and Lenstra has n-1 variables, and … Read more
Lifting is a procedure for deriving valid inequalities for mixed-integer sets from valid inequalities for suitable restrictions of those sets. Lifting has been shown to be very effective in developing strong valid inequalities for linear integer programming and it has been successfully used to solve such problems with branch-and-cut algorithms. Here we generalize the theory … Read more
Stochastic dominance constraints allow a decision-maker to manage risk in an optimization setting by requiring their decision to yield a random outcome which stochastically dominates a reference random outcome. We present new integer and linear programming formulations for optimization under first and second-order stochastic dominance constraints, respectively. These formulations are more compact than existing formulations, … Read more