Large Scale Linear and Integer Optimization: A Unified Approach
This is a textbook about linear and integer linear optimization. There is a growing need in industries such as airline, trucking, and financial engineering to solve very large linear and integer linear optimization problems. Building these models requires
- PDF / 29,249,683 Bytes
- 739 Pages / 439.37 x 666.14 pts Page_size
- 86 Downloads / 271 Views
LARGE SCALE LINEAR AND INTEGER OPTIMIZATION: A UNIFIED APPROACH Richard Kipp Martin Graduate School of Business Universify of Chicago
" ~.
Springer Science+Business Media, LLC
Library of Congress Cataloging-in-Publication Data
Martin, Richard Kipp. Large scale linear and integer optimization : a united approach / Richard Kipp Martin. p. cm. Includes bibliographical references and index. ISBN 978-1-46l3-7258-5 ISBN 978-1-4615-4975-8 (eBook) DOI 10.1007/978-1-4615-4975-8 1. Linear programming. 2. Mathematical optimization. 1. Title. T57.75.M375 1999 5 19.7'2--dc2 1 98-46062 CIP Copyright © 1999 Springer Science+Business Media New York Originally published by Kluwer Academic Publishers in 1999 Softcover reprint of the hardcover 1st edition 1999 AII rights reserved. No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, mechanical, photocopying, record ing, or otherwise, without the prior written permis sion of the publisher, Springer Science+Business Media, LLC .
Printed an acid-free paper.
This book is dedicated to my parents, Bruce and Phyllis Martin.
CONTENTS
Preface Part I 1
MOTIVATION
LINEAR AND INTEGER LINEAR OPTIMIZATION 1.1 1.2 1.3 1.4 1.5 1.6 1.7
Part II 2
xv
Introduction Linear and Integer Linear Optimization A Guided Tour of Applications Special Structure Linear and Integer Linear Programming Codes Other Directions Exercises
3 3 5 7 21 25 28 29
THEORY
33
LINEAR SYSTEMS AND PROJECTION 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10
1
Introduction Projection for Equality Systems: Gaussian Elimination Projection for Inequality Systems: Fourier-Motzkin Elimination Applications of Projection Theorems of the Alternative Duality Theory Complementary Slackness Sensitivity Analysis Conclusion Exercises
35 35 36 39 46 49 57 61 65 75 75
LARGE SCALE LINEAR AND INTEGER OPTIMIZATION
Vlll
3
LINEAR SYSTEMS AND INVERSE PROJECTION 3.1 3.2 3.3 3.4 3.5 3.6
4
INTEGER LINEAR SYSTEMS: PROJECTION AND INVERSE PROJECTION 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8
Part III 5
Introduction Background Material Solving A System of Congruence Equations Integer Linear Equalities Integer Linear Inequalities: Projection Integer Linear Inequalities: Inverse Projection Conclusion Exercises
ALGORITHMS
THE SIMPLEX ALGORITHM 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9
6
Introduction Deleting Constraints by Adding Variables Dual Relationships Sensitivity Analysis Conclusion Homework Exercises
Introduction Motivation Pivoting Revised Simplex Product Form of the Inverse Degeneracy and Cycling Complexity of the Simplex Algorithm Conclusion Exercises
MORE ON SIMPLEX 6.1 6.2 6.3
Introduction Sensitivity Analysis The Dual Simplex Algorithm
81 81 81 91 93 99 100 ]03 103 105 114 122 124 127 136 137 141 143 143 143 147 154 162 168 177 178 178 183 183 184 191
Contents
6.4 6.5 6.6 6.7 6.8 6.9
7
Introduction Projective Transformations Karmarkar's Algorithm Polynomial Termination Purification, Standard Form and Sliding Objective Affine Polyhedral Transformations Geometry of th
