Accession Number : AD0658740

Title :   DUALITY IN DISCRETE PROGRAMMING.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CALIF OPERATIONS RESEARCH HOUSE

Personal Author(s) : Balas,Egon

Report Date : AUG 1967

Pagination or Media Count : 36

Abstract : A duality theory is proposed for discrete programming. The mixed-integer programming problem is shown to be a special case of a minimax problem with a Lagrangian-type objective function, linear constraints, and some variables constrained to belong to an arbitrary set of real numbers. The dual of this problem is formulated as a problem of the same type, and such that the dual of the dual is the primal. It is shown that the primal has an optimal solution if and only if the dual has one, and in this case the values of their respective objective functions are equal. An optimal solution to the primal and the dual is shown to have the saddle-point property of optimal solutions to a pair of dual linear (and certain nonlinear) programs. A certain type of complementary slackness is shown to hold. Conditions for the uniqueness of a solution are examined. Finally, an economic interpretation is outlined in terms of a generalized shadow-prince system for mixed-integer programs.

Descriptors :   (*LINEAR PROGRAMMING, PROBLEM SOLVING), OPTIMIZATION, THEOREMS, STEEPEST DESCENT METHOD, REAL NUMBERS, MINIMAX TECHNIQUE, DECISION MAKING, ECONOMICS, MATHEMATICAL PROGRAMMING, OPERATIONS RESEARCH

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE