Valid Linear Inequalities for Fixed Charge Problems

M. W. Padberg, T. J. Van Roy and L. A. Wolsey
Additional contact information
M. W. Padberg: New York University, New York, New York
T. J. Van Roy: Center for Operations Research and Econometrics, Louvain la Neuve, Belgium
L. A. Wolsey: Center for Operations Research and Econometrics, Louvain la Neuve, Belgium

Operations Research, 1985, vol. 33, issue 4, 842-861

Abstract: Many problems in the Operations Research/Management Science literature can be formulated with both zero-one and continuous variables. However, the exact optimization of such mixed zero-one models remains a computational challenge. In this paper, we propose to study mixed problems from a mathematical point of view that is similar in spirit to recent research on purely combinatorial problems that has investigated systems of defining linear inequalities (or facets of the underlying polytope). At least two numerical studies have validated this line of research computationally, and the advances in the problem-solving capabilities are considerable. We expect that similar gains are possible for the mixed zero-one problem. More precisely, we consider the mixed integer programs whose feasible region X is composed of (i) a simple additive constraint in the continuous variables x j , for j = 1, 2, …, n and (ii) constraints 0 ≤ x j ≤ m j y j defined by binary variables y j for j = 1, 2, …, n . This type of feasible region arises in a variety of mixed integer problems, and particularly in network problems with fixed charges on the arcs. We derive two classes of facet-defining linear inequalities of the convex hull of X , and show that the second of these classes gives a complete description of the convex hull when m j = m for all j . We also develop methods to detect violated inequalities from these classes, so that these facets can be used as cutting planes to strengthen the formulations of certain mixed integer problems.

Keywords: 490 valid inequalities for fixed charge networks; 634 valid inequalities for mixed integer problems (search for similar items in EconPapers)
Date: 1985
References: Add references at CitEc
Citations: View citations in EconPapers (36)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.33.4.842 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:33:y:1985:i:4:p:842-861

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().