On Trivial and Binding Constraints in Programming Problems

Publisher Website
Google Scholar
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.

This publication has 0 references indexed in Scilit: