A two-phase algorithm for the biobjective integer minimum cost flow problem

We present an algorithm to compute a complete set of efficient solutions for the biobjective integer minimum cost flow problem. We use the two phase method, with a parametric network simplex algorithm in phase 1 to compute all non-dominated extreme points. In phase 2, the remaining non-dominated points (non-extreme supported and non-supported) are computed using a k best flow algorithm on single-objective weighted sum problems.     

Adaptive weighted sum method for multiobjective optimization: a new method for Pareto front generation

This paper presents an adaptive weighted sum (AWS) method for multiobjective optimization problems. The method extends the previously developed biobjective AWS method to problems with more than two objective functions. In the first phase, the usual weighted sum method is performed to approximate the Pareto surface quickly, and a mesh of Pareto front patches is identified. Each Pareto front patch is then refined by imposing additional equality constraints that connect the pseudonadir point and the expected Pareto optimal solutions on a piecewise planar hypersurface in the -dimensional objective space. It is demonstrated that the method produces a well-distributed Pareto front mesh for effective visualization, and that it finds solutions in nonconvex regions. Two numerical examples and a simple structural optimization problem are solved as case studies. Presented as paper AIAA-2004-4322 at the 10th AIAA-ISSMO Multidisciplinary Analysis and Optimization Conference, Albany, New York, August 30–September 1, 2004     

Bound sets for biobjective combinatorial optimization problems

In this paper we introduce the concept of bound sets for multiobjective discrete optimization. We prove general results on lower and upper bound sets for combinatorial optimization problems with multiple objectives. We present general algorithms for constructing lower and upper bound sets for biobjective problems and provide numerical results on five different problem types.     

An evolutionary algorithm for multi-criteria inverse optimal value problems using a bilevel optimization model

Given a linear program, a desired optimal objective value, and a set of feasible cost vectors, one needs to determine a cost vector of the linear program such that the corresponding optimal objective value is closest to the desired value. The problem is always known as a standard inverse optimal value problem. When multiple criteria are adopted to determine cost vectors, a multi-criteria inverse optimal value problem arises, which is more general than the standard case. This paper focuses on the algorithmic approach for this class of problems, and develops an evolutionary algorithm based on a dynamic weighted aggregation method. First, the original problem is converted into a bilevel program with multiple upper level objectives, in which the lower level problem is a linear program for each fixed cost vector. In addition, the potential bases of the lower level program are encoded as chromosomes, and the weighted sum of the upper level objectives is taken as a new optimization function, by which some potential nondominated solutions can be generated. In the design of the evolutionary algorithm some specified characteristics of the problem are well utilized, such as the optimality conditions. Some preliminary computational experiments are reported, which demonstrates that the proposed algorithm is efficient and robust.     

An algorithm for the biobjective integer minimum cost flow problem

In this paper, we study the single commodity flow problems, optimizing two objectives simultaneously, where the flow values must be integer values. We propose a method that finds all the efficient integer points in the objective space. Our algorithm performs two phases. In the first phase, all integer points on the efficient boundary are found and in the second phase, the efficient integer points that do not lie on the efficient boundary are calculated. In addition, we carry out a computational experiment showing that the number of efficient integer solutions that do not lie on the efficient boundary is greater than the number of integer solutions on the efficient boundary.Scope and purposeIn many combinatorial optimization problems, the selection of the optimum solution takes into account more than one criterion. For example, in transportation problems or in network flows problems, the criteria that can be considered are the minimization of the cost for selected routes, the minimization of arrival times at the destinations, the minimization of the deterioration of goods, the minimization of the load capacity that would not be used in the selected vehicles, the maximization of safety, reliability, etc. Often, these criteria are in conflict and for this reason, a multiobjective network flow formulation of the problem is necessary. The solution to this problem is searched for among the set of efficient points. Although multiobjective network flow problems can be solved using the techniques available for the multiobjective linear programming problem, network-based methods are computationally better. The multicriteria minimum cost flow problem has already merited the attention of several authors and the case which has been considered in literature is that which has two objectives, where the continuous flow values are permissible. However, the integer case of the biobjective minimum cost flow problem has scarcely been studied. Whereas, in many real network flow problems, integer values on flow values are required. In this paper, we propose an approach to solve the biobjective integer minimum cost flow problem. An algorithm to obtain all efficient integer solutions of this problem is introduced. This method is characterized by the use of the classic resolution tools of network flow problems, such as the network simplex method. It does not utilize the biobjective integer linear programming methodology. Furthermore, the method does not calculate dominated solutions, so it is not necessary to incorporate tools to eliminate dominated solutions.     

Adaptive weighted-sum method for bi-objective optimization: Pareto front generation

This paper presents a new method that effectively determines a Pareto front for bi-objective optimization with potential application to multiple objectives. A traditional method for multiobjective optimization is the weighted-sum method, which seeks Pareto optimal solutions one by one by systematically changing the weights among the objective functions. Previous research has shown that this method often produces poorly distributed solutions along a Pareto front, and that it does not find Pareto optimal solutions in non-convex regions. The proposed adaptive weighted sum method focuses on unexplored regions by changing the weights adaptively rather than by using a priori weight selections and by specifying additional inequality constraints. It is demonstrated that the adaptive weighted sum method produces well-distributed solutions, finds Pareto optimal solutions in non-convex regions, and neglects non-Pareto optimal solutions. This last point can be a potential liability of Normal Boundary Intersection, an otherwise successful multiobjective method, which is mainly caused by its reliance on equality constraints. The promise of this robust algorithm is demonstrated with two numerical examples and a simple structural optimization problem.     

Multi-objective optimization with fuzzy measures and its application to flow-shop scheduling

Most of the research in multi-objective scheduling optimization uses the classical weighted arithmetic mean operator to aggregate the various optimization criteria. However, there are scheduling problems where criteria are considered interact and thus a different operator should be adopted. This paper is devoted to the search of Pareto-optimal solutions in a tri-criterion flow-shop scheduling problem (FSSP) considering the interactions among the objectives. A new hybrid meta-heuristic is proposed to solve the problem which combines a genetic algorithm (GA) for solutions evolution and a reduced variable neighborhood search (RVNS) technique for fast solution improvement. To deal with the interactions among the three criteria the discrete Choquet integral method is adopted as a means to aggregate the criteria in the fitness function of each individual solution. Experimental comparisons (over public available FSSP test instances) with five existing multi-objective evolutionary algorithms (including the well known SPEA2 and NSGAII algorithms as well as the recently published L-NSGA algorithm) showed a superior performance for the developed approach in terms of diversity and domination of solutions.     

Choquet integral for criteria aggregation in the flexible job-shop scheduling problems

Most complex scheduling problems are combinatorial problems and difficult to solve. That is why, several methods focus on the optimization according to a single criterion such as makespan, workloads of machines, waiting times, etc. In this paper, the Choquet integral is introduced as a general tool for dealing with multiple criteria decision making and used in optimization flexible job-shop scheduling problems. The considered optimization problem is based of the Genetic Algorithm (GA) used as objective function the Choquet integral for criteria aggregation. Then lower bounds are defined for each criterion. Presented examples illustrate theoretical considerations and show the efficiency of the proposed approach.     

Inheritable genetic algorithm for biobjective 0/1 combinatorial optimization problems and its applications.

In this paper, we formulate a special type of multiobjective optimization problems, named biobjective 0/1 combinatorial optimization problem BOCOP, and propose an inheritable genetic algorithm IGA with orthogonal array crossover (OAX) to efficiently find a complete set of nondominated solutions to BOCOP. BOCOP with n binary variables has two incommensurable and often competing objectives: minimizing the sum r of values of all binary variables and optimizing the system performance. BOCOP is NP-hard having a finite number C(n, r) of feasible solutions for a limited number r. The merits of IGA are threefold as follows: 1) OAX with the systematic reasoning ability based on orthogonal experimental design can efficiently explore the search space of C(n, r); 2) IGA can efficiently search the space of C(n, r+/-1) by inheriting a good solution in the space of C(n, r); and 3) The single-objective IGA can economically obtain a complete set of high-quality nondominated solutions in a single run. Two applications of BOCOP are used to illustrate the effectiveness of the proposed algorithm: polygonal approximation problem (PAP) and the problem of editing a minimum reference set for nearest neighbor classification (MRSP). It is shown empirically that IGA is efficient in finding complete sets of nondominated solutions to PAP and MRSP, compared with some existing methods.     

Computing all efficient solutions of the biobjective minimum spanning tree problem

A common way of computing all efficient (Pareto optimal) solutions for a biobjective combinatorial optimisation problem is to compute first the extreme efficient solutions and then the remaining, non-extreme solutions. The second phase, the computation of non-extreme solutions, can be based on a “k-best” algorithm for the single-objective version of the problem or on the branch-and-bound method. A k-best algorithm computes the k-best solutions in order of their objective values. We compare the performance of these two approaches applied to the biobjective minimum spanning tree problem. Our extensive computational experiments indicate the overwhelming superiority of the k-best approach. We propose heuristic enhancements to this approach which further improve its performance.     

Iterative Dutch combinatorial auctions

The combinatorial auction problem can be modeled as a weighted set packing problem. Similarly the reverse combinatorial auction can be modeled as a weighted set covering problem. We use the set packing and set covering formulations to suggest novel iterative Dutch auction algorithms for combinatorial auction problems. We use generalized Vickrey auctions (GVA) with reserve prices in each iteration. We prove the convergence of the algorithms and show that the solutions obtained using the algorithms lie within provable worst case bounds. We conduct numerical experiments to show that in general the solutions obtained using these algorithms are much better than the theoretical bounds.     

Multi-objective genetic algorithm and its applications to flowshop scheduling

In this paper, we propose a multi-objective genetic algorithm and apply it to flowshop scheduling. The characteristic features of our algorithm are its selection procedure and elite preserve strategy. The selection procedure in our multi-objective genetic algorithm selects individuals for a crossover operation based on a weighted sum of multiple objective functions with variable weights. The elite preserve strategy in our algorithm uses multiple elite solutions instead of a single elite solution. That is, a certain number of individuals are selected from a tentative set of Pareto optimal solutions and inherited to the next generation as elite individuals. In order to show that our approach can handle multi-objective optimization problems with concave Pareto fronts, we apply the proposed genetic algorithm to a two-objective function optimization problem with a concave Pareto front. Last, the performance of our multi-objective genetic algorithm is examined by applying it to the flowshop scheduling problem with two objectives: to minimize the makespan and to minimize the total tardiness. We also apply our algorithm to the flowshop scheduling problem with three objectives: to minimize the makespan, to minimize the total tardiness, and to minimize the total flowtime.     

浅谈求解组合优化问题的几种近似算法

现实生活中,为了最大限度地利用资源、节省开支,出现了许多最优化利用资源的问题,往往是要求求出最大值或最小值的。在优化问题中,比较常见的是组合优化问题。针对此类问题,也出现了不少求解的算法。该文对其中比较常用的几种近似算法进行了总结,并通过一种典型的组合优化问题——装箱问题的实例对各算法的优劣进行了比较。     

Greedy algorithms for a class of knapsack problems with binary weights

In this article we identify a class of two-dimensional knapsack problems with binary weights and related three-criteria unconstrained combinatorial optimization problems that can be solved in polynomial time by greedy algorithms. Starting from the knapsack problem with two equality constraints we show that this problem can be solved efficiently by using an appropriate partitioning of the items with respect to their binary weights. Based on the results for this problem we derive an algorithm for the three-criteria unconstrained combinatorial optimization problem with two binary objectives that explores the connectedness of the set of efficient knapsacks with respect to a combinatorial definition of adjacency. Furthermore, we prove that our approach is asymptotically optimal and provide extensive computational experiments that shows that we can solve the three-criteria problem with up to one million items in less than half an hour. Finally, we derive an efficient algorithm for the two-dimensional knapsack problems with binary constraints that only takes into account the results we obtained for the unconstrained three-criteria problem with binary weights.     

Solving constrained combinatorial optimization problems via importance sampling in the grand canonical ensemble

Combinatorial optimization problems are usually NP-hard. These problems are generally tackled by heuristic or branch-and-bound methods. The aim of this paper is to tackle constrained combinatorial optimization problems by importance Monte Carlo sampling. For this, we show that every constrained combinatorial optimization problem can be represented by a thermodynamical system in a suitable grand canonical ensemble given by the quantities of temperature, volume, and chemical potential. In order to find optimum solutions of the optimization problem, the grand canonical Monte Carlo method can be applied to the corresponding thermodynamical system. This method will amount to importance sampling, i.e. good feasible solutions of the optimization problem will be preferably sampled, provided that the intensive quantities of temperature and chemical potential are appropriately chosen. Our approach extends the standard importance sampling approach in the canonical ensemble to tackle unconstrained combinatorial optimization problems. The knapsack problem is considered as a prototype example.     

The multiobjective multidimensional knapsack problem: a survey and a new approach

The knapsack problem (KP) and its multidimensional version (MKP) are basic problems in combinatorial optimization. In this paper, we consider their multiobjective extension (MOKP and MOMKP), for which the aim is to obtain or approximate the set of efficient solutions. In the first step, we classify and briefly describe the existing works that are essentially based on the use of metaheuristics. In the second step, we propose the adaptation of the two‐phase Pareto local search (2PPLS) to the resolution of the MOMKP. With this aim, we use a very large scale neighborhood in the second phase of the method, that is the PLS. We compare our results with state‐of‐the‐art results and show that the results we obtained were never reached before by heuristics for biobjective instances. Finally, we consider the extension to three‐objective instances.     

基于线性判别分析的Choquet积分的符号模糊测度提取

在解决分类问题时,建立在Choquet积分上的分类器以其非线性和不可加性的特点,扮演着越来越重要的角色。由于Choquet积分中的符号模糊测度可以描述各特征对结果的影响,因此Choquet积分在解决数据分类及融合 问题方面具有显著的优势。但是,关于Choquet积分符号模糊测度值的求解,学术界一直缺乏有效的方法。目前最常用的方法是遗传算法,但是遗传算法在解决符号模糊测度值的优化问题时存在算法较为复杂、耗时较长等缺陷。由于符号模糊测度值在Choquet积分分类器中是决定性的重要参数,因此设计出一种有效的符号模糊测度提取方法十分必要。文中提出基于线性判别分析的Choquet积分符号模糊测度的提取方法,推导出在分类问题下Choquet积分的符号模糊测度值的解析式表达,其能够有效、快速地得出关键性参数。分别在人工数据集及基准实际数据集上进行测试与验证,实验结果表明所提方法能有效解决Choquet积分分类器中符号模糊测度的优化问题。     

Minimizing total weighted flowtime subject to minimum makespan on two identical parallel machines

We study the problem of scheduling n jobs on two identical parallel processors or machines where an optimal schedule is defined as one with the shortest total weighted flowtime (i.e., the sum of the weighted completion time of all jobs), among the set of schedules with minimum makespan (i.e., the completion time of the last job finished). We present a two phase non-linear Integer Programming formulation for its solution, admittedly not to be practical or useful in most cases, but theoretically interesting since it models the problem. Thus, as an alternative, we propose an optimization algorithm, for small problems, and a heuristic, for large problems, to find optimal or near optimal solutions. Furthermore, we perform a computational study to evaluate and compare the effectiveness of the two proposed methods.     

An Experimental Study of Algorithms for Weighted Completion Time Scheduling

We consider the total weighted completion time scheduling problem for parallel identical machines and precedence constraints, P| prec|\sum w _i C _i . This important and broad class of problems is known to be NP-hard, even for restricted special cases, and the best known approximation algorithms have worst-case performance that is far from optimal. However, little is known about the experimental behavior of algorithms for the general problem. This paper represents the first attempt to describe and evaluate comprehensively a range of weighted completion time scheduling algorithms. We first describe a family of combinatorial scheduling algorithms that optimally solve the single-machine problem, and show that they can be used to achieve good performance for the multiple-machine problem. These algorithms are efficient and find schedules that are on average within 1.5\percent of optimal over a large synthetic benchmark consisting of trees, chains, and instances with no precedence constraints. We then present several ways to create feasible schedules from nonintegral solutions to a new linear programming relaxation for the multiple-machine problem. The best of these linear programming-based approaches finds schedules that are within 0.2\percent of optimal over our benchmark. Finally, we describe how the scheduling phase in profile-based program compilation can be expressed as a weighted completion time scheduling problem and apply our algorithms to a set of instances extracted from the SPECint95 compiler benchmark. For these instances with arbitrary precedence constraints, the best linear programming-based approach finds optimal solutions in 78\percent of cases. Our results demonstrate that careful experimentation can help lead the way to high quality algorithms, even for difficult optimization problems. Received October 30, 1998; revised March 28, 2001.     

Fuzzy programming for mixed-integer optimization problems

Mixed-integer optimization problems belong to the group of NP-hard combinatorial problems. Therefore, they are difficult to search for global optimal solutions. Mixed-integer optimization problems are always described by precise mathematical programming models. However, many practical mixed-integer optimization problems have inherited a more or less imprecise nature. Under these circumstances, if we take into account the flexibility of the constraints and the fuzziness of the objectives, the original mixed-integer optimization problems can be formulated as fuzzy mixed-integer optimization problems. Mixed-integer hybrid differential evolution (MIHDE) is an evolutionary search algorithm which has been successfully applied to many complex mixed-integer optimization problems. In this article, a fuzzy mixed-integer mathematical programming model is developed to formulate the fuzzy mixed-integer optimization problem. In addition the MIHDE is introduced to solve the fuzzy mixed-integer programming problem. Finally, the illustrative example shows that satisfactory results can be obtained by the proposed method. This demonstrates that MIHDE can effectively handle fuzzy mixed-integer optimization problems.