Multi-objective Meta-heuristics for the Traveling Salesman Problem with Profits

We introduce and test a new approach for the bi-objective routing problem known as the traveling salesman problem with profits. This problem deals with the optimization of two conflicting objectives: the minimization of the tour length and the maximization of the collected profits. This problem has been studied in the form of a single objective problem, where either the two objectives have been combined or one of the objectives has been treated as a constraint. The purpose of our study is to find solutions to this problem using the notion of Pareto optimality, i.e. by searching for efficient solutions and constructing an efficient frontier. We have developed an ejection chain local search and combined it with a multi-objective evolutionary algorithm which is used to generate diversified starting solutions in the objective space. We apply our hybrid meta-heuristic to synthetic data sets and demonstrate its effectiveness by comparing our results with a procedure that employs one of the best single-objective approaches.      

Effects of diversity control in single-objective and multi-objective genetic algorithms

This paper covers an investigation on the effects of diversity control in the search performances of single-objective and multi-objective genetic algorithms. The diversity control is achieved by means of eliminating duplicated individuals in the population and dictating the survival of non-elite individuals via either a deterministic or a stochastic selection scheme. In the case of single-objective genetic algorithm, onemax and royal road R ₁ functions are used during benchmarking. In contrast, various multi-objective benchmark problems with specific characteristics are utilised in the case of multi-objective genetic algorithm. The results indicate that the use of diversity control with a correct parameter setting helps to prevent premature convergence in single-objective optimisation. Furthermore, the use of diversity control also promotes the emergence of multi-objective solutions that are close to the true Pareto optimal solutions while maintaining a uniform solution distribution along the Pareto front.     

The biobjective travelling purchaser problem

The purpose of this article is to present and solve the Biobjective Travelling Purchaser Problem, which consists in determining a route through a subset of markets in order to collect a set of products, minimizing the travel distance and the purchasing cost simultaneously. The most convenient purchase of the product in the visited markets is easily computed once the route has been determined. Therefore, this problem contains a finite set of solutions (one for each route) and the problem belongs to the field of the Biobjective Combinatorial Optimization. It is here formulated as a Biobjective Mixed Integer Linear Programming model with an exponential number of valid inequalities, and this model is used within a cutting plane algorithm to generate the set of all supported and non-supported efficient points in the objective space. A variant of the algorithm computes only supported efficient points. For each efficient point in the objective space exactly one Pareto optimal solution in the decision space is computed by solving a single-objective problem. Each of these single-objective problems, in turn, is solved by a specific branch-and-cut approach. A heuristic improvement based on saving previously generated cuts in a common cut-pool structure has also been developed with the aim of speeding up the algorithm performance. Results based on benchmark instances from literature show that the common cut-pool heuristic is very useful, and that the proposed algorithm manages to solve instances containing up to 100 markets and 200 different products. The general procedure can be extended to address other biobjective combinatorial optimization problems whenever a branch-and-cut algorithm is available to solve a single-objective linear combination of these criteria.     

Reducing the bandwidth of a sparse matrix with a genetic algorithm

Abstract

The matrix bandwidth minimization problem (MBMP) consists in finding a permutation of the lines and columns of a given sparse matrix in order to keep the non-zero elements in a band that is as close as possible to the main diagonal. Equivalently in terms of graph theory, MBMP is defined as the problem of finding a labelling of the vertices of a given graph G such that its bandwidth is minimized. In this paper, we propose an improved genetic algorithm (GA)-based heuristic for solving the matrix bandwidth minimization problem, motivated by its robustness and efficiency in a wide area of optimization problems. Extensively computational results are reported for an often used set of benchmark instances. The obtained results on the different instances investigated show improvement of the quality of the solutions and demonstrate the efficiency of our GA compared to the existing methods in the literature.     

Helper-objectives: Using multi-objective evolutionary algorithms for single-objective optimisation

This paper investigates the use of multi-objective methods to guide the search when solving single-objective optimisation problems with genetic algorithms. Using the job shop scheduling and travelling salesman problems as examples, experiments demonstrate that the use of helper-objectives (additional objectives guiding the search) significantly improves the average performance of a standard GA. The helper-objectives guide the search towards solutions containing good building blocks and help the algorithm escape local optima. The experiments reveal that the approach works if the number of simultaneously used helper-objectives is low. However, a high number of helper-objectives can be used in the same run by changing the helper-objectives dynamically. The experiments reveal that for the majority of problem instances studied, the proposed approach significantly outperforms a traditional GA.The experiments also demonstrate that controlling the proportion of non-dominated solutions in the population is very important when using helper-objectives, since the presence of too many non-dominated solutions removes the selection pressure in the algorithm.     

The timetable constrained distance minimization problem

We define the timetable constrained distance minimization problem (TCDMP) which is a sports scheduling problem applicable for tournaments where the total travel distance must be minimized. The problem consists of finding an optimal home-away assignment when the opponents of each team in each time slot are given. We present an integer programming, a constraint programming formulation and describe two alternative solution methods: a hybrid integer programming/constraint programming approach and a branch and price algorithm. We test all four solution methods on benchmark problems and compare the performance. Furthermore, we present a new heuristic solution method called the circular traveling salesman approach (CTSA) for solving the traveling tournament problem. The solution method is able to obtain high quality solutions almost instantaneously, and by applying the TCDMP, we show how the solutions can be further improved.     

Convergence of Fixed-Point Continuation Algorithms for Matrix Rank Minimization

The matrix rank minimization problem has applications in many fields, such as system identification, optimal control, low-dimensional embedding, etc. As this problem is NP-hard in general, its convex relaxation, the nuclear norm minimization problem, is often solved instead. Recently, Ma, Goldfarb and Chen proposed a fixed-point continuation algorithm for solving the nuclear norm minimization problem (Math. Program., doi:, 2009). By incorporating an approximate singular value decomposition technique in this algorithm, the solution to the matrix rank minimization problem is usually obtained. In this paper, we study the convergence/recoverability properties of the fixed-point continuation algorithm and its variants for matrix rank minimization. Heuristics for determining the rank of the matrix when its true rank is not known are also proposed. Some of these algorithms are closely related to greedy algorithms in compressed sensing. Numerical results for these algorithms for solving affinely constrained matrix rank minimization problems are reported.     

CHESS—Changing Horizon Efficient Set Search: A Simple Principle for Multiobjective Optimization

This paper presents a new concept for generating approximations to the non-dominated set in multiobjective optimization problems. The approximation set A is constructed by solving several single-objective minimization problems in which a particular function D(A, z) is minimized. A new algorithm to calculate D(A, z) is proposed.No general approach is available to solve the one-dimensional optimization problems, but metaheuristics based on local search procedures are used instead. Tests with multiobjective combinatorial problems whose non-dominated sets are known confirm that CHESS can be used to approximate the non-dominated set. Straightforward parallelization of the CHESS approach is illustrated with examples.The algorithm to calculate D(A, z) can be used in any other applications that need to determine Tchebycheff distances between a point and a dominant-free set.     

Minimizing shifts for personnel task scheduling problems: A three-phase algorithm

The personnel task scheduling problem is a subject of commercial interest which has been investigated since the 1950s. This paper proposes an effective and efficient three-phase algorithm for solving the shift minimization personnel task scheduling problem (SMPTSP). To illustrate the increased efficacy of the proposed algorithm over an existing algorithm, computational experiments are performed on a test problem set with characteristics motivated by employee scheduling applications. Experimental results show that the proposed algorithm outperforms the existing algorithm in terms of providing optimal solutions, improving upon most of the best-known solutions and revealing high-quality feasible solutions for those unsolved test instances in the literature.     

Heuristic approaches to determine base-stock levels in a serial supply chain with a single objective and with multiple objectives

This paper deals with the problem of determination of installation base-stock levels in a serial supply chain. The problem is treated first as a single-objective inventory-cost optimization problem, and subsequently as a multi-objective optimization problem by considering two cost components, namely, holding costs and shortage costs. Variants of genetic algorithms are proposed to determine the best base-stock levels in the single-objective case. All variants, especially random-key gene-wise genetic algorithm (RKGGA), show an excellent performance, in terms of convergence to the best base-stock levels across a variety of supply chain settings, with minimum computational effort. Heuristics to obtain base-stock levels are proposed, and heuristic solutions are introduced in the initial population of the RKGGA to expedite the convergence of the genetic search process. To deal with the multi-objective supply-chain inventory optimization problem, a simple multi-objective genetic algorithm is proposed to obtain a set of non-dominated solutions.     

Solving the bi-objective prize-collecting Steiner tree problem with the ϵ-constraint method

In this paper, we study the bi-objective prize-collecting Steiner tree problem, whose goal is to find a subtree that minimizes the edge costs for building that tree, and, at the same time, to maximize the collected node revenues. We propose to solve the problem using an ϵ-constraint algorithm. This is an iterative mixed-integer-programming framework that identifies one solution for every point on the Pareto front. In this framework, a branch-and-cut approach for the single-objective variant of the problem is enhanced with warm-start procedures that are used to (i) generate feasible solutions, (ii) generate violated cutting planes, and (iii) guide the branching process. Standard benchmark instances from the literature are used to assess the efficacy of our method.     

A new exclusion test for finding the global minimum

Exclusion algorithms have been used recently to find all solutions of a system of nonlinear equations or to find the global minimum of a function over a compact domain. These algorithms are based on a minimization condition that can be applied to each cell in the domain. In this paper, we consider Lipschitz functions of order α and give a new minimization condition for the exclusion algorithm. Furthermore, convergence and complexity results are presented for such algorithm.     

Global minimization of a generalized convex multiplicative function

This paper discusses an algorithm for generalized convex multiplicative programming problems, a special class of nonconvex minimization problems in which the objective function is expressed as a sum ofp products of two convex functions. It is shown that this problem can be reduced to a concave minimization problem with only 2p variables. An outer approximation algorithm is proposed for solving the resulting problem.     

Compression and denoising using <Emphasis Type="Italic">l</Emphasis><Subscript>0</Subscript>-norm

In this paper, we deal with l ₀-norm data fitting and total variation regularization for image compression and denoising. The l ₀-norm data fitting is used for measuring the number of non-zero wavelet coefficients to be employed to represent an image. The regularization term given by the total variation is to recover image edges. Due to intensive numerical computation of using l ₀-norm, it is usually approximated by other functions such as the l ₁-norm in many image processing applications. The main goal of this paper is to develop a fast and effective algorithm to solve the l ₀-norm data fitting and total variation minimization problem. Our idea is to apply an alternating minimization technique to solve this problem, and employ a graph-cuts algorithm to solve the subproblem related to the total variation minimization. Numerical examples in image compression and denoising are given to demonstrate the effectiveness of the proposed algorithm.     

An outer approximation method for minimizing the product of several convex functions on a convex set

This paper addresses the minimization of the product ofp convex functions on a convex set. It is shown that this nonconvex problem can be converted to a concave minimization problem withp variables, whose objective function value is determined by solving a convex minimization problem. An outer approximation method is proposed for obtaining a global minimum of the resulting problem. Computational experiments indicate that this algorithm is reasonable efficient whenp is less than 4.This research was partly supported by Grant-in-Aid for Scientific Research of the Ministry of Education, Science and Culture, Grant No. (C)03832018 and (C)04832010.     

An algorithm for the estimation of a regression function by continuous piecewise linear functions

The problem of the estimation of a regression function by continuous piecewise linear functions is formulated as a nonconvex, nonsmooth optimization problem. Estimates are defined by minimization of the empirical L ₂ risk over a class of functions, which are defined as maxima of minima of linear functions. An algorithm for finding continuous piecewise linear functions is presented. We observe that the objective function in the optimization problem is semismooth, quasidifferentiable and piecewise partially separable. The use of these properties allow us to design an efficient algorithm for approximation of subgradients of the objective function and to apply the discrete gradient method for its minimization. We present computational results with some simulated data and compare the new estimator with a number of existing ones.     

Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs

Motivated by just-in-time manufacturing, we consider a single machine scheduling problem with dual criteria, i.e., the minimization of the total weighted earliness subject to minimum number of tardy jobs. We discuss several dominance properties of optimal solutions. We then develop a heuristic algorithm with time complexity O(n³) and a branch and bound algorithm to solve the problem. The computational experiments show that the heuristic algorithm is effective in terms of solution quality in many instances while the branch and bound algorithm is efficient for medium-size problems.     

Vector and matrix apportionment problems and separable convex integer optimization

The problems of (bi-)proportional rounding of a nonnegative vector or matrix, resp., are written as particular separable convex integer minimization problems. Allowing any convex (separable) objective function we use the notions of vector and matrix apportionment problems. As a broader class of problems we consider separable convex integer minimization under linear equality restrictions Ax = b with any totally unimodular coefficient matrix A. By the total unimodularity Fenchel duality applies, despite the integer restrictions of the variables. The biproportional algorithm of Balinski and Demange (Math Program 45:193–210, 1989) is generalized and derives from the dual optimization problem. Also, a primal augmentation algorithm is stated. Finally, for the smaller class of matrix apportionment problems we discuss the alternating scaling algorithm, which is a discrete variant of the well-known Iterative Proportional Fitting procedure.     

About strongly polynomial time algorithms for quadratic optimization over submodular constraints

We present new strongly polynomial algorithms for special cases of convex separable quadratic minimization over submodular constraints. The main results are: an O(NM log(N ²/M)) algorithm for the problemNetwork defined on a network onM arcs andN nodes; an O(n logn) algorithm for thetree problem onn variables; an O(n logn) algorithm for theNested problem, and a linear time algorithm for theGeneralized Upper Bound problem. These algorithms are the best known so far for these problems. The status of the general problem and open questions are presented as well.This research has been supported in part by ONR grant N00014-91-J-1241.Corresponding author.     

Minimization of Linear Functionals Defined on Solutions of Large-Scale Discrete Ill-Posed Problems

The minimization of linear functionals defined on the solutions of discrete ill-posed problems arises, e.g., in the computation of confidence intervals for these solutions. In 1990, Eldén proposed an algorithm for this minimization problem based on a parametric programming reformulation involving the solution of a sequence of trust-region problems, and using matrix factorizations. In this paper, we describe MLFIP, a large-scale version of this algorithm where a limited-memory trust-region solver is used on the subproblems. We illustrate the use of our algorithm in connection with an inverse heat conduction problem. AMS subject classification (2000) 65F22