On Trivial and Binding Constraints in Programming Problems

J. C. G. Boot
Additional contact information
J. C. G. Boot: Netherlands School of Economics, Rotterdam

Management Science, 1962, vol. 8, issue 4, 419-441

Abstract: The present paper is concerned with the constraints which enter in programming problems in the form of linear inequalities. The solution of a programming problem consists of finding that point out of the points satisfying all constraints which maximizes some given objective function. Constraints may be trivial in the sense that, should we delete them, the set of points satisfying all (remaining) constraints does not increase. This notion is discussed in detail in Sections 1-5. Section 6, using the concept of a trivial constraint, proves concisely the main theorems of linear programming, known as the duality theorem and the existence theorem. Part 2 discusses binding constraints, i.e., constraints which are satisfied in equational form in the solution. The approach is based on the work of Theil-Van de Panne [Theil, H., C. van de Panne. 1960. Quadratic programming as an extension of conventional quadratic maximization. Management Sci. 7 (1) 1-20], which amounts to finding the set S of constraints such that, maximizing the objective function with all constraints belonging to S taken as strict equalities, the solution point is obtained. Rules are given in the work of Theil-Van de Panne to generate this set. One conclusion is that the set thus generated need not be unique in cases of "pathological" degeneracy. Another that trivial constraints may be binding! Numerical examples and figures illustrate the various anomalies.

Date: 1962
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.8.4.419 (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:ormnsc:v:8:y:1962:i:4:p:419-441

Access Statistics for this article

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