Modified Orbital Branching with Applications to Orbitopes and to Unit Commitment

The past decade has seen advances in general methods for symmetry breaking in mixed-integer linear programming. These methods are advantageous for general problems with general symmetry groups. Some important classes of MILP problems, such as bin packing and graph coloring, contain highly structured symmetry groups. This observation has motivated the development of problem-specific techniques. In … Read more

Global Routing in VLSI Design: Algorithms, Theory, and Computational Practice

Global routing in VLSI (very large scale integration) design is one of the most challenging discrete optimization problems in computational theory and practice. In this paper, we present a polynomial time algorithm for the global routing problem based on integer programming formulation with a theoretical approximation bound. The algorithm ensures that all routing demands are … Read more

Symmetry in Scheduling Problems

The presence of symmetry is common in certain types of scheduling problems. Symmetry can occur when one is scheduling a collection of jobs on multiple identical machines, or if one is determining production schedules for identical machines. General symmetry-breaking methods can be strengthened by taking advantage of the special structure of the symmetry group in … Read more

Formulation of Oligopolistic Competition in AC Power Networks: An NLP Approach

In this paper, oligopolistic competition in a centralized power market is characterized by a multi-leader single-follower game, and formulated as a nonlinear programming (NLP) problem. An AC network is used to represent the transmission system and is modeled using rectangular coordinates. The follower is composed of a set of competitive suppliers, demands, and the system … Read more

Numerical Study of Affine Supply Function Equilibrium in AC Network-Constrained Markets

An affine supply function equilibrium (SFE) approach is used to discuss voltage constraints and reactive power issues in the modeling of strategic behavior. Generation companies (GenCos) can choose their bid parameters with no restrictions for both energy and spinning reserves. The strategic behavior of generators is formulated as a multi-leader single-follower game. Each GenCo is … Read more

Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes

This paper is concerned with the single-row facility layout problem (SRFLP). A globally optimal solution to the SRFLP is a linear placement of rectangular facilities with varying lengths that achieves the minimum total cost associated with the (known or projected) inter- actions between them. We demonstrate that the combination of a semidefinite programming relaxation with … Read more

A Semidefinite Optimization Approach for the Single-Row Layout Problem with Unequal Dimensions

The facility layout problem is concerned with the arrangement of a given number of rectangular facilities so as to minimize the total cost associated with the (known or projected) interactions between them. We consider the one-dimensional space allocation problem (ODSAP), also known as the single-row facility layout problem, which consists in finding an optimal linear … Read more

A New Mathematical-Programming Framework for Facility-Layout Design

We present a new framework for efficiently finding competitive solutions for the facility-layout problem. This framework is based on the combination of two new mathematical-programming models. The first model is a relaxation of the layout problem and is intended to find good starting points for the iterative algorithm used to solve the second model. The … Read more

An Attractor-Repeller Approach to Floorplanning

The floorplanning (or facility layout) problem consists in finding the optimal positions for a given set of modules of fixed area (but perhaps varying dimensions) within a facility such that the distances between pairs of modules that have a positive connection cost are minimized. This is a hard discrete optimization problem; even the restricted version … Read more