Accession Number : AD0702811

Title :   AN APPLICATION OF DUALITY THEORY TO ZERO-ONE INTEGER PROGRAMS HAVING CONVEX OBJECTIVE FUNCTIONS.

Descriptive Note : Technical rept.,

Corporate Author : AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OHIO SCHOOL OF SYSTEMS AND LOGISTICS

Personal Author(s) : Muckstadt,John A.

Report Date : OCT 1969

Pagination or Media Count : 27

Abstract : The report contains a discussion of a zero-one integer programming algorithm for solving the following problem: min (f(x) : (b + Ax) > or = 0, (x sub j) = 0 or 1) where f(x) is a differentiable convex function, b is an m-vector, x is an n-vector and A is an mxn matrix. The algorithm is a generalization of one developed by Geoffrion for solving the above problem when f(x) is linear. The basic motivation for performing this research was a desire to construct an algorithm for solving an aircraft maintenance scheduling problem. Limited experimental experience is reported. The results of the tests indicate solution times increase approximately quadratically as a function of increasing the number of integer variables in the problem structure. (Author)

Descriptors :   (*AIR FORCE OPERATIONS, LOGISTICS), (*AIRCRAFT, MAINTENANCE), (*SCHEDULING, *MATHEMATICAL PROGRAMMING), ALGORITHMS

Subject Categories : Operations Research
      Logistics, Military Facilities and Supplies

Distribution Statement : APPROVED FOR PUBLIC RELEASE