AN APPLICATION OF DUALITY THEORY TO ZERO-ONE INTEGER PROGRAMS HAVING CONVEX OBJECTIVE FUNCTIONS.
AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OHIO SCHOOL OF SYSTEMS AND LOGISTICS
Pagination or Media Count:
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
- Operations Research
- Logistics, Military Facilities and Supplies