CHAPTER 9
Integer
Linear Programming
Chapter Guide. Integer linear programs (ILPs) are linear programs with some or all the variables restricted to integer (or
discrete) values. When you study ILP, you need to concentrate on three areas:
application, theory, and computation. The chapter starts with a number of
applications that demonstrate the rich use of ILP in practice. Then it presents
the two prominent algorithms of ILP: branch and bound (B&B) and cutting
plane. Of the two algorithms, B&B is decidedly more efficient
computationally. Indeed, practically all commercial codes are rooted in
B&B. The chapter closes with a presentation of the traveling salesperson
problem (TIP), a problem that has important practical applications.
A drawback of ILP algorithms is their lack of consistency in solving
integer problems. Although these algorithms are proven theoretically to
converge in a finite number of iterations, their implementation on the computer
(with its inherent machine roundoff error) is a different experience. You
should keep this point in mind as you study the ILP algorithms.
The chapter shows how AMPL and Solver are used with ILP You will find
TORA's user-guided option useful in detailing the B&B computations.
This chapter includes a summary of 1 real-life application, 12 solved
examples, 5 AMPL models, 1 Excel spreadsheet, 65 end-ot-section problems, and
10 cases. The cases are in Appendix E on the CD. The AMPL/Excel/Solver/TORA
programs are in folder ch9Files.
Real-Life Application-optimizing Trailer Payloads at PFG Building Glass
PFG uses specially equipped (fifth-wheel) trailers to deliver packs of
sheets of flat glass to customers. The packs vary in both size and weight, and
a single trailer load may include different packs, depending on received
orders. Government regulations set maximum limits on axle weights, and the
actual positioning of the packs on the trailer is crucial in determining these
weights. The problem deals with determining the opti-mal loading of the packs
on the trailer bed to satisfy axle-weight limits. The problem is solved as an
integer program. Case 7 in Chapter 24 on the CD provides the details of the
study.
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.