We consider a complex planning problem in integrated steel production. A sequence of coils of sheet metal needs to be color coated in consecutive stages. Di erent coil geometries and changes of coatings may necessitate time-consuming setup work. In most coating stages one can choose between two parallel color tanks in order to reduce setup times. … Read more
We consider two approaches for solving the classical minimum vertex coloring problem�that is, the problem of coloring the vertices of a graph so that adjacent vertices have different colors and minimizing the number of used colors, namely, constraint programming and column generation. Constraint programming is able to solve very efficiently many of the benchmarks but … Read more
Run time distributions or time-to-target plots are very useful tools to characterize the running times of stochastic algorithms for combinatorial optimization. We further explore run time distributions and describe a new tool to compare two algorithms based on stochastic local search. For the case where the running times of both algorithms fit exponential distributions, we … Read more
Given a graph with nonnegative edge weights and a set of pairs of nodes Q, we study the problem of constructing a minimum weight set of edges so that the induced subgraph contains at least K edge-disjoint paths containing at most L edges between each pair in Q. Using the layered representation introduced by Gouveia, … Read more
In the paper we consider degree, spectral, and semidefinite bounds on the stability and chromatic numbers of a graph: so-called weak sandwich theorems. We examine the additivity properties of the bounds (the sum of two graphs is their disjoint union), and as an application we tighten the bounds in the weak sandwich theorems, if the … Read more
GRASP with path-relinking (GRASP+PR) is a metaheuristic for finding optimal or near-optimal solutions of combinatorial optimization problems. This paper proposes a new automatic parameter tuning procedure for GRASP+PR heuristics based on a biased random-key genetic algorithm (BRKGA). Given a GRASP+PR heuristic with N input parameters, the tuning procedure makes use of a BRKGA in a … Read more
In this paper we deal with the Critical Node Problem (CNP), i.e., the problem of searching for a given number K of nodes in a graph G, whose removal minimizes the number of connections between pairs of nodes in the residual graph. While the NP-completeness of this problem for general graphs has been already established … Read more
We study the problem of detecting a maximum embedded network submatrix in a {-1,0,+1}-matrix. Our aim is to solve the problem to optimality. We introduce a 0-1 integer linear formulation for this problem based on its representation over a signed graph. A polyhedral study is presented and a branch-and-cut algorithm is described for finding an … Read more
We consider optimization of nonlinear objective functions that balance $d$ linear criteria over $n$-element independence systems presented by linear-optimization oracles. For $d=1$, we have previously shown that an $r$-best approximate solution can be found in polynomial time. Here, using an extended Erdos-Ko-Rado theorem of Frankl, we show that for $d=2$, finding a $\rho n$-best solution … Read more
We study the maximum flow problem subject to binary disjunctive constraints in a directed graph: A negative disjunctive constraint states that a certain pair of arcs in a digraph cannot be simultaneously used for sending flow in a feasible solution. In contrast to this, positive disjunctive constraints force that for certain pairs of arcs at … Read more