Publisher Summary This chapter traces the history of combinatorial optimization. As a coherent mathematical discipline, combinatorial optimization is relatively young. Linear programming forms the hinge in the history of combinatorial optimization. Its initial conception by Kantorovich and Koopmans was motivated by combinatorial applications—in particular, in transportation and transshipment. The assignment problem is one of the first investigated combinatorial optimization problems. A breakthrough in solving the assignment problem came when Dantzig showed that the assignment problem can be formulated as a linear programming problem that automatically has an integer optimum solution. The reason is a theorem of Birkhoff 1946 stating that the convex hull of the permutation matrices is equal to the set of doubly stochastic matrices—nonnegative matrices in which each row and column sum is equal to 1. Therefore, minimizing a linear functional over the set of doubly stochastic matrices (which is a linear programming problem) gives a permutation matrix, being the optimum assignment.
Description
On the History of Combinatorial Optimization (Till 1960)
%0 Book Section
%1 Schrijver20051
%A Schrijver, Alexander
%B Discrete Optimization
%D 2005
%E K. Aardal, G.L. Nemhauser
%E Weismantel, R.
%I Elsevier
%K Combinatorial History Optimization
%P 1 - 68
%R 10.1016/S0927-0507(05)12001-5
%T On the History of Combinatorial Optimization (Till 1960)
%U http://www.sciencedirect.com/science/article/pii/S0927050705120015
%V 12
%X Publisher Summary This chapter traces the history of combinatorial optimization. As a coherent mathematical discipline, combinatorial optimization is relatively young. Linear programming forms the hinge in the history of combinatorial optimization. Its initial conception by Kantorovich and Koopmans was motivated by combinatorial applications—in particular, in transportation and transshipment. The assignment problem is one of the first investigated combinatorial optimization problems. A breakthrough in solving the assignment problem came when Dantzig showed that the assignment problem can be formulated as a linear programming problem that automatically has an integer optimum solution. The reason is a theorem of Birkhoff 1946 stating that the convex hull of the permutation matrices is equal to the set of doubly stochastic matrices—nonnegative matrices in which each row and column sum is equal to 1. Therefore, minimizing a linear functional over the set of doubly stochastic matrices (which is a linear programming problem) gives a permutation matrix, being the optimum assignment.
@incollection{Schrijver20051,
abstract = {Publisher Summary This chapter traces the history of combinatorial optimization. As a coherent mathematical discipline, combinatorial optimization is relatively young. Linear programming forms the hinge in the history of combinatorial optimization. Its initial conception by Kantorovich and Koopmans was motivated by combinatorial applications—in particular, in transportation and transshipment. The assignment problem is one of the first investigated combinatorial optimization problems. A breakthrough in solving the assignment problem came when Dantzig showed that the assignment problem can be formulated as a linear programming problem that automatically has an integer optimum solution. The reason is a theorem of Birkhoff [1946] stating that the convex hull of the permutation matrices is equal to the set of doubly stochastic matrices—nonnegative matrices in which each row and column sum is equal to 1. Therefore, minimizing a linear functional over the set of doubly stochastic matrices (which is a linear programming problem) gives a permutation matrix, being the optimum assignment. },
added-at = {2014-01-10T21:11:30.000+0100},
author = {Schrijver, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/2b48e090a2f13b17a5b22a2a340ed9e26/rlanger},
booktitle = {Discrete Optimization},
description = {On the History of Combinatorial Optimization (Till 1960)},
doi = {10.1016/S0927-0507(05)12001-5},
editor = {K. Aardal, G.L. Nemhauser and Weismantel, R.},
interhash = {53e5a014646bca84daacb004cfdbd7eb},
intrahash = {b48e090a2f13b17a5b22a2a340ed9e26},
issn = {0927-0507},
keywords = {Combinatorial History Optimization},
pages = {1 - 68},
publisher = {Elsevier},
series = {Handbooks in Operations Research and Management Science },
timestamp = {2014-01-10T21:11:30.000+0100},
title = {On the History of Combinatorial Optimization (Till 1960) },
url = {http://www.sciencedirect.com/science/article/pii/S0927050705120015},
volume = 12,
year = 2005
}