David J. Rader - Deterministic Operations Research: Models and Methods in Linear Optimization

CONTENTS

Copyright 2010 by John Wiley & Sons, Inc. All rights reserved

Published by John Wiley & Sons, Inc., Hoboken, New Jersey

Published simultaneously in Canada.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 750-4470, or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permission.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at (800) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Rader, David J., 1970

Deterministic operations research : models and methods in linear

optimization / David J. Rader, Jr.

p. cm.

Includes bibliographical references and index.

ISBN 978-0-470-48451-7 (cloth)

1. Operations researchMathematics. 2. Mathematical optimization. 3.

Linear programming. I. Title.

T57.6.R245 2010

519.72dc22

2009054232

10 9 8 7 6 5 4 3 2 1

To Cetta, Megan, and
Abby

PREFACE

This book represents the deterministic operations research course that I have taught to mathematics, computer science, and engineering students over the past 10 years. It deals with the study of linear optimization (both continuous and discrete), emphasizing the modeling of real problems as linear optimization problems and the designing of algorithms to solve them, covering topics in linear programming, network optimization, and integer programming.

In this book, I emphasize three aspects of deterministic operations research:

1. Modeling real-world problems as linear optimization problems.

2. Designing algorithms (both heuristic and exact methods) to solve these problems.

3. Using mathematical theory to improve our understanding of the problem, to improve existing algorithms, and to design new algorithms.

Although these aspects are important for both researchers and practitioners of operations research, they are not always in the forefront of operations research textbooks. It is true that many books highlight optimization modeling and algorithms to solve these problems; however, very few, if any, explicitly discuss the algorithm design process used to solve problems. This book is intended to fill that gap.

My intended audience for this book is a junior/senior mathematics course in deterministic operations research. It will serve as both comprehensive text for such a course and a reference book for future exploration of the subjects. The book can also be used for operations research courses in engineering departments and for first-year graduate courses in linear optimization. It is not meant to be a reference book for researchers, but to be a book for people wanting to learn about linear optimization problems and techniques. A student using this book should have been exposed to (multivariable) calculus and linear algebra, whenever possible.

I introduce concepts and approaches by mixing in many examples to both demonstrate and motivate theoretical concepts and then proving these results. Advanced ideas are described in a common-sense style that illustrates the core aspects of the idea in ways that are easy to understand, motivates the reader to understand how to think about the problem, not just what to think, and illustrates this using concrete examples. Each chapter of the book is designed to be the continuation of the story of how to both model and solve optimization problems by using the specific problems (linear and integer programs) as guides. This enables the reader (and instructors) to see how solution methods can be derived instead of just seeing the final product (the algorithms themselves).

I begin this book with an introduction to linear optimization modeling, incorporating many common modeling constructs through examples. In class I typically take about 2025% of the term to discuss various models and the modeling process, so it is no surprise that the modeling chapters encompass that much of the book. I feel it is important for students to be able to translate a real-world situation into a mathematical language (here as an optimization model), be able to solve it using an optimization package, and be able to interpret the results. It is also important for students to see that there is a difference between the model and the data, and I try to emphasize this by discussing the general form of various constructs. I end my discussion of modeling by illustrating some common operations research problems and how they are solved. In addition, the exercises discuss various applications that have appeared in the research literature over the past 20 years.

Once the importance and usefulness of linear and integer programming models have been illustrated, I take a different approach to solution methods than most books. Typically, at an introductory level, solution methods for optimization problems are presented in the following style: (a) the problem is defined, (b) a solution technique is described and illustrated, and (c) the solution method is proven correct (it gives the correct answer) and various properties are studied. I illustrate how to design methods to solve these problems by first introducing the algorithm design paradigm through the use of heuristic methods for common integer programming models and then discussing general optimization approaches and showing how to use the properties of linear programs to specialize these general methods. This illustrates the algorithm design process.

I have found that the algorithm design process (which is key to deterministic operations research) can best be introduced through heuristic methods. This allows us to concentrate on the design itself without having to worry about finding the optimal solution. Once we have designed a few simple algorithms we are ready to search for optimal solutions by first learning through an example what properties an optimal solution must have and then designing (and improving) an algorithm to satisfy them.