Location, scheduling, design, and integer programming

Manfred Padberg, Minendra P. Rijal

This monograph focuses on a class of problems that in effect have yet to be solved. Location, scheduling and design problems are assignment type problems with quadratic cost functions and occur in many contexts. Applications of these problems abound in diverse disciplines, such as anthropology, archeology, architecture, chemistry, computer science, economics, electronics, ergonomics, marketing, operations management, political science, statistical physics, zoology, etc. Padberg and Rijal have taken an important step in the solution of these problems. In this monograph they classify mathematical properties for ten classes of assignment problems: Quadratic Assignment Problems, Traveling Salesman Problems, Triangulation Problems, Linear Assignment Problems, VLSI Circuit Layout Design Problems, Multi-Processor Problems, Scheduling Problems with Interaction Costs, Operation-Scheduling Problems, Graph and Clique Partitioning Problems, and Boolean Quadratic Problems. They note that before these problems can be solved computationally, one must know and understand their mathematical properties. After discussing these properties, an integer programming approach is offered for solving them. The computational approach has shown considerable algorithmic success. The heart of this monograph is the theoretical work on assignment problems and the computation results that were produced using algorithms developed at NYU. The authors conclude that implementing a proper branch-and-cut algorithm on these types of problems will push the limits of exact computation far beyond the current ones.

「Nielsen BookData」より


  • Preface. 1. Location Problems. 2. Scheduling and Design Problems. 3. Solution Approaches. 4. Locally Ideal LP Formulations I. 5. Locally Ideal LP Formulations II. 6. Quadratic Scheduling Problems. 7. Quadratic Assignment Polytopes. 8. Solving Small QAPs. A. FORTRAN Programs for Small SQPs. References. Index.

「Nielsen BookData」より


書名 Location, scheduling, design, and integer programming
著作者等 Padberg, M. W
Padberg M.W.
Rijal Minendra
Rijal Minendra P.
シリーズ名 International series in operations research & management science
出版元 Kluwer Academic
刊行年月 c1996
ページ数 xi, 220 p.
大きさ 25 cm
ISBN 0792397150
NCID BA28415458
※クリックでCiNii Booksを表示
言語 英語
出版国 アメリカ合衆国