Aggregation in Large-Scale Optimization
When analyzing systems with a large number of parameters, the dimen sion of the original system may present insurmountable difficulties for the analysis. It may then be convenient to reformulate the original system in terms of substantially fewer aggrega
- PDF / 23,347,411 Bytes
- 301 Pages / 439.377 x 666.117 pts Page_size
- 18 Downloads / 219 Views
Applied Optimization Volume 83 Series Editors:
Panos M. Pardalos University ofFlorida, U.S.A.
Donald W. Hearn University ofFlorida, U.S.A.
Aggregation in Large-Scale Optimization by
Igor Litvinchev and Vladimir Tsurkov Computing Center, Russian Academy a/Sciences, Moscow, Russia
SPRINGER-SCIENCE+BUSINESS MEDIA, B.V.
tt
Electronic Services
Library of Congress Cataloging-in-Publication
Litvinchev, Igor 1 Tsurkov, Vladimir Aggregation in Large-Scale Optimization ISBN 978-1-4613-4812-2 ISBN 978-1-4419-9154-6 (eBook) DOI 10.1007/978-1-4419-9154-6
Copyright © 2003 by Springer Science+Business Media Dordrecht Originally published by Kluwer Academic Publishers in 2003 Softcover reprint of the hardcover 1st edition 2003 All rights reserved. No part ofthis publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photo-copying, microfilming, recording, or otherwise, without the prior written permission of the publisher, with the exception of any material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Permissions for books published in the USA: permj s s; on s@Wkap com Permissions for books published in Europe: [email protected] Printed on acid-free paper.
Contents
Preface ............................................................. ix Chapter 1. Aggregated Problem and Bounds for Aggregation .............................. . .... 1 §1. Linear Programming Aggregation ..................... . .... 1
1.1. Definitions and Preliminary Results ............ . .... 2 1.2. A Posteriori Bounds ........................... . .... 6 1.3. A Priori Bounds ............................... . .... 8 1.4. Some Generalizations .............................. 10 1.4.1. A Posteriori Bounds ......................... 10 1.4.2. A Priori Bounds ............................ 17 1.5. Illustrative Example and Numerical Indications .... 19 §2. The Generalized Transportation Problem ............. . ... 25 2.1. The Aggregated Problem ...................... . ... 26 2.2. The Error Bounds ................................. 30 2.3. Numerical Indications ............................. 35 §3. Variable Aggregation in Nonlinear Programming .......... 38 §4. Sharpening Localization by Valid Inequalities in Integer Programming ................................. . ... 44 §5. The Generalized Assignment Problem ................ . ... 51 Comments and References to Chapter 1 . . . . . . . . . . . . . . . . . .. . ... 58 Chapter 2. Iterative Aggregation-Decomposition in Optimization Problems ........................ 61 §1. Linear Aggregation in Finite-Dimensional Problems ....... 62
vi §2. Problems with Constraints of Special Structure ....... . ... 72 §3. Decomposition of the Macroproblem in the Block-Separable Case ................................. . ... 92 §4. Adaptive Clustering in Variable Aggregation ............. 104 §5. Aggregation of Constraints .............................. 112 §6. Aggreg
