Linear Assignment Problems in Combinatorial Optimization

Boris Goldengorin () and Dmitry Krushinsky ()
Additional contact information
Boris Goldengorin: Ohio University
Dmitry Krushinsky: Wageningen University and Research

A chapter in Optimization Methods and Applications, 2017, pp 183-216 from Springer

Abstract: Abstract In this chapter we introduce the notion of a “pattern” in the Linear Assignment Problem and show that patterns may be useful to create new insights and approaches for many combinatorial optimization problems defined on a rectangular input matrix. We define a pattern as a specific collection of cells in the rectangular matrix reflecting the structure of an optimal solution to the original combinatorial optimization problem (COP). We illustrate the notion of pattern by means of some well-known problems in combinatorial optimization, including the variations of the Linear Ordering Problem, the Cell Formation Problem, and some others. Then, we give a detailed consideration to pattern-based solution approaches for the two mentioned problems.

Keywords: Linear Assignment Problem (LAP); Linear Ordering Problem (LOP); Cell Formation Problem (CFP); Feasible Patterns; Multicut Problem (search for similar items in EconPapers)
Date: 2017
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-319-68640-0_9

Ordering information: This item can be ordered from
http://www.springer.com/9783319686400

DOI: 10.1007/978-3-319-68640-0_9

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().