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.
Copyright © 2018-2021 BrainKart.com; All Rights Reserved. (BS) Developed by Therithal info, Chennai.