A hierarchy of relaxations for linear generalized disjunctive programming

A hierarchy of relaxations for linear generalized disjunctive programming

0.00 Avg rating0 Votes
Article ID: iaor20119353
Volume: 216
Issue: 1
Start Page Number: 70
End Page Number: 82
Publication Date: Jan 2012
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: integer
Abstract:

Generalized disjunctive programming (GDP) is an extension of the well-known disjunctive programming paradigm developed by Balas in the mid 70s. This mathematical representation of discrete-continuous optimization problems, which represents an alternative to the mixed-integer program (MIP), led to the development of customized algorithms that successfully exploited the underlying logical structure of the problem. The underlying theory of these methods, however, borrowed only in a limited way from the theories of disjunctive programming, and the unique insights from Balas’ work have not been fully exploited. In this paper, we establish new connections between the fields of disjunctive programming and generalized disjunctive programming for the linear case. We then propose a novel hierarchy of relaxations to the original linear GDP model that subsumes known relaxations for this model, and show that a subset of these relaxations are tighter than the latter. We discuss the usefulness of these relaxations within the context of MIP and illustrate these results on the classic strip-packing problem.

Reviews

Required fields are marked *. Your email address will not be published.