On Resource Allocation Problems with Interval-Scale Coefficients

In this paper we discuss the classical problem of the allocation of a single finite resource among many competing activities for the specific case where the coefficients of the objective function form an interval scale. In this case there is no longer a single optimal solution, but rather a set of efficient solutions. We recommend a technique equivalent to parametric objective function analysis to generate the set of efficient solutions to the problem.     

Maximal and supremal tolerances in multiobjective linear programming

Let a multiobjective linear programming problem and any efficient solution be given. Tolerance analysis aims to compute interval tolerances for (possibly all) objective function coefficients such that the efficient solution remains efficient for any perturbation of the coefficients within the computed intervals. The known methods either yield tolerances that are not the maximal possible ones, or they consider perturbations of weights of the weighted sum scalarization only. We focus directly on perturbations of the objective function coefficients, which makes the approach independent on a scalarization technique used. In this paper, we propose a method for calculating the supremal tolerance (the maximal one need not exist). The main disadvantage of the method is the exponential running time in the worst case. Nevertheless, we show that the problem of determining the maximal/supremal tolerance is NP-hard, so an efficient (polynomial time) procedure is not likely to exist. We illustrate our approach on examples and present an application in transportation problems. Since the maximal tolerance may be small, we extend the notion to individual lower and upper tolerances for each objective function coefficient. An algorithm for computing maximal individual tolerances is proposed.     

An interactive method of tackling uncertainty in interval multiple objective linear programming

Mathematical programming models for decision support must explicitly take account of the treatment of the uncertainty associated with the model coefficients along with multiple and conflicting objective functions. Interval programming just assumes that information about the variation range of some (or all) of the coefficients is available. In this paper, we propose an interactive approach for multiple objective linear programming problems with interval coefficients that deals with the uncertainty in all the coefficients of the model. The presented procedures provide a global view of the solutions in the best and worst case coefficient scenarios and allow performing the search for new solutions according to the achievement rates of the objective functions regarding both the upper and lower bounds. The main goal is to find solutions associated with the interval objective function values that are closer to their corresponding interval ideal solutions. It is also possible to find solutions with non-dominance relations regarding the achievement rates of the upper and lower bounds of the objective functions considering interval coefficients in the whole model.     

Characterizing Nonemptiness and Compactness of the Solution Set of a Convex Vector Optimization Problem with Cone Constraints and Applications

In this paper, we characterize the nonemptiness and compactness of the set of weakly efficient solutions of a convex vector optimization problem with cone constraints in terms of the level-boundedness of the component functions of the objective on the perturbed sets of the original constraint set. This characterization is then applied to carry out the asymptotic analysis of a class of penalization methods. More specifically, under the assumption of nonemptiness and compactness of the weakly efficient solution set, we prove the existence of a path of weakly efficient solutions to the penalty problem and its convergence to a weakly efficient solution of the original problem. Furthermore, for any efficient point of the original problem, there exists a path of efficient solutions to the penalty problem whose function values (with respect to the objective function of the original problem) converge to this efficient point.     

A cutting plane method for bilevel linear programming with interval coefficients

This article considers the bilevel linear programming problem with interval coefficients in both objective functions. We propose a cutting plane method to solve such a problem. In order to obtain the best and worst optimal solutions, two types of cutting plane methods are developed based on the fact that the best and worst optimal solutions of this kind of problem occur at extreme points of its constraint region. The main idea of the proposed methods is to solve a sequence of linear programming problems with cutting planes that are successively introduced until the best and worst optimal solutions are found. Finally, we extend the two algorithms proposed to compute the best and worst optimal solutions of the general bilevel linear programming problem with interval coefficients in the objective functions as well as in the constraints.     

Linear bilevel programming with interval coefficients

In this paper, we address linear bilevel programs when the coefficients of both objective functions are interval numbers. The focus is on the optimal value range problem which consists of computing the best and worst optimal objective function values and determining the settings of the interval coefficients which provide these values. We prove by examples that, in general, there is no precise way of systematizing the specific values of the interval coefficients that can be used to compute the best and worst possible optimal solutions. Taking into account the properties of linear bilevel problems, we prove that these two optimal solutions occur at extreme points of the polyhedron defined by the common constraints. Moreover, we develop two algorithms based on ranking extreme points that allow us to compute them as well as determining settings of the interval coefficients which provide the optimal value range.     

On fuzzy random multiobjective quadratic programming

In this paper, a multiobjective quadratic programming problem having fuzzy random coefficients matrix in the objective and constraints and the decision vector are fuzzy pseudorandom variables is considered. First, we show that the efficient solutions of fuzzy quadratic multiobjective programming problems are resolved into series-optimal-solutions of relative scalar fuzzy quadratic programming. Some theorems are proved to find an optimal solution of the relative scalar quadratic multiobjective programming with fuzzy coefficients, having decision vectors as fuzzy variables. At the end, numerical examples are illustrated in the support of the obtained results.     

The use of possibility theory in the definition of fuzzy Pareto-optimality

Pareto-optimality conditions are crucial when dealing with classic multi-objective optimization problems. Extensions of these conditions to the fuzzy domain have been discussed and addressed in recent literature. This work presents a novel approach based on the definition of a fuzzily ordered set with a view to generating the necessary conditions for the Pareto-optimality of candidate solutions in the fuzzy domain. Making use of the conditions generated, one can characterize fuzzy efficient solutions by means of carefully chosen mono-objective problems and Karush-Kuhn-Tucker conditions to fuzzy non-dominated solutions. The uncertainties are inserted into the formulation of the studied fuzzy multi-objective optimization problem by means of fuzzy coefficients in the objective function. Some numerical examples are analytically solved to illustrate the efficiency of the proposed approach.     

Minimum values over the efficient set in multiple objective decision making

In multiple objective decision making (MODM), it is often helpful to provide the decision maker (DM) with bounds on the values of each of the objectives. Ideal solutions are relatively easy to calculate and provide upper bounds on the value of each objective over the set of efficient solutions. Ideal solutions also provide lower bounds on the value of each objective over the ideal set. However, the lower bounds over the set of efficient solutions can be strictly less than the ideal lower bounds, but are, in general, more difficult to determine. Thus MODM procedures which utilize the ideal lower bound may overlook elements of the set of efficient solutions. This study explores the differences between the subset of the set of efficient solutions to a MODM problem bounded by its ideal solutions and the complete efficient set.     

A new strategy for the undirected two-commodity maximum flow problem

We address the two-commodity maximum flow problem on undirected networks. As a result of a change of variables, we introduce a new formulation that solves the problem through classical maximum flow techniques with only one-commodity. Therefore, a general strategy, based on this change of variables, is defined to deal with other undirected multi-commodity problems. Finally, we extend the single objective problem to a bicriteria environment. We show that the set of efficient solutions of the biobjective undirected two-commodity maximum flow problem is the set of alternative optimum solutions of the undirected two-commodity maximum flow problem. In addition, we prove that the set of efficient extreme points in the objective space has, at most, cardinality two.     

Weighting factor results in vector optimization

This paper deals with the study, in a convex vector optimization problem, of the set of efficient solutions and the set of properly efficient solutions, the latter being obtained by a weighting factor technique. Relationships between these two sets are discussed; they are shown to be nonempty when the objective functions have no common direction of recession and to be closed and equal when, moreover, the objective functions are locally polyhedral. An example is provided where the set of efficient solutions is not included in the closure of the nonempty set of properly efficient solutions.The author wishes to thank the unknown referee for the helpful comments that improved the quality of this paper.     

Strictly feasible solutions and strict complementarity in multiple objective linear optimization

Recently, Luc defined a dual program for a multiple objective linear program. The dual problem is also a multiple objective linear problem and the weak duality and strong duality theorems for these primal and dual problems have been established. Here, we use these results to prove some relationships between multiple objective linear primal and dual problems. We extend the available results on single objective linear primal and dual problems to multiple objective linear primal and dual problems. Complementary slackness conditions for efficient solutions, and conditions for the existence of weakly efficient solution sets and existence of strictly primal and dual feasible points are established. We show that primal-dual (weakly) efficient solutions satisfying strictly complementary conditions exist. Furthermore, we consider Isermann’s and Kolumban’s dual problems and establish conditions for the existence of strictly primal and dual feasible points. We show the existence of primal-dual feasible points satisfying strictly complementary conditions for Isermann’s dual problem. Also, we give an alternative proof to establish necessary conditions for weakly efficient solutions of multiple objective programs, assuming the Kuhn–Tucker (KT) constraint qualification. We also provide a new condition to ensure the KT constraint qualification.     

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.      

Robust topology optimization for multi-material structures under interval uncertainty

In this paper, we propose an efficient method to design robust multi-material structures under interval loading uncertainty. The objective of this study is to minimize the structural compliance of linear elastic structures. First, the loading uncertainty can be decomposed into two unit forces in the horizontal and vertical directions based on the orthogonal decomposition, which separates the uncertainty into the calculation coefficients of structural compliance that are not related to the finite element analysis. In this manner, the time-consuming procedure, namely, the nested double-loop optimization, can be avoided. Second, the uncertainty problem can be transformed into an augmented deterministic problem by means of uniform sampling, which exploits the coefficients related to interval variables. Finally, an efficient sensitivity analysis method is explicitly developed. Thus, the robust topology optimization (RTO) problem considering interval uncertainty can be solved by combining orthogonal decomposition with uniform sampling (ODUS). In order to eliminate the influence of numerical units when comparing the optimal results to deterministic and RTO solutions, the relative uncertainty related to interval objective function is employed to characterize the structural robustness. Several multi-material structure optimization cases are provided to demonstrate the feasibility and efficiency of the proposed method, where the magnitude uncertainty, directional uncertainty, and combined uncertainty are investigated.     

Inverse multi-objective combinatorial optimization

Inverse multi-objective combinatorial optimization consists of finding a minimal adjustment of the objective functions coefficients such that a given set of feasible solutions becomes efficient. An algorithm is proposed for rendering a given feasible solution into an efficient one. This is a simplified version of the inverse problem when the cardinality of the set is equal to one. The adjustment is measured by the Chebyshev distance. It is shown how to build an optimal adjustment in linear time based on this distance, and why it is right to perform a binary search for determining the optimal distance. These results led us to develop an approach based on the resolution of mixed-integer linear programs. A second approach based on a branch-and-bound is proposed to handle any distance function that can be linearized. Finally, the initial inverse problem is solved by a cutting plane algorithm.     

Vector maximization with two objective functions

This note gives a characterization of an efficient solution for the vector maximization problem with two objective functions. This characterization yields a parametric procedure for generating the set of all efficient solutions for this problem. The parametric procedure can also be used to solve certain bicriterion mathematical programs.     

Levitin–Polyak well-posedness for constrained quasiconvex vector optimization problems

In this paper, a notion of Levitin–Polyak (LP in short) well-posedness is introduced for a vector optimization problem in terms of minimizing sequences and efficient solutions. Sufficient conditions for the LP well-posedness are studied under the assumptions of compactness of the feasible set, closedness of the set of minimal solutions and continuity of the objective function. The continuity assumption is then weakened to cone lower semicontinuity for vector-valued functions. A notion of LP minimizing sequence of sets is studied to establish another set of sufficient conditions for the LP well-posedness of the vector problem. For a quasiconvex vector optimization problem, sufficient conditions are obtained by weakening the compactness of the feasible set to a certain level-boundedness condition. This in turn leads to the equivalence of LP well-posedness and compactness of the set of efficient solutions. Some characterizations of LP well-posedness are given in terms of the upper Hausdorff convergence of the sequence of sets of approximate efficient solutions and the upper semicontinuity of an approximate efficient map by assuming the compactness of the set of efficient solutions, even when the objective function is not necessarily quasiconvex. Finally, a characterization of LP well-posedness in terms of the closedness of the approximate efficient map is provided by assuming the compactness of the feasible set.     

Optimal value range in interval linear programming

We deal with the linear programming problem in which input data can vary in some given real compact intervals. The aim is to compute the exact range of the optimal value function. We present a general approach to the situation the feasible set is described by an arbitrary linear interval system. Moreover, certain dependencies between the constraint matrix coefficients can be involved. As long as we are able to characterize the primal and dual solution set (the set of all possible primal and dual feasible solutions, respectively), the bounds of the objective function result from two nonlinear programming problems. We demonstrate our approach on various cases of the interval linear programming problem (with and without dependencies).     

锥弱有效解的本质集和本质连通区

对于多目标规划问题,通过引入锥弱有效解集的概念,证明了任何连续有界泛函至少存在一个极小本质集和一个本质连通区.     

Conjugate maps and duality in multiobjective optimization

This paper considers duality in convex vector optimization. A vector optimization problem requires one to find all the efficient points of the attainable value set for given multiple objective functions. Embedding the primal problem into a family of perturbed problems enables one to define a dual problem in terms of the conjugate map of the perturbed objective function. Every solution of the stable primal problem is associated with a certain solution of the dual problem, which is characterized as a subgradient of the perturbed efficient value map. This pair of solutions also provides a saddle point of the Lagrangian map.