In 1961 Leon Steinberg formulated a “backboard wiring” problem that has resisted solution for 40 years. Steinberg’s wiring problem is to determine the locations of 34 computer components on a 4 by 9 grid so as to minimize the total length of the wiring required to interconnect them. The problem is an example of a … Read more
We propose a new relaxation scheme for the MAX-CUT problem using second-order cone programming. We construct relaxation problems to reflect the structure of the original graph. Numerical experiments show that our relaxation approaches give better bounds than those based on the spectral decomposition proposed by Kim and Kojima, and that the efficiency of the branch-and-bound … Read more
This paper addresses a multi-period investment model for capacity expansion in an uncertain environment. Using a scenario tree approach to model the evolution of uncertain demand and cost parameters, and fixed-charge cost functions to model the economies of scale in expansion costs, we develop a multi-stage stochastic integer programming formulation for the problem. A reformulation … Read more
This paper considers the solution of Mixed Integer Nonlinear Programming (MINLP) problems. Classical methods for the solution of MINLP problems decompose the problem by separating the nonlinear part from the integer part. This approach is largely due to the existence of packaged software for solving Nonlinear Programming (NLP) and Mixed Integer Linear Programming problems. In … Read more