We propose an approximate lifting procedure for general integer programs. This lifting procedure uses information from multiple constraints of the problem formulation and can be used to strengthen formulations and cuts for mixed integer programs. In particular we demonstrate how it can be applied to improve Gomory’s fractional cut which is central to Glover’s primal … Read more
In this paper, we derive new families of piecewise linear facet-defining inequalities for the finite group problem and extreme inequalities for the infinite group problem using approximate lifting. The new valid inequalities for the finite group problem are two- and three-slope facet-defining inequalities as well as the first family of four-slope facet-defining inequalities. The new … Read more
This paper introduces the single item lot sizing problem with inventory gains. This problem is a generalization of the classical single item capacitated lot sizing problem to one in which stock is not conserved. That is, the stock in inventory undergoes a transformation in each period that is independent of the period in which the … Read more
In this paper we derive new properties of extreme inequalities for infinite group problems. We develop tools to prove that given valid inequalities for the infinite group problem are extreme. These results show that integer infinite group problems have discontinuous extreme inequalities. These inequalities are strong when compared to related classes of continuous extreme inequalities. … Read more
In this paper we present a centralized model for managing, at the same time, the dayahead energy market and the reserve market in order to price through the market, beside energy, the overall cost of reliability and to assure that the power grid survives the failure of any single components, so to avoid extended blackouts. … Read more
We identify the best root node strategy for the approximation of the time-indexed bound in min-sum scheduling by sorting through various options that involve the primal simplex, dual simplex, and barrier methods for linear programming, the network simplex method for network flow problems, and Dantzig-Wolfe decomposition and column generation. CitationSubmitted for publication.ArticleDownload View PDF
In this paper, we lay the foundation for the study of the two-dimensional mixed integer infinite group problem (2DMIIGP). We introduce tools to determine if a given continuous and piecewise linear function over the two-dimensional infinite group is subadditive and to determine whether it defines a facet. We then present two different constructions that yield … Read more
This report combines the contributions to INOC 2005 (Wessälly et al., 2005) and DRCN 2005 (Gruber et al., 2005). A new integer linear programming model for the end-to-end survivability concept deman d-wise shared protection (DSP) is presented. DSP is based on the idea that backup capacity is dedicated to a particular demand, but shared within … Read more
We present mixed integer linear programming models that are robust in the face of uncertain traffic demands known to lie in a certain polyhedron for the problem of dense wavelength division multiplexing network routing and provisioning at minimal cost. We investigate the solution of the problem in a set of numerical experiments for two models … Read more
Working with an integer bilinear programming formulation of a one-dimensional cutting-stock problem, we develop an ILP-based local-search heuristic. The ILPs holistically integrate the master and subproblem of the usual price driven pattern-generation paradigm, resulting in a unified model that generates new patterns in situ. We work harder to generate new columns, but we are guaranteed … Read more