Benders decomposition has been widely used for solving network design problems. In this paper, we use a branch-and-cut algorithm to improve the separation procedure of Gabrel et al. and Knippel et al. for capacitated network design. We detail experiments on bilayer networks, comparing with Knippel’s previous results. CitationTechnical Reports of the ULB Computer Science Department, … Read more
In this paper, we propose a new recombination operator and test its performance in the context of the multiobjective 0/1 knapsack problem (MOKP). The proposed recombination operator generates only one offspring solution from a selected pair of parents according to the two following stages. In the first stage, called genetic shared-information stage or similarity-preserving stage, … Read more
The Fibonacci index of a graph is the number of its stable sets. This parameter is widely studied and has applications in chemical graph theory. In this paper, we establish tight upper bounds for the Fibonacci index in terms of the stability number and the order of general graphs and connected graphs. Tur\’an graphs frequently … Read more
CitationThis paper is published in Annals of Operations Research, Springer
The Max-Min Diversity Problem (MMDP) consists in selecting a subset of elements from a given set in such a way that the diversity among the selected elements is maximized. The problem is NP-hard and can be formulated as an integer linear program. Since the 1980s, several solution methods for this problem have been developed and … Read more
Conventional Lagrangean preprocessing for the network Weight Constrained Shortest Path Problem (WCSPP calculates lower bounds on the cost of using each node and edge in a feasible path using a single optimal Lagrange multiplier for the relaxation of the WCSPP. These lower bounds are used in conjunction with an upper bound to eliminate nodes and … Read more
In this work, we consider a classification problem where the objects to be classified are bags of instances which are vectors measuring d different attributes. The classification rule is defined in terms of a ball, whose center and radius are the parameters to be computed. Given a bag, it is assigned to the positive class … Read more
Systems of polynomial equations over an algebraically-closed field K can be used to concisely model many combinatorial problems. In this way, a combinatorial problem is feasible (e.g., a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution over K. In this paper, we investigate an algorithm … Read more
The problem of Routing and Wavelength Assignment in Wavelength Division Multiplexing (WDM) optical networks consists in routing a set of lightpaths and assigning a wavelength to each of them, such that lightpaths whose routes share a common fiber are assigned to different wavelengths. When the objective is to minimize the total number of wavelengths used, … Read more
Given a graph G = (V,E), the independent set problem is that of finding a maximum-cardinality subset S of V such that no two vertices in S are adjacent. We introduce two fast local search routines for this problem. The first can determine in linear time whether a maximal solution can be improved by replacing … Read more