Ebook: Location, Scheduling, Design and Integer Programming

Location, scheduling and design problems are assignment type problems with quadratic cost functions and occur in many contexts stretching from spatial economics via plant and office layout planning to VLSI design and similar prob­ lems in high-technology production settings. The presence of nonlinear inter­ action terms in the objective function makes these, otherwise simple, problems NP hard. In the first two chapters of this monograph we provide a survey of models of this type and give a common framework for them as Boolean quadratic problems with special ordered sets (BQPSs). Special ordered sets associated with these BQPSs are of equal cardinality and either are disjoint as in clique partitioning problems, graph partitioning problems, class-room scheduling problems, operations-scheduling problems, multi-processor assign­ ment problems and VLSI circuit layout design problems or have intersections with well defined joins as in asymmetric and symmetric Koopmans-Beckmann problems and quadratic assignment problems. 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. We then give a survey of the traditional solution approaches to BQPSs. It is an unfortunate fact that even after years of investigation into these problems, the state of algorithmic development is nowhere close to solving large-scale real­ life problems exactly. In the main part of this book we follow the polyhedral approach to combinatorial problem solving because of the dramatic algorith­ mic successes of researchers who have pursued this approach.

---

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.

---

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.
Content:
Front Matter....Pages i-xi
Location Problems....Pages 1-34
Scheduling and Design Problems....Pages 35-58
Solution Approaches....Pages 59-78
Locally Ideal LP Formulations I....Pages 79-104
Locally Ideal LP Formulations II....Pages 105-131
Quadratic Scheduling Problems....Pages 133-150
Quadratic Assignment Polytopes....Pages 151-166
Solving Small QAPs....Pages 167-171
Back Matter....Pages 173-220

---

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.
Content:
Front Matter....Pages i-xi
Location Problems....Pages 1-34
Scheduling and Design Problems....Pages 35-58
Solution Approaches....Pages 59-78
Locally Ideal LP Formulations I....Pages 79-104
Locally Ideal LP Formulations II....Pages 105-131
Quadratic Scheduling Problems....Pages 133-150
Quadratic Assignment Polytopes....Pages 151-166
Solving Small QAPs....Pages 167-171
Back Matter....Pages 173-220
....