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

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)

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1969
Accession Number
AD0702811

Entities

People

  • John A. Muckstadt

Organizations

  • Air Force Institute of Technology

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Aircraft Maintenance
  • Aircrafts
  • Airframes
  • Algorithms
  • Computer Programming
  • Evolutionary Algorithms
  • Heuristic Methods
  • Integer Programming
  • Maintenance
  • Mathematics
  • Mechanical Structure
  • Motivation
  • Scheduling (Production)

Fields of Study

  • Mathematics

Readers

  • Linear Algebra
  • Operations Research