ABSTRACT

This chapter discusses various topics in discrete optimization, especially those that arise in applying operations research techniques to applied problems. A fundamental tool is linear programming and its extensions to problems in which certain variables must assume integer values. These techniques are useful in devising solution techniques for a variety of problems in which a given resource must be optimally utilized subject to constraints. The chapter also presents several metaheuristic approaches for approximate solution of difficult discrete optimization problems. Linear programming (LP) involves the optimization of a linear function under linear inequality constraints. Applications of this model are widespread, including problems arising in marketing, finance, inventory, capital budgeting, computer science, transportation, and production. Algorithms are available that, in practice, solve LP problems efficiently. The simplex method is in practice remarkably efficient and it is widely used for solving LP problems.