The n-step mixed integer rounding (MIR) functions are used to generate n-step MIR inequalities for (mixed) integer programming problems (Kianfar and Fathi, 2006). We show that these functions are sources for generating extreme valid inequalities (facets) for group problems. We first prove the n-step MIR function, for any positive integer n, generates two-slope facets for … Read more
We present new families of valid inequalities for (mixed) integer programming (MIP) problems. These valid inequalities are based on a generalization of the 2-step mixed integer rounding (MIR), proposed by Dash and Günlük (2006). We prove that for any positive integer n, n facets of a certain (n+1)-dimensional mixed integer set can be obtained through … Read more
Gomory mixed-integer (GMI) cuts generated from optimal simplex tableaus are known to be useful in solving mixed-integer programs. Further, it is well-known that GMI cuts can be derived from facets of Gomory’s master cyclic group polyhedron and its mixed-integer extension studied by Gomory and Johnson. In this paper we examine why cutting planes derived from … Read more
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