The multiperiod assignment problem: A multicommodity network flow model and specialized branch and bound algorithm
type: Item
instance of: scholarly article
title: The multiperiod assignment problem: A multicommodity network flow model and specialized branch and bound algorithm
zbMATH Open document ID: 0582.90074
DOI: 10.1016/0377-2217(86)90302-4
author: Jay E. Aronson
published in: European Journal of Operational Research
publication date: 1986-01-01T00:00:00Z
review text: The multiperiod assignment problem, a specialization of the three dimensional assignment problem, is an optimization model that describes the situation of assigning people to activities, or jobs over time. We consider the most general case which has both a cost of assigning a person to an activity in each time period, and a cost of transferring the person from one activity in each period to another activity in the next period. In general, the number of time periods need not equal the number of persons and activities. We present a new formulation of the multiperiod assignment problem, that of an integer, multicommodity network flow model. The special structure of the model allows us to find a good feasible solution relatively quickly by a shortest path heuristic algorithm. We discuss a new branch and bound algorithm for solving this problem to optimality. The subproblems of the branch and bound tree are evaluated by solving a set of special-structured, shortest path problems all of which can be solved in order \(n^ 2T\) time, where n is the number of persons and activities, and T is the number of time periods. We present computational tests of the algorithm on moderately sized problems.
Mathematics Subject Classification ID: 90C08
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 3932793
zbMATH Keywords: planning
zbMATH Keywords: multiperiod assignment problem
zbMATH Keywords: integer, multicommodity network flow model
zbMATH Keywords: shortest path heuristic algorithm
zbMATH Keywords: branch and bound algorithm
MaRDI profile type: Publication
full work available at URL: 0377-2217(86)90302-4
OpenAlex ID: W2074639186
cites work: Facets of the three-index assignment polytope
cites work: Traffic assignment in communication satellites
cites work: Note—On the Use of Fictitious Bounds in Tree Search Algorithms
cites work: On a routing problem
cites work: Static and Dynamic Assignment Models with Multiple Objectives, and Some Remarks on Organization Design
cites work: Q5337702
cites work: Q5541765
cites work: Generalized upper bounding techniques
cites work: A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees
cites work: A note on two problems in connexion with graphs
cites work: A combinatorial equivalence between A class of multicommodity flow problems and the capacitated transportation problem
cites work: Technical Note—A Single-Commodity Transformation for Certain Multicommodity Networks
cites work: The simplex method for integral multicommodity networks
cites work: The multicommodity assignment problem: A network aggregation heuristic
cites work: Network topology and integral multicommodity flow problems
cites work: Graphic matroids and the multicommodity transportation problem
cites work: A bilinear programming formulation of the 3-dimensional assignment problem
cites work: Complexity of a 3-dimensional assignment problem
cites work: An Algorithm for Solving 3-Dimensional Assignment Problems with Application to Scheduling a Teaching Practice
cites work: Q5675139
cites work: Q4178800
cites work: Q5518886
cites work: New Methods in Mathematical Programming—The Solid Transportation Problem
cites work: The Multi-Index Problem
cites work: Multi-Commodity Network Flows
cites work: A Survey of Linear Cost Multicommodity Network Flows
cites work: Q3968758
cites work: An Effective Subgradient Procedure for Minimal Cost Multicommodity Flow Problems
cites work: Q4130999
cites work: Shortest Path and Network Flow Algorithms
cites work: Branch-and-Bound Methods: A Survey
cites work: Q5643803
cites work: Q5528346
cites work: Letter to the Editor—The Multidimensional Assignment Problem
cites work: On Two Commodity Network Flows
cites work: Feasibility of Two Commodity Network Flows
cites work: Two commodity network flows and linear programming
cites work: Q3285992
cites work: Q3264587
Recommended article: Approximation and Online Algorithms
Recommended article: Solving Multicommodity Flow Problems by an Approximation Scheme
Recommended article: A Specialized Interior-Point Algorithm for Multicommodity Network Flows
Recommended article: The Multicommodity Multilevel Bottleneck Assignment Problem
Recommended article: Q5020878
Recommended article: The minimum cost multicommodity flow problem in dynamic networks and an algorithm for its solving
Recommended article: A Combined Matheuristic for the Piecewise Linear Multicommodity Network Flow Problem
Recommended article: A forward network simplex algorithm for solving multiperiod network flow problems
Recommended article: A branch‐and‐cut algorithm for the single‐commodity, uncapacitated, fixed‐charge network flow problem
Recommended article: Cycle‐based algorithms for multicommodity network flow problems with separable piecewise convex costs
description: scientific article; zbMATH DE number 3932793