Random-key genetic algorithms were introduced by Bean (1994) for solving sequencing problems in combinatorial optimization. Since then, they have been extended to handle a wide class of combinatorial optimization problems. This paper presents a tutorial on the implementation and use of biased random-key genetic algorithms for solving combinatorial optimization problems. Biased random-key genetic algorithms are … Read more
We study the minimum spanning tree problem, the maximum matching problem and the shortest path problem subject to binary disjunctive constraints: A negative disjunctive constraint states that a certain pair of edges cannot be contained simultaneously in a feasible solution. It is convenient to represent these negative disjunctive constraints in terms of a so-called conflict … Read more
Distance geometry problems arise from the need to position entities in the Euclidean $K$-space given some of their respective distances. Entities may be atoms (molecular distance geometry), wireless sensors (sensor network localization), or abstract vertices of a graph(graph drawing). In the context of molecular distance geometry, the distances are usually known because of chemical properties … Read more
Computing the 1-width of the incidence matrix of a Steiner Triple System gives rise to small set covering instances that provide a computational challenge for integer programming techniques. One major source of difficulty for instances of this family is their highly symmetric structure, which impairs the performance of most branch-and-bound algorithms. The largest instance in … Read more
We study a resource allocation problem where jobs have the following characteristics: Each job consumes some quantity of a bounded resource during a certain time interval and induces a given profit. We aim to select a subset of jobs with maximal total profit such that the total resource consumed at any point in time remains … Read more
Semidefinite programming (SDP) bounds for the quadratic assignment problem (QAP) were introduced in: [Q. Zhao, S.E. Karisch, F. Rendl, and H. Wolkowicz. Semidefinite Programming Relaxations for the Quadratic Assignment Problem. Journal of Combinatorial Optimization, 2,71–109, 1998.] Empirically, these bounds are often quite good in practice, but computationally demanding, even for relatively small instances. For QAP … Read more
When the matrix of distances between cities is symmetric and circulant, the traveling salesman problem (TSP) reduces to the so-called symmetric circulant traveling salesman problem (SCTSP), that has applications in the design of reconfigurable networks, and in minimizing wallpaper waste. The complexity of the SCTSP is open, but conjectured to be NP-hard, and we compare … Read more
We present a number of new algorithmic ideas for solving LP relaxations of extremely large precedence constrained production scheduling problems. These ideas are used to develop an implementation that is tested on a variety of real-life, large scale instances; yielding optimal solutions in very practicable CPU time. CitationUnpublished. Columbia University, BHP Billiton, August 2009.ArticleDownload View … Read more
The Sherali-Adams lift-and-project hierarchy is a fundamental construct in integer programming, which provides successively tighter linear programming relaxations of the integer hull of a polytope. We initiate a new approach to understanding the Sherali-Adams procedure by relating it to methods from computational algebraic geometry. Our main result is a refinement of the Sherali-Adams procedure that … Read more
We consider a generalization of the well known greedy algorithm, called $m$-step greedy algorithm, where $m$ elements are examined in each iteration. When $m=1$ or $2$, the algorithm reduces to the standard greedy algorithm. For $m=3$ we provide a complete characterization of the independence system, called trioid, where the $m$-step greedy algorithm guarantees an optimal … Read more