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.     

The biobjective integer minimum cost flow problem—incorrectness of Sedeño-Noda and Gonzàlez-Martin's algorithm

In this paper, we show with a counterexample, that the method proposed by Sedeño-Noda and Gonzàlez-Martin for the biobjective integer minimum flow problem is not able to find all efficient integer points in objective space.     

Stability analysis of efficient solutions in multiobjective integer programming: A case study in load management

This paper presents a multiobjective linear integer programming model for supporting the choice of remote load control strategies in electric distribution network management. The model takes into account the main concerns in load management, considering three objective functions: minimization of the peak demand as perceived by the distribution network dispatch center, maximization of the utility profit associated with the energy services delivered by the controlled loads and minimization of the discomfort caused to consumers. The problem was analyzed using an interactive reference point method for multiobjective integer (and mixed-integer) linear programming. This approach exploits the use of the branch-and-bound algorithm for solving the reference point scalarizing programs through which efficient solutions are computed. Post-optimality techniques enable a stability analysis of the efficient solutions by means of computing and displaying graphically sets of reference points that correspond to the same solution.     

Multicriteria distribution network planning using simulated annealing

The classical long-range distribution network planning problem involves deciding network investments to meet future demand at a minimum cost while meeting technical restrictions (thermal limits and maximum voltage drop). The decision whether to construct facilities and branches leads to a mixed integer programming problem with a large number of decision variables. The great deal of uncertainty associated with data that cannot be modeled using probabilistic methods leads to the use of fuzzy models to capture the uncertainty. In addition, several criteria must be taken into account that is resulting in the problem being fuzzy multiobjective. The combinatorial nature of the problem limits the use of traditional mathematical tools to limited size problems. This contribution presents a methodology that generates a sample of efficient solutions for the fuzzy multiobjective problem, based on a meta-heuristic, simulated annealing (SA). The results obtained with this approach are shown to be satisfactory compared to other methods under similar conditions.     

Finding extreme supported solutions of biobjective network flow problems: An enhanced parametric programming approach

We address the problem of determining a complete set of extreme supported efficient solutions of biobjective minimum cost flow (BMCF) problems. A novel method improving the classical parametric method for this biobjective problem is proposed. The algorithm runs in O(Nn(m + nlogn)) time determining all extreme supported non-dominated points in the outcome space and one extreme supported efficient solution associated with each one of them. Here n is the number of nodes, m is the number of arcs and N is the number of extreme supported non-dominated points in outcome space for the BMCF problem. The memory space required by the algorithm is O(n + m) when the extreme supported efficient solutions are not required to be stored in RAM. Otherwise, the algorithm requires O(N + m) space. Extensive computational experiments comparing the performance of the proposed method and a standard parametric network simplex method are presented.     

Dual problem of sorptive barrier design with a multiobjective approach

Sorptive barrier technology is a recently developed tool to separate hazardous contaminants from friendly environment. The design of sorptive barrier refers to configuring different amendments with sorptive ability of organic pollutant, which is an integer programming problem and a relatively time consuming problem as well. In this paper, sorptive barrier design is newly modeled in a biobjective optimization approach, in which the dual problem of sorptive barrier design is deduced. The objectives are to minimize the financial cost and the amount of pollutant leaking through barriers. Then an opposition-based adaptive multiobjective differential evolution algorithm (MODEA-OA) is applied to handle the proposed model. The Pareto optimal front obtained by MODEA-OA spreads accurately and evenly in all three instances tested. To select extreme optimal solutions, the original and dual sorptive barrier design problems can be solved simultaneously. This study suggests that modeling barrier design as a multiobjective optimization problem is an effective approach.

     

A Cut-Based Algorithm for the Nonlinear Dual of the Minimum Cost Network Flow Problem

We consider a convex, or nonlinear, separable minimization problem with constraints that are dual to the minimum cost network flow problem. We show how to reduce this problem to a polynomial number of minimum s,t-cut problems. The solution of the reduced problem utilizes the technique for solving integer programs on monotone inequalities in three variables, and a so-called proximity-scaling technique that reduces a convex problem to its linear objective counterpart. The problem is solved in this case in a logarithmic number of calls, O(log U), to a minimum cut procedure, where U is the range of the variables. For a convex problem on n variables the minimum cut is solved on a graph with O(n²) nodes. Among the consequences of this result is a new cut-based scaling algorithm for the minimum cost network flow problem. When the objective function is an arbitrary nonlinear function we demonstrate that this constrained problem is solved in pseudopolynomial time by applying a minimum cut procedure to a graph on O(nU) nodes.     

Minimum cost multiple multicast network coding with quantized rates

In this paper, we consider multiple multicast sessions with intra-session network coding where rates over all links are integer multiples of a basic rate. Although having quantized rates over communication links is quite common, conventional minimum cost network coding problem cannot generally result in quantized solutions. In this research, the problem of finding minimum cost transmission for multiple multicast sessions with network coding is addressed. It is assumed that the rate of coded packet injection at every link of each session takes quantized values. First, this problem is formulated as a mixed integer linear programming problem, and then it is proved that this problem is strongly NP-hard on general graphs. In order to obtain an exact solution for the problem, an effective and efficient scheme based on Benders decomposition is developed. Using this scheme the problem is decomposed into a master integer programming problem and several linear programming sub-problems. The efficiency of the proposed scheme is subsequently evaluated by numerical results on random networks.     

Choquet optimal set in biobjective combinatorial optimization

We study in this paper the generation of the Choquet optimal solutions of biobjective combinatorial optimization problems. Choquet optimal solutions are solutions that optimize a Choquet integral. The Choquet integral is used as an aggregation function, presenting different parameters, and allowing to take into account the interactions between the objectives. We develop a new property that characterizes the Choquet optimal solutions. From this property, a general method to easily generate these solutions in the case of two objectives is defined. We apply the method to two classical biobjective optimization combinatorial optimization problems: the biobjective knapsack problem and the biobjective minimum spanning tree problem. We show that Choquet optimal solutions that are not weighted sum optimal solutions represent only a small proportion of the Choquet optimal solutions and are located in a specific area of the objective space, but are much harder to compute than weighted sum optimal solutions.     

Scalable Pareto set generation for multiobjective co-design problems in water distribution networks: a continuous relaxation approach

In this paper, we study the multiobjective co-design problem of optimal valve placement and operation in water distribution networks, addressing the minimization of average pressure and pressure variability indices. The presented formulation considers nodal pressures, pipe flows and valve locations as decision variables, where binary variables are used to model the placement of control valves. The resulting optimization problem is a multiobjective mixed integer nonlinear optimization problem. As conflicting objectives, average zone pressure and pressure variability can not be simultaneously optimized. Therefore, we present the concept of Pareto optima sets to investigate the trade-offs between the two conflicting objectives and evaluate the best compromise. We focus on the approximation of the Pareto front, the image of the Pareto optima set through the objective functions, using the weighted sum, normal boundary intersection and normalized normal constraint scalarization techniques. Each of the three methods relies on the solution of a series of single-objective optimization problems, which are mixed integer nonlinear programs (MINLPs) in our case. For the solution of each single-objective optimization problem, we implement a relaxation method that solves a sequence of nonlinear programs (NLPs) whose stationary points converge to a stationary point of the original MINLP. The relaxed NLPs have a sparse structure that come from the sparse water network graph constraints. In solving the large number of relaxed NLPs, sparsity is exploited by tailored techniques to improve the performance of the algorithms further and render the approaches scalable for large scale networks. The features of the proposed scalarization approaches are evaluated using a published benchmarking network model.     

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.     

Solving a type of biobjective bilevel programming problem using NSGA-II

This paper considers a type of biobjective bilevel programming problem, which is derived from a single objective bilevel programming problem via lifting the objective function at the lower level up to the upper level. The efficient solutions to such a model can be considered as candidates for the after optimization bargaining between the decision-makers at both levels who retain the original bilevel decision-making structure. We use a popular multiobjective evolutionary algorithm, NSGA-II, to solve this type of problem. The algorithm is tested on some small-dimensional benchmark problems from the literature. Computational results show that the NSGA-II algorithm is capable of solving the problems efficiently and effectively. Hence, it provides a promising visualization tool to help the decision-makers find the best trade-off in bargaining.     

Representation of the non-dominated set in biobjective discrete optimization

This paper introduces several algorithms for finding a representative subset of the non-dominated point set of a biobjective discrete optimization problem with respect to uniformity, coverage and the ϵ-indicator. We consider the representation problem itself as multiobjective, trying to find a good compromise between these quality measures. These representation problems are formulated as particular facility location problems with a special location structure, which allows for polynomial-time algorithms in the biobjective case based on the principles of dynamic programming and threshold approaches. In addition, we show that several multiobjective variants of these representation problems are also solvable in polynomial time. Computational results obtained by these approaches on a wide range of randomly generated point sets are presented and discussed.     

Cycle Flow Formulation of Optimal Network Flow Problems and Respective Distributed Solutions

In this paper, we use the cycle basis from graph theory to reduce the size of the decision variable space of optimal network flow problems by eliminating the aggregated flow conservation constraint. We use a minimum cost flow problem and an optimal power flow problem with generation and storage at the nodes to demonstrate our decision variable reduction method. The main advantage of the proposed technique is that it retains the natural sparse/decomposable structure of network flow problems. As such, the reformulated problems are still amenable to distributed solutions. We demonstrate this by proposing a distributed alternating direction method of multipliers (ADMM) solution for a minimum cost flow problem. We also show that the communication cost of the distributed ADMM algorithm for our proposed cycle-based formulation of the minimum cost flow problem is lower than that of a distributed ADMM algorithm for the original arc-based formulation.      

一种求解鲁棒优化问题的多目标进化方法

鲁棒优化问题（Robust Optimization Problem,ROP）是进化算法（Evolutionary Algorithms,EAs）研究的重要方面之一,对于许多实际工程优化问题,通常需要得到鲁棒最优解。利用多目标优化中的Pareto思想优化ROP的鲁棒性和最优性,将ROP转化为一个两目标的优化问题,一个目标为解的鲁棒性,一个目标为解的最优性。针对ROP与多目标优化的特点,利用动态加权思想,设计一种求解ROP的多目标进化算法。通过测试函数的实验仿真,验证了该方法的有效性。     

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.     

Methods of multiextremal optimization under constraints for separably quasimonotone functions

The properties of separably quasimonotone functions such that calculation of the minimum and maximum values for the variables belonging to the n-dimensional partially integer parallelepiped is reduced to solving simple problems are studied. Operators and iterative processes for identifying domains without admissible and optimal solutions for nonconvex constraints described by systems of inequalities, and systems of efficient boundary estimates of optimal solutions are proposed. This made it possible to reduce the search domain and the number of options involved and to improve the stopping rule of solving processes. For this class of functions, modifications and strategies for branch-and-bound and global random search methods that were not addressed in publications are developed.     

An efficient solution to biobjective generalized assignment problem

The generalized assignment problem (GAP) has found applications in many real world problems. In this paper, we examine the GAP from a multiobjective point of view to accommodate some real world situations where more than one objective is involved. An efficient LP-based heuristic is proposed to solve the biobjective generalized assignment problem (BiGAP). Extensive computational experiments are carried out to evaluate the performance of the proposed method. The results show that the proposed approach is able to generate good approximations to the nondominated frontier of the BiGAP efficiently, especially when the ratio of the number of items to the number of knapsacks is large.     

Theoretical and practical fundamentals for multi-objective optimisation in resource-constrained project scheduling problems

Project scheduling is an inherently multi-objective problem, since managers want to finish projects as soon as possible with the minimum cost and the maximum quality. However, there are only a few papers dealing with multiobjective resource-constrained project scheduling problems (MORCPSPs). Moreover, there is no theoretical study in the literature that establishes the fundamentals for correct algorithmic developments. In this paper we try to close the gap by proving several results for MORCPSPs. With these results as a basis, both exact and heuristic procedures capable of obtaining a set of efficient solutions for several important MORCPSPs can be created.