Search

Robust combinatorial optimization problems with cardinality constrained uncertainty may be solved by a finite number of nominal problems. In this paper, we show that the number of nominal problems to be solved can be reduced significantly.

We establish strong NP-hardness and in-approximability of the so-called representatives selection problem, a tool selection problem in the area of robust optimization. Our results answer a recent question of Dolgui and Kovalev (4OR Q J Oper Res 10:181–192, 2012). Keywords: Combinatorial optimization; Computational complexity; Robust optimization

This paper deals with stability analysis in multi-objective combinatorial optimization problems. The stability radius of an efficient solution is defined as the maximal adjustment of the problem parameters such that this solution remains efficient. An algorithm based on inverse optimization is proposed to compute it. The adjustment is limited to the coefficients of the objective functions and measured by the Chebyshev norm. This approach is applied to randomly generated instances of the bi-objective knapsack problem and computational results are reported. Several illustrative examples are analyzed.

The design of effective neighborhood structures is fundamental to the performance of local search and metaheuristic algorithms for combinatorial optimization. Significant efforts have been made in the creation of larger and more powerful neighborhoods that are able to explore the solution space more extensively and effectively while keeping computation complexity within acceptable levels. The most important advances in this domain derive from dynamic and adaptive neighborhood constructions originating in ejection chain methods and a special form of a candidate list design that constitutes the core of the filter-and-fan method. The objective of this paper is to lay out the general framework of the ejection chain and filter-and-fan methods and present applications to a number of important combinatorial optimization problems. The features of the methods that make them effective in these applications is expected to provide insights into solving challenging problems in other settings.

International audience; The purpose of this paper is to illustrate the diversity of combinatorial problems encountered in the design of wireless switching systems. This is done via a representative selection of examples of real problems along with their associated solution methods. It should be emphasized that all the solution methods presented in this paper are successfully operating in the field at the time of writing.

This is a summary of the most important results presented in the author’s PhD thesis (Spanjaard 2003). This thesis, written in French, was defended on 16 December 2003 and supervised by Patrice Perny. A copy is available from the author upon request. This thesis deals with the search for preferred solutions in combinatorial optimization problems (and more particularly graph problems). It aims at conciliating preference modelling and algorithmic concerns for decision aiding.

This is a summary of the Ph.D. thesis defended by the author on July 2012 at the University of Modena and Reggio Emilia. The thesis was supervised by Mauro Dell’Amico and co-supervised by Manuel Iori. The manuscript is written in English and is available from the author upon request at jose.diaz@unimore.it. The thesis addresses relevant optimization problems: the Bin Packing Problem, the Quadratic Assignment Problem, the large-scale Energy Management Problem, and the Node, Edge and Arc Routing Problem. To solve these problems exact, heuristic and local search techniques are proposed. The first problem studied is the Bin Packing Problem with Precedence Constraints (BPP-P): given a set of identical capacitated bins, a set of weighted items and a set of precedences among those items, we are interested in determining the minimum number of bins that can accommodate all items and can be ordered in such a way that all precedences are satisfied. The problem has a very intriguing combinatorial structure and models many assembly and scheduling issues. According to our knowledge the BPP-P has received little attention in the literature, and in the thesis we address it for the first time with exact solution methods. In particular, we develop reduction criteria, a large set of lower bounds, a variable neighborhood search upper bounding technique and a branch-and-bound algorithm (see Dell’Amico M., Diaz Diaz J.C. and Iori M. (2012): The Bin Packing Problem with Precedence Constraints, Operations Research, doi:10.1287/opre.1120.1109). We show the effectiveness of the proposed algorithms by means of extensive computational tests on benchmark instances and comparison with standard integer linear programming techniques. The second problem studied is to find the Friendly Bin Packing Instances without Integer Round-up Property. It is well known that the gap between the optimal values of bin packing and fractional bin packing, if the latter is rounded up to the closest integer, is almost always null. Known counterexamples to this for integer input values involve fairly large numbers. Specifically, the first one was derived in 1986 and involved a bin capacity of the order of a billion. Later in 1998 a counterexample with a bin capacity of the order of a million was found. In the thesis we show a large number of counterexamples with bin capacity of the order of a hundred, showing that the gap may be positive even for numbers which arise in customary applications. The associated instances are constructed starting from the Petersen graph and taking advantage of the fact that it is fractionally, but not integrally, 3-edge colorable. The third problem studied is the Single-finger Keyboard Layout Problem. The problem of designing new keyboards layouts able to improve the typing speed of an