We present a scheme for generating new valid inequalities for mixed integer programs by taking pair-wise combinations of existing valid inequalities. Our scheme is related to mixed integer rounding and mixing. The scheme is in general sequence-dependent and therefore leads to an exponential number of inequalities. For some important cases, we identify combination sequences that … Read more
In this paper, we study the minimum converter wavelength assignment problem in optical networks. To benchmark the quality of solutions obtained by heuristics, we derive an integer programming formulation by generalizing the formulation of Mehrotra and Trick (1996) for the vertex coloring problem. To handle the exponential number of variables, we propose a column generation … Read more
Energy, a fundamental entity of modern life, is usually produced using fossil fuels as the primary raw material. A consequence of burning fossil fuels is the emission of environmentally harmful substances. Energy production systems generate steam and electricity that are served to different process customers to satisfy their energy requirement. The improvement of economical and … Read more
This paper presents a new data classification method based on mixed-integer programming. Traditional approaches that are based on partitioning the data sets into two groups perform poorly for multi-class data classification problems. The proposed approach is based on the use of hyper-boxes for defining boundaries of the classes that include all or some of the … Read more
We extend a static mixed intger diajunctive (MID) transmission expansion planning model so as to deal with circuit contingency criterion. The model simultaneously represents the network constraints for base case and each selected circuit contingency. The MID approach aloows a commercial optimization solver to achieve and prove solution aptimiality. The proposed approach is applied to … Read more
One of the main issues in the glass industry is the minimization of the trim loss generated when cutting large parts (stocks) into small items. In our application stocks are produced in the plant. Many distinct stock sizes are feasible, and technical constraints limit the variety of cutting patterns to those producing a single type … Read more
We consider knapsack constraints involving one general integer and many binary variables. We introduce the concept of a cover for such a constraint and we construct a new family of valid inequalities based on this concept. We generalize this idea to extended covers, and we propose a specialized lifting procedure for cover inequalities. Finally, we … Read more
This paper addresses a multi-stage stochastic integer programming formulation of the uncapacitated lot-sizing problem under uncertainty. We show that the classical (l,S) inequalities for the deterministic lot-sizing polytope are also valid for the stochastic lot-sizing polytope. We then extend the (l,S) inequalities to a general class of valid inequalities, called the (Q,S_Q) inequalities, and we … Read more
In this paper we use facets of mixed-integer sets with two and three variables to derive valid inequalities for integer sets defined by a single equation. These inequalities also define facets of the master cyclic group polyhedron of Gomory. Facets of this polyhedron give strong valid inequalities for general mixed-integer sets, such as the well-known … Read more
Decomposition algorithms such as Lagrangian relaxation and Dantzig-Wolfe decomposition are well-known methods that can be used to generate bounds for mixed-integer linear programming problems. Traditionally, these methods have been viewed as distinct from polyhedral methods, in which bounds are obtained by dynamically generating valid inequalities to strengthen the linear programming relaxation. Recently, a number of … Read more