Introduction to Network Optimization

Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin

ABSTRACT

Due to its widespread applications, network optimization is an important subfield within the broad field of optimization. This article introduces some core network optimization problems that are studied in greater depth in subsequent sections. The article introduces the following fundamental network optimization problems: maximum flow problem, shortest-path problem, minimum-cost single-commodity flow problem, minimum-cost multicommodity flow problem, and the minimum spanning tree problem. The focus of the article is to describe several sample applications of each of the fundamental network optimization problems. These applications are intended to illustrate a range of problem contexts and to be suggestive of how network optimization problems arise in practice.