A branch-and-price algorithm for the stochastic generalized assignment problem

David P. Morton, Jonathan F. Bard, Yong Min Wang

Research output: Chapter in Book/Report/Conference proceedingChapter

1 Scopus citations

Abstract

In this chapter, we investigate the generalized assignment problem with the objective of finding a minimum-cost assignment of jobs to agents subject to capacity constraints. A complicating feature of the model is that the coefficients for resource consumption and capacity are random. The problem is formulated as a stochastic integer program with a penalty term associated with the violation of the resource constraints and is solved with a branch-and-price algorithm that combines column generation with branch and bound. To speed convergence, a stabilization procedure is included. The performance of the methodology was tested on four classes of randomlygenerated instances. The principal results showed that the value of the stochastic solution (V SS), i.e., the gap between the stochastic solution and the expected value solution, was 35.5% on average. At the root node of the search tree, it was found that the linear programming relaxation of the master problem associated with column generation provided a much tighter lower bound than the relaxation of the original constraint-based formulation. In fact, two thirds of the test problems evidenced no gap between the optimal integer solution and the relaxed master problem solution. Additional testing showed that (1) initializing the master problem with a feasible solution outperforms the classical big-M approach; (2) SOS type 1 branching is superior to single-variable branching; and, (3) variable fixing based on reduced costs provides only a slight decrease in runtimes.

Original languageEnglish (US)
Title of host publicationComputational Optimization
Subtitle of host publicationNew Research Developments
PublisherNova Science Publishers, Inc.
Pages207-236
Number of pages30
ISBN (Electronic)9781612094397
ISBN (Print)9781606926710
StatePublished - Jan 1 2010

Keywords

  • Branch and price
  • Generalized assignment problem
  • Stochastic integer programming

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'A branch-and-price algorithm for the stochastic generalized assignment problem'. Together they form a unique fingerprint.

Cite this