On local optima in multiobjective combinatorial optimization problems

In this article, local optimality in multiobjective combinatorial optimization is used as a baseline for the design and analysis of two iterative improvement algorithms. Both algorithms search in a neighborhood that is defined on a collection of sets of feasible solutions and their acceptance criterion is based on outperformance relations. Proofs of the soundness and completeness of these algorithms are given.     

离散优化与连续优化的复杂性概念

问题的复杂性概念起源于离散的图灵计算机理论的研究,在离散优化问题的研究中被广泛的接受.近期连续优化领域的很多文章中提及NP难这个概念.从而来对比介绍离散优化和连续优化研究中这两个概念的差异.     

Case-based reasoning for repetitive combinatorial optimization problems, part I: Framework

This article presents a case-based reasoning approach for the development of learning heuristics for solving repetitive operations research problems. We first define the subset of problems we will consider in this work: repetitive combinatorial optimization problems. We then present several general forms that can be used to select previously solved problems that might aid in the solution of the current problem, and several different techniques for actually using this information to derive a solution for the current problem. We describe both fixed forms and forms that have the ability to change as we solve more problems. A simple example for the 0–1 knapsack problem is presented.     

Approximation algorithms for combinatorial fractional programming problems

We are concerned with a combinatorial optimization problem which has the ratio of two linear functions as the objective function. This type of problems can be solved by an algorithm that uses an auxiliary problem with a parametrized linear objective function. Because of its combinatorial nature, however, it is often difficult to solve the auxiliary problem exactly. In this paper, we propose an algorithm which assumes that the auxiliary problems are solved only approximately, and prove that it gives an approximate solution to the original problem, of which the accuracy is at least as good as that of approximate solutions to the auxiliary problems. It is also shown that the time complexity is bounded by the square of the computation time of the approximate algorithm for the auxiliary problem. As an example of the proposed algorithm, we present a fully polynomial time approximation scheme for the fractional 0–1 knapsack problem.     

Models and algorithms for combinatorial optimization problems arising in railway applications

This is a summary of the author’s PhD thesis supervised by Alberto Caprara and Paolo Toth and defended on 29 May 2007 at the Università di Bologna. The thesis is written in English and is available from the author upon request. This work deals with Railway Optimization, and in particular it focuses on the Train Timetabling Problem (in the basic version on a corridor and in the extension to a railway network), and on the Train Unit Assignment Problem. Integer Linear Programming (ILP) formulations are proposed for both problems, and their continuous and Lagrangian relaxations are used to obtain optimal and heuristic solutions to real-world instances.      

An Efficient Algorithm for the Knapsack Sharing Problem

The Knapsack Sharing Problem (KSP) is an NP-Hard combinatorial optimization problem, admitted in numerous real world applications. In the KSP, we have a knapsack of capacity c and a set of n objects, namely N, where each object j, j = 1,...,n, is associated with a profit p _j and a weight w _j. The set of objects N is composed of m different classes of objects J _i, i = 1,...,m, and N = ^m _i=1 J _i. The aim is to determine a subset of objects to be included in the knapsack that realizes a max-min value over all classes.In this article, we solve the KSP using an approximate solution method based upon tabu search. First, we describe a simple local search in which a depthparameter and a tabu list are used. Next, we enhance the algorithm by introducing some intensifying and diversifying strategies. The two versions of the algorithm yield satisfactory results within reasonable computational time. Extensive computational testing on problem instances taken from the literature shows the effectiveness of the proposed approach.     

Convergent sequences of sparse graphs: A large deviations approach

Models based on sparse graphs are of interest to many communities: they appear as basic models in combinatorics, probability theory, optimization, statistical physics, information theory, and more applied fields of social sciences and economics. Different notions of similarity (and hence convergence) of sparse graphs are of interest in different communities. In probability theory and combinatorics, the notion of Benjamini‐Schramm convergence, also known as left‐convergence, is used quite frequently. Statistical physicists are interested in the the existence of the thermodynamic limit of free energies, which leads naturally to the notion of right‐convergence. Combinatorial optimization problems naturally lead to so‐called partition convergence, which relates to the convergence of optimal values of a variety of constraint satisfaction problems. The relationship between these different notions of similarity and convergence is, however, poorly understood. In this paper we introduce a new notion of convergence of sparse graphs, which we call Large Deviations or LD‐convergence, and which is based on the theory of large deviations. The notion is introduced by “decorating” the nodes of the graph with random uniform i.i.d. weights and constructing corresponding random measures on and . A graph sequence is defined to be converging if the corresponding sequence of random measures satisfies the Large Deviations Principle with respect to the topology of weak convergence on bounded measures on . The corresponding large deviations rate function can be interpreted as the limit object of the sparse graph sequence. In particular, we can express the limiting free energies in terms of this limit object. We then establish that LD‐convergence implies the other three notions of convergence discussed above, and at the same time establish several previously unknown relationships between the other notions of convergence. In particular, we show that partition‐convergence does not imply left‐ or right‐convergence, and that right‐convergence does not imply partition‐convergence. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 52–89, 2017     

Forest management models and combinatorial algorithms: analysis of state of the art

Linear Programming and Mixed Integer Linear Programs have been used for forest planning since the 60's to support decision making on forest harvesting and management. In particular, during the last two decades of forest management there has been an increased interest in spatial issues. Further, new environmental concerns, such as resource sustainability and wildlife protection, impose that increased attention be paid to activities carried out on the ground. Road building needed for access also requires spatial definiton. As a result, more complex models must be used. We discuss the issues which have led to the combinatorial nature of some main forest management problems and the solution algorithms that have been proposed for these problems, including local search heuristics, random search approaches, strengthening of mixed integer model formulations and Lagrangian relaxation. In this survey, we discuss which of the proposed approaches have been used succesfully, the advantages and shortcomings of each and what are still open research problems. This revised version was published online in June 2006 with corrections to the Cover Date.     

Diversification strategies in tabu search algorithms for the maximum clique problem

The purpose of this study is to develop some understanding of the benefits that can be derived from the inclusion of diversification strategies in tabu search methods. To do so, we discuss the implementation of various diversification strategies in several tabu search heuristics developed for the maximum clique problem. Computational results on a large set of randomly generated test problems are reported and compared to assess the impact of these techniques on solution quality and running time.     

Theory and application of conflict resolution with hybrid preference in colored graphs

An algebraic approach is proposed to calculate stabilities in a colored graph with hybrid preference. The algebraic approach establishes a hybrid framework for stability analysis by combining strength of preference and unknown preference. The hybrid system is more general than existing models, which consider preference strength and preference uncertainty separately. Within the hybrid preference structure, matrix representations of four basic stabilities in a colored graph are extended to include mild, strong, and uncertain preference and algorithms are developed to calculate efficiently the inputs essential to the stability definitions. A specific case study, including multiple decision makers and hybrid preference, is used to illustrate how the proposed method can be applied in practice.     

Strategies of node selection in search procedures for solving combinatorial optimization problems: A survey and a general formalization

Currently, most combinatorial optimization problems have to be solved, if the optimum solution is sought, using general techniques to explore the space of feasible solutions and, more specifically, through exploratory enumerative procedures in trees and search graphs. The objective of this work is to propose a survey and a general formalization of the selection strategy of the next node to explore, a feature that is common to all these optimization procedures. This research has been partially supported by TAP98-0494 project     

Branch and win: OR tree search algorithms for solving combinatorial optimisation problems

Currently, most combinatorial optimisation problems have to be solved, if the optimum solution is sought, using general techniques to explore the space of feasible solutions and, more specifically, through exploratory enumerative procedures in trees and search graphs. We propose Branch and Win, a general formulation for understanding and synthesising the different tree search procedures that have been presented in the literature of operations research as well as in that of artificial intelligence. Several general ideas are also presented, whose application allows designing new hybrid search algorithms, in order to implement the procedure.     

Adaptive and restarting techniques-based algorithms for circular packing problems

In this paper, we study the circular packing problem (CPP) which consists of packing a set of non-identical circles of known radii into the smallest circle with no overlap of any pair of circles. To solve CPP, we propose a three-phase approximate algorithm. During its first phase, the algorithm successively packs the ordered set of circles. It searches for each circle’s “best” position given the positions of the already packed circles where the best position minimizes the radius of the current containing circle. During its second phase, the algorithm tries to reduce the radius of the containing circle by applying (i) an intensified search, based on a reduction search interval, and (ii) a diversified search, based on the application of a number of layout techniques. Finally, during its third phase, the algorithm introduces a restarting procedure that explores the neighborhood of the current solution in search for a better ordering of the circles. The performance of the proposed algorithm is evaluated on several problem instances taken from the literature.     

Local search algorithms for finding the Hamiltonian completion number of line graphs

Given a graph G=(V,E), the Hamiltonian completion number of G, HCN(G), is the minimum number of edges to be added to G to make it Hamiltonian. This problem is known to be -hard even when G is a line graph. In this paper, local search algorithms for finding HCN(G) when G is a line graph are proposed. The adopted approach is mainly based on finding a set of edge-disjoint trails that dominates all the edges of the root graph of G. Extensive computational experiments conducted on a wide set of instances allow to point out the behavior of the proposed algorithms with respect to both the quality of the solutions and the computation time.     

Sparse graphs: Metrics and random models

Recently, Bollobás, Janson and Riordan introduced a family of random graph models producing inhomogeneous graphs with n vertices and Θ(n) edges whose distribution is characterized by a kernel, i.e., a symmetric measurable function κ: [0, 1]² → [0, ∞). To understand these models, we should like to know when different kernels κ give rise to “similar” graphs, and, given a real‐world network, how “similar” is it to a typical graph G(n, κ) derived from a given kernel κ. The analogous questions for dense graphs, with Θ(n²) edges, are answered by recent results of Borgs, Chayes, Lovász, Sós, Szegedy and Vesztergombi, who showed that several natural metrics on graphs are equivalent, and moreover that any sequence of graphs converges in each metric to a graphon, i.e., a kernel taking values in [0, 1]. Possible generalizations of these results to graphs with o(n²) but ω(n) edges are discussed in a companion article [Bollobás and Riordan, London Math Soc Lecture Note Series 365 (2009), 211–287]; here we focus only on graphs with Θ(n) edges, which turn out to be much harder to handle. Many new phenomena occur, and there are a host of plausible metrics to consider; many of these metrics suggest new random graph models and vice versa. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 1‐38, 2011     

Tabu Machine: A New Neural Network Solution Approach for Combinatorial Optimization Problems

A new artificial neural network solution approach is proposed to solve combinatorial optimization problems. The artificial neural network is called the Tabu Machine because it has the same structure as the Boltzmann Machine does but uses tabu search to govern its state transition mechanism. Similar to the Boltzmann Machine, the Tabu Machine consists of a set of binary state nodes connected with bidirectional arcs. Ruled by the transition mechanism, the nodes adjust their states in order to search for a global minimum energy state. Two combinatorial optimization problems, the maximum cut problem and the independent set problem, are used as examples to conduct a computational experiment. Without using overly sophisticated tabu search techniques, the Tabu Machine outperforms the Boltzmann Machine in terms of both solution quality and computation time.     

Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms

A minimal blocker in a bipartite graph G is a minimal set of edges the removal of which leaves no perfect matching in G. We give an explicit characterization of the minimal blockers of a bipartite graph G. This result allows us to obtain a polynomial delay algorithm for finding all minimal blockers of a given bipartite graph. Equivalently, we obtain a polynomial delay algorithm for listing the anti‐vertices of the perfect matching polytope of G. We also provide generation algorithms for other related problems, including d‐factors in bipartite graphs, and perfect 2‐matchings in general graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 209–232, 2006     

Improved FPT algorithms for weighted independent set in bull-free graphs

Very recently, Thomassé et al. (2017) have given an FPT algorithm for Weighted Independent Set in bull-free graphs parameterized by the weight of the solution, running in time $2^{O\left(k^5\right)}?n^9$. In this article we improve this running time to $2^{O\left(k^2\right)}?n^7$. As a byproduct, we also improve the previous Turing-kernel for this problem from $O\left(k^5\right)$ to $O\left(k^2\right)$. Furthermore, for the subclass of bull-free graphs without holes of length at most $2p?1$ for $p\ge 3$, we speed up the running time to $2^{O(k?k^{\frac{1}{p?1}})}?n^7$. As $p$ grows, this running time is asymptotically tight in terms of $k$, since we prove that for each integer $p\ge 3$, Weighted Independent Set cannot be solved in time $2^{o\left(k\right)}?n^{O\left(1\right)}$ in the class of $\{\text{bull},C_4,\dots ,C_{2p?1}\}$-free graphs unless the ETH fails.     

Distributed algorithms for weighted problems in sparse graphs

We study distributed algorithms for three graph-theoretic problems in weighted trees and weighted planar graphs. For trees, we present an efficient deterministic distributed algorithm which finds an almost exact approximation of a maximum-weight matching. In addition, in the case of trees, we show how to approximately solve the minimum-weight dominating set problem. For planar graphs, we present an almost exact approximation for the maximum-weight independent set problem.