A hybrid approach to discrete mathematical programming

The dynamic programming and branch-and-bound approaches are combined to produce a hybrid algorithm for separable discrete mathematical programs. Linear programming is used in a novel way to compute bounds. Every simplex pivot permits a bounding test to be made on every active node in the search tree. Computational experience is reported.     

A reduced-gradient variant of Karmarkar's algorithm and null-space projections

This paper discusses the relationship between Karmarkar's new method for linear programming and the traditional simplex method. It is shown how null-space Karmarkar projections can be done using a basis matrix to compute the projections in the null space. Preliminary computational evidence shows that problems exist in the choice of a basis matrix, but that, given a basis, very inexact and computationally efficient projections are computationally sound.     

The fleet assignment problem: Solving a large-scale integer program

Given a flight schedule and set of aircraft, the fleet assignment problem is to determine which type of aircraft should fly each flight segment. This paper describes a basic daily, domestic fleet assignment problem and then presents chronologically the steps taken to solve it efficiently. Our model of the fleet assignment problem is a large multi-commodity flow problem with side constraints defined on a time-expanded network. These problems are often severely degenerate, which leads to poor performance of standard linear programming techniques. Also, the large number of integer variables can make finding optimal integer solutions difficult and time-consuming. The methods used to attack this problem include an interior-point algorithm, dual steepest edge simplex, cost perturbation, model aggregation, branching on set-partitioning constraints and prioritizing the order of branching. The computational results show that the algorithm finds solutions with a maximum optimality gap of 0.02% and is more than two orders of magnitude faster than using default options of a standard LP-based branch-and-bound code.This work was supported by NSF and AFORS grant DDM-9115768 and NSF grant SES-9122674.Corresponding author.     

Computational experience with a globally convergent primal—dual predictor—corrector algorithm for linear programming

Kojima, Megiddo, and Mizuno proved global convergence of a primal—dual algorithm that corresponds to methods used in practice. Here, the numerical efficiency of a predictor—corrector extension of that algorithm is tested. Numerical results are extremely positive, indicating that the safety of a globally convergent algorithm can be obtained at little computational cost. The algorithm is tested on infeasible problems with less success. Finally, the algorithm is applied to a warm started problem, with very encouraging preliminary results.Corresponding author. The research of this author is sponsored by the Air Force Office of Scientific Research, Air Force System Command under Grant AFOSR-92-J0046. The United States Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notations thereon.