The Set Covering Problem Revisited: An Empirical Study of the Value of Dual Information

This paper investigates the role of dual information on the performances of heuristics designed for solving the set covering problem. After solving the linear programming relaxation of the problem, the dual information is used to obtain the two main approaches proposed here: (i) The size of the original problem is reduced and then the resulting … Read more

Simultaneous Column-and-Row Generation for Large-Scale Linear Programs with Column-Dependent-Rows

In this paper, we develop a simultaneous column-and-row generation algorithm that could be applied to a general class of large-scale linear programming problems. These problems typically arise in the context of linear programming formulations with exponentially many variables. The defining property for these formulations is a set of linking constraints, which are either too many … Read more

On EOQ Cost Models with Arbitrary Purchase and Transportation Costs

We analyze an economic order quantity cost model with unit out-of-pocket holding costs, unit opportunity costs of holding, fixed ordering costs, and general purchase-transportation costs. We identify the set of purchase-transportation cost functions for which this model is easy to solve and related to solving a one-dimensional convex minimization problem. For the remaining purchase-transportation cost … Read more

A Hybrid Shifting Bottleneck-Tabu Search Heuristic for the Job Shop Total Weighted Tardiness Problem

In this paper, we study the job shop scheduling problem with the objective of minimizing the total weighted tardiness. We propose a hybrid shifting bottleneck – tabu search (SB-TS) algorithm by replacing the reoptimization step in the shifting bottleneck (SB) algorithm by a tabu search (TS). In terms of the shifting bottleneck heuristic, the proposed … Read more