INFORMS Journal on Computing articles from January 2000

INFORMS Journal on Computing archives from January 2000

Progress in linear programming-based algorithms for integer programming: an exposition.
January 1, 2000... This paper is about modeling and solving mixed integer programming (MIP) problems. In the last decade, the use of mixed integer programming models has increased dramatically. Fifteen years ago, mainframe computers were required to solve...

Statistical analysis of computational tests of algorithms and heuristics.
January 1, 2000... Statistical analysis is a powerful tool to apply when evaluating the performance of computer implementations of algorithms and heuristics. Yet many computational studies in the literature do not use this tool to maximum effectiveness. This...

Parallelizing the dual simplex method.
January 1, 2000... We study the parallelization of the steepest-edge version of the dual simplex algorithm. Three different parallel implementations are examined, each of which is derived from the CPLEX dual simplex implementation. One alternative uses PVM, one...

When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)?
January 1, 2000... We derive results of the following flavor: If a combinatorial optimization problem can be formulated via a dynamic program of a certain structure and if the involved cost and transition functions satisfy certain arithmetical and structural...

A minimal algorithm for the bounded knapsack problem.
January 1, 2000... The Bounded Knapsack Problem (BKP) is a generalization of the 0-1 Knapsack Problem where a bounded amount of each item type is available. Currently, the most efficient algorithm for BKP transforms the data instance to an equivalent 0-1 Knapsack...