MA381 INTEGER PROGRAMMING & NETWORK FLOWS (3 Cr.)
COURSE DESCRIPTION
Prerequisite: MA380
Linear Programming
General Introduction and Goals
Introduction to the basic concepts, algorithms, and methodology of network
and integer programming with strong emphasis on mathematical modeling,
analysis, and application to nontrivial problems arising in various areas of
the physical, social, and decision sciences, and applied mathematics.
Network flow theory, which is closely related to linear programming, integer
programming, and graph theory, is one of the most useful tools of Operations
Research. Its significance lies mainly in its remarkable capability for
modeling a wide range of practical problems encountered frequently in
various areas of science, mathematics, engineering, economics, management,
and operations research. Network analysis has found relevance and
applications in information theory, cybernetics, social-group structures,
language structures, chemical-bond structures, planning and control of
research and development projects, transportation systems, distribution
systems, communication systems, routing problems, assignment problems,
scheduling problems, and integer programming, among others.
Linear
integer programming (integer programming, discrete optimization,
combinatorial optimization), which is intimately connected with linear
programming, network flow theory, and combinatorics, is concerned with the
analysis and solution of optimization problems in which some or all of the
decision variables are restricted to assume values within specified discrete
sets. These discrete constraint structures allow the mathematical
abstraction and formal representation of phenomena or alternatives where
indivisibility is unavoidable or there is not a continuum of alternatives.
Discrete optimization problems abound in many areas of science, mathematics,
engineering, economics, management, and operations research. Specifically,
the prototype integer programming models have found widespread applications
in the design of distribution systems, production scheduling, machine
sequencing, capital budgeting, portfolio analysis, facility location,
telecommunication and transportation network design, VLSI circuit design,
automated production systems design, computer design, combinatorics, graph
theory, logic statistical data analysis, reliability theory, high-energy
physics (determination of minimum energy states), cryptography (designing
unbreakable codes), politics (selecting fair election districts), molecular
biology, and x-ray crystallography, among others.
The
mathematical underpinnings of network flow theory and integer programming
belong to the domain of modern applied mathematics. This fact coupled with
the possibility of accommodating and treating a broad selection of concrete
problems in a unified framework will make MA 381 a valuable addition to the
Mathematics and Computer Science curriculum. This and the two companion
courses
MA 380 and
MA 485 will provide the students with ample opportunities to gain an
appreciation for, an understanding of, and a facility in the use of
mathematics in other fields. Furthermore, these courses will make the
students aware of a broad range of career opportunities, help them in the
job market, and guide them in exploring the possibilities of pursuing
graduate programs in some areas of the decision sciences.
Course Content
1.
Network
Models and Algorithms
a.
Basic
definitions and terminology
b.
Single-commodity maximum flow problems
c.
Single-commodity minimum cost flow problems
d.
Shortest path
problems
e.
Minimum
spanning tree problems
f.
Project
planning and control with PERT-CPM
g.
Multicommodity network flow problems
h.
Relationships
between linear programming and network flows
i.
The network
simplex algorithms
j.
Other network
algorithms
2.
Integer
Programming
a.
The origins
and scope of integer programming
b.
Formulation
of integer and combinatorial programming problems
c.
Examples of
integer programming: capital budgeting problems, batch size problems, fixed
charge problems, plant location problems, project selection problems,
multiple choice problems, job sequencing problems, work scheduling problems,
facility location problems, cutting stock problems, knapsack problems,
matching problems, set representation problems, set covering problems, set
partitioning problems, set packing problems, the Chinese postman problem,
traveling salesman problems, problems containing either-or constraints,
problems containing if-then constraints, combinatorial problems, assignment
problems, network design problems, graph-theoretical problems, separable
nonlinear programming problems, . . .
d.
Relationships
between linear programming and integer programming
e.
The
branch-and-bound algorithm for solving pure integer programming problems
f.
The
branch-and-bound algorithm for solving mixed integer programming problems
g.
Solution of
knapsack problems by the branch-and-bound method
h.
Solution of
combinatorial optimization problems by the branch-and-bound method
i.
Implicit
enumeration techniques
j.
Cutting plane
algorithms
k.
Computer
packages
3.
Deterministic
Discrete Dynamic Programming
a.
Characteristics of dynamic programming
b.
Bellman's
principle of optimality
c.
Formulation
of dynamic programming recursions
d.
Dynamic
programming formulation of network flow, combinatorial, and integer
programming problems
e.
Applications
of dynamic programming: equipment inspection and replacement problems,
resource allocation problems, optimal capacity expansion problems,
cargo-loading problems, sequencing problems, scheduling problems, dynamic
inventory control problems, multistage production planning problems,
discrete optimal control problems, . . .
4.
Computational
Complexity
a.
Polynomial-time algorithms
b.
Nondeterministic algorithms
c.
NP-complete
problems
|
