A branch-bound algorithm for a wiring problem

A simple computational method for solving a specific wiring problem related to the construction of the RC 4000 computer is described. The intimate relationship between the wiring problem and the traveling salesman problem is established, and the algorithm is based upon the branch and bound technique as employed by J.D.C. Little et al. [1] for solving the latter problem.Adapted from the thesis Fixed-cost and Other Network Flow Problems presented to The Institute of Mathematical Statistics and Operations Research, The Technical University of Denmark in partial fulfilment of the requirements for the licentiate degree, April 1967.     

A Lagrangian-based heuristic for large-scale set covering problems

We present a new Lagrangian-based heuristic for solving large-scale set-covering problems arising from crew-scheduling at the Italian Railways (Ferrovie dello Stato). Our heuristic obtained impressive results when compared to state-of-the-art codes on a test-bed provided by the company, which includes instances with sizes ranging from 50,000 variables and 500 constraints to 1,000,000 variables and 5000 constraints. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author.This research was performed while the author was affiliated with IASI, CNR and Dipartimento di Informatica e Sistemistica, Università di Roma, La Sapienza, Italy.This research was partially supported by National Research Program Metodi di Ottimizzazione per le Decisioni, MURST, Roma, Italy.