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):

Report Date:

1969-10-01

Pagination or Media Count:

27.0

Abstract:

The report contains a discussion of a zero-one integer programming algorithm for solving the following problem min fx b Ax or 0, x sub j 0 or 1 where fx 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 fx 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

Subject Categories:

  • Operations Research
  • Logistics, Military Facilities and Supplies

Distribution Statement:

APPROVED FOR PUBLIC RELEASE