[ugrads] Discrete Optimization Talk Next Week

Hemanshu Kaul kaul at iit.edu
Wed Apr 13 23:35:35 CDT 2016

Hello all,

Next week, on *Tuesday 4/19 at 12:45pm*, Adam Rumpf, a graduate student in
Applied Math, will give a talk on introduction to Minimum cost Flow
problems and the Network Simplex Algorithm. All students are welcome and
encouraged to attend the talk as there will be no prerequisites beyond Math
332/ Linear Algebra for understanding the ideas. *Students who have taken
or are taking Math 435 or Math 535 are especially encouraged to attend. *See
the details below.

Adam will give a followup talk on Wednesday, 4/27 at 12:45pm on building a
network simplex-type algorithm for minimum cost flow problem on
interdependent networks.


*Title: Introduction to Minimum Cost Flow and the Network Simplex Algorithm*
*Speaker: Adam Rumpf, IIT*

*Location: 122, RE (E1)*

*Time: 12:45pm, Tuesday, 4/19.*

*Abstract: *The minimum cost network flow (MCNF) problem is an important
form of linear program that can be used to model a wide variety of network
design and management decision problems. Given a flow network through which
material must be routed, the goal in the MCNF problem is to determine the
amount of material to transport through each arc of the network in order to
satisfy all given supply and demand requirements, while minimizing the cost
over the arcs used.
This problem is formulated as a linear program whose decision variables
represent the flow values of each arc, with the objective of minimizing the
sum of all flow costs, and with constraints to enforce flow conservation
and arc capacity. Its special combinatorial basis structure allows for it
to be solved much more efficiently than a general linear program through
the use of a specialized algorithm called network simplex.
This talk will serve as an introduction to the MCNF problem and network
simplex, discussing some major applications of the MCNF problem, and
showing how and why the network simplex algorithm works. * Familiarity with
network flows and linear programming will NOT be assumed.*

Hemanshu Kaul
Associate Professor of Applied Mathematics
Co-Director, Graduate Program on Decision Sciences (CDSOR)
Illinois Institute of Technology
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://math.iit.edu/pipermail/ugrads/attachments/20160413/8b262eae/attachment.html>

More information about the ugrads mailing list