This paper addresses a multi-period investment model for capacity expansion in an uncertain environment. Using a scenario tree approach to model the evolution of uncertain demand and cost parameters, and fixed-charge cost functions to model the economies of scale in expansion costs, we develop a multi-stage stochastic integer programming formulation for the problem. A reformulation … Read more
In this paper we describe the results of a computational study towards the (re)optimization of signaling transfer points (STPs) in telecommunication networks. The best performance of an STP is achieved whenever the traffic load is evenly distributed among the internal components. Due to the continuously changing traffic pattern, the load of the components has to … Read more
We develop a method for generating valid convex polynomial inequalities for mixed 0-1 convex programs. We also show how these inequalities can be generated in the linear case by defining cut generation problems using a projection cone. The basic results for quadratic inequalities are extended to generate convex polynomial inequalities. Article Download View Generating Convex … Read more
We present a nontrivial family of facet-defining inequalities for the p-median polytope. We incorporate the inequalities in a branch-and-cut scheme, and we report computational results that demonstrate their effectiveness. Citation Department of Industrial Engineering, State University of New York at Buffalo, submitted Article Download View A Family of Facets for the p-Median Polytope
We present a family of inequalities that are valid for the generalized assignment polytope. Although the inequalities are not facet-defining in general, they define facets of a polytope of a relaxation. We report computational results on the use of the inequalities in a branch-and-cut scheme that demonstrate their effectiveness. Citation Department of Industrial Engineering, State … Read more
We present a polyhedral study of the complementarity knapsack problem, in which no auxiliary binary variables are introduced, but rather the inequalities are derived in the space of the continuous variables. Citation School of Industrial and Systems Engineering, GA Tech, under review Article Download View Facets of the Complementarity Knapsack Polytope
The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Some instances of size n >= 30 have remained unsolved for decades. The solution of these problems requires both improvements in mathematical programming algorithms and the utilization of powerful computational platforms. In this article we describe a novel approach to solve QAPs using … Read more
We study the use of binary variables in reformulating general mixed-integer linear programs. We show that binary reformulations result in problems for which almost all the binary variables replacing a general integer variable need to be explored during branching. We also give computational results on the performance of such reformulations in solving the mixed-integer programs, … Read more
The term Planning is not used in Operations Research in the sense that is most common in Artificial Intelligence. AI Planning does have many features in common with OR scheduling, sequencing, routing, and assignment problems, however. Current approaches to solving such problems can be broadly classified into four areas: Combinatorial Optimization, Integer Programming, Constraint Programming, … Read more
We describe a parallel, linear programming and implication based heuristic for solving set partitioning problems on distributed memory computer architectures. Our implementation is carefully designed to exploit parallelism to greatest advantage in advanced techniques like preprocessing and probing, primal heuristics, and cut generation. A primal-dual subproblem simplex method is used for solving the linear programming … Read more