A class of multiobjective linear programming model with fuzzy random coefficients

The aim of this paper is to deal with a multiobjective linear programming problem with fuzzy random coefficients. Some crisp equivalent models are presented and a traditional algorithm based on an interactive fuzzy satisfying method is proposed to obtain the decision maker’s satisfying solution. In addition, the technique of fuzzy random simulation is adopted to handle general fuzzy random objective functions and fuzzy random constraints which are usually hard to be converted into their crisp equivalents. Furthermore, combined with the techniques of fuzzy random simulation, a genetic algorithm using the compromise approach is designed for solving a fuzzy random multiobjective programming problem. Finally, illustrative examples are given in order to show the application of the proposed models and algorithms.     

Using Efficient Anchoring Points for Generating Search Directions in Interior Multiobjective Linear Programming

This paper modifies the affine-scaling primal algorithm to multiobjective linear programming (MOLP) problems. The modification is based on generating search directions in the form of projected gradients augmented by search directions pointing toward what we refer to as anchoring points. These anchoring points are located on the boundary of the feasible region and, together with the current, interior, iterate, define a cone in which we make the next step towards a solution of the MOLP problem. These anchoring points can be generated in more than one way. In this paper we present an approach that generates efficient anchoring points where the choice of termination solution available to the decision maker at each iteration consists of a set of efficient solutions. This set of efficient solutions is being updated during the iterative process so that only the most preferred solutions are retained for future considerations. Current MOLP algorithms are simplex-based and make their progress toward the optimal solution by following an exterior trajectory along the vertices of the constraints polytope. Since the proposed algorithm makes its progress through the interior of the constraints polytope, there is no need for vertex information and, therefore, the search for an acceptable solution may prove less sensitive to problem size. We refer to the resulting class of MOLP algorithms that are based on the affine-scaling primal algorithm as affine-scaling interior multiobjective linear programming (ASIMOLP) algorithms.     

On the transformation of lexicographic nonlinear multiobjective programs to single objective programs

This paper deals with multiobjective optimization programs in which the objective functions are ordered by their degree of priority. A number of approaches have been proposed (and several implemented) for the solution of lexicographic (preemptive priority) multiobjective optimization programs. These approaches may be divided into two classes. The first encompasses the development of algorithms specifically designed to deal directly with the initial model. Considered only for linear multiobjective programs and multiobjective programs with a finite discrete feasible region, the second one attempts to transform, efficiently, the lexicographic multiobjective model into an equvivalent model, i.e. a single objective programming problem. In this paper, we deal with the second approach for lexicographic nonlinear multiobjective programs.     

Stochastic MOLP with Incomplete Information: An Interactive Approach with Recourse

Numerous multiobjective linear programming (MOLP) methods have been proposed in the last two decades, but almost all for contexts where the parameters of problems are deterministic. However, in many real situations, parameters of a stochastic nature arise. In this paper, we suppose that the decision-maker is confronted with a situation of partial uncertainty where he possesses incomplete information about the stochastic parameters of the problem, this information allowing him to specify only the limits of variation of these parameters and eventually their central values. For such situations, we propose a multiobjective stochastic linear programming methodology; it implies the transformation of the stochastic objective functions and constraints in order to obtain an equivalent deterministic MOLP problem and the solving of this last problem by an interactive approach derived from the STEM method. Our methodology is illustrated by a didactical example.     

Characterization of vector strict global minimizers of order 2 in differentiable vector optimization problems under a new approximation method

In this paper, a new approximation method is introduced to characterize a so-called vector strict global minimizer of order 2 for a class of nonlinear differentiable multiobjective programming problems with (F,ρ)-convex functions of order 2. In this method, an equivalent vector optimization problem is constructed by a modification of both the objectives and the constraint functions in the original multiobjective programming problem at the given feasible point. In order to prove the equivalence between the original multiobjective programming problem and its associated F-approximated vector optimization problem, the suitable (F,ρ)-convexity of order 2 assumption is imposed on the functions constituting the considered vector optimization problem.     

An interactive fuzzy satisficing method for structured multiobjective linear fractional programs with fuzzy numbers

In this paper, by considering the experts' vague or fuzzy understanding of the nature of the parameters in the problem formulation process, multiobjective linear fractional programming problems with block angular structure involving fuzzy numbers are formulated. Using the a-level sets of fuzzy numbers, the corresponding nonfuzzy a-multiobjective linear fractional programming problem is introduced. The fuzzy goals of the decision maker for the objective functions are quantified by eliciting the corresponding membership functions including nonlinear ones. Through the introduction of extended Pareto optimality concepts, if the decision maker specifies the degree a and the reference membership values, the corresponding extended Pareto optimal solution can be obtained by solving the minimax problems for which the Dantzig-Wolfe decomposition method and Ritter's partitioning procedure are applicable. Then a linear programming-based interactive fuzzy satisficing method with decomposition procedures for deriving a satisficing solution for the decision maker efficiently from an extended Pareto optimal solution set is presented. An illustrative numerical example is provided to demonstrate the feasibility of the proposed method.     

Fuzzy goal programming for multiobjective transportation problems

Several fuzzy approaches can be considered for solving multiobjective transportation problem. This paper presents a fuzzy goal programming approach to determine an optimal compromise solution for the multiobjective transportation problem. We assume that each objective function has a fuzzy goal. Also we assign a special type of nonlinear (hyperbolic) membership function to each objective function to describe each fuzzy goal. The approach focuses on minimizing the negative deviation variables from 1 to obtain a compromise solution of the multiobjective transportation problem. We show that the proposed method and the fuzzy programming method are equivalent. In addition, the proposed approach can be applied to solve other multiobjective mathematical programming problems. A numerical example is given to illustrate the efficiency of the proposed approach.     

A class of multiobjective linear programming models with random rough coefficients

In the present paper, we concentrate on dealing with a class of multiobjective programming problems with random rough coefficients. We first discuss how to turn a constrained model with random rough variables into crisp equivalent models. Then an interactive algorithm which is similar to the interactive fuzzy satisfying method is introduced to obtain the decision maker’s satisfying solution. In addition, the technique of random rough simulation is applied to deal with general random rough objective functions and random rough constraints which are usually hard to convert into their crisp equivalents. Furthermore, combined with the techniques of random rough simulation, a genetic algorithm using the compromise approach is designed for solving a random rough multiobjective programming problem. Finally, illustrative examples are given in order to show the application of the proposed models and algorithms.     

An Interval-Parameter Fuzzy Approach for Multiobjective Linear Programming Under Uncertainty

An interval-parameter fuzzy linear programming method (IFMOLP) is proposed in this study for multiple objective decision-making under uncertainty. As a hybrid of interval-parameter and fuzzy methodologies, the IFMOLP incorporates interval-parameter linear programming and fuzzy multiobjective programming approaches to form an integrated optimization system. The method inherits advantages of interval-parameter programming, and allows uncertainties and decision-makers’ aspirations to be effectively communicated into its programming processes and resulting solutions. Membership functions for both objectives and constraints are formulated to reflect uncertainties in different system components and their interrelationships. An interactive solution procedure has been developed based on solution approaches of the interval-parameter and fuzzy programming techniques, plus necessary measures for handling the multiobjective feature. A didactic example is provided in the paper to illustrate the detailed solution process. Possibilities of further improvements by seeking Pareto optimum and incorporating flexible preference within constraints are also discussed.     

Duality Theory in Fuzzy Linear Programming Problems with Fuzzy Coefficients

The concept of fuzzy scalar (inner) product that will be used in the fuzzy objective and inequality constraints of the fuzzy primal and dual linear programming problems with fuzzy coefficients is proposed in this paper. We also introduce a solution concept that is essentially similar to the notion of Pareto optimal solution in the multiobjective programming problems by imposing a partial ordering on the set of all fuzzy numbers. We then prove the weak and strong duality theorems for fuzzy linear programming problems with fuzzy coefficients.     

On p-norm linear discrimination

We consider a p-norm linear discrimination model that generalizes the model of Bennett and Mangasarian (1992) and reduces to a linear programming problem with p-order cone constraints. The proposed approach for handling linear programming problems with p-order cone constraints is based on reformulation of p-order cone optimization problems as second order cone programming (SOCP) problems when p is rational. Since such reformulations typically lead to SOCP problems with large numbers of second order cones, an “economical” representation that minimizes the number of second order cones is proposed. A case study illustrating the developed model on several popular data sets is conducted.     

An interactive fuzzy satisficing method for multiobjective nonconvex programming problems through floating point genetic algorithms

In this paper, we focus on multiobjective nonconvex nonlinear programming problems and present an interactive fuzzy satisficing method through floating point genetic algorithms. After determining the fuzzy goals of the decision maker, if the decision maker specifies the reference membership values, the corresponding Pareto optimal solution can be obtained by solving the augmented minimax problems for which the floating point genetic algorithm, called GENOCOP III, is applicable. In order to overcome the drawbacks of GENOCOP III, we propose the revised GENOCOP III by introducing a method for generating an initial feasible point and a bisection method for generating a new feasible point efficiently. Then an interactive fuzzy satisficing method for deriving a satisficing solution for the decision maker efficiently from a Pareto optimal solution set is presented together with an illustrative numerical example.     

带非凸二次约束的二次比式和问题的全局优化算法(英文)

对带非凸二次约束的二次比式和问题(P)给出分枝定界算法,首先将问题(P)转化为其等价问题(Q),然后利用线性化技术,建立了(Q)松弛线性规划问题(RLP),通过对(RLP)可行域的细分及求解一系列线性规划问题,不断更新(Q)的上下界,从理论上证明了算法的收敛性,数值实验表明了算法的可行性和有效性.     

Reducibility of minimax to minisum 0–1 programming problems

We consider 0–1 programming problems with a minimax objective function and any set of constraints. Upon appropriate transformations of its cost coefficients, such a minimax problem can be reduced to a linear minisum problem with the same set of feasible solutions such that an optimal solution to the latter will also solve the original minimax problem.Although this reducibility applies for any 0–1 programming problem, it is of particular interest for certain locational decision models. Among the obvious implications are that an algorithm for solving a p-median (minisum) problem in a network will also solve a corresponding p-center (minimax) problem.It should be emphasized that the results presented will in general only hold for 0–1 problems due to intrinsic properties of the minimax criterion.     

Branch-and-Bound Outer Approximation Algorithm for Sum-of-Ratios Fractional Programs

In this article, a branch and-bound outer approximation algorithm is presented for globally solving a sum-of-ratios fractional programming problem. To solve this problem, the algorithm instead solves an equivalent problem that involves minimizing an indefinite quadratic function over a nonempty, compact convex set. This problem is globally solved by a branch-and-bound outer approximation approach that can create several closed-form linear inequality cuts per iteration. In contrast to pure outer approximation techniques, the algorithm does not require computing the new vertices that are created as these cuts are added. Computationally, the main work of the algorithm involves solving a sequence of convex programming problems whose feasible regions are identical to one another except for certain linear constraints. As a result, to solve these problems, an optimal solution to one problem can potentially be used to good effect as a starting solution for the next problem.     

A mathematical programming approach to the computation of the omega invariant of a numerical semigroup

In this paper we present a mathematical programming formulation for the ω-invariant of a numerical semigroup for each of its minimal generators which is an useful index in commutative algebra (in particular in factorization theory) to analyze the primality of the elements in the semigroup. The model consists of solving a problem of optimizing a linear function over the efficient set of a multiobjective linear integer program. We offer a methodology to solve this problem and we provide some computational experiments to show the efficiency of the proposed algorithm.     

Limit vector variational inequality problems via scalarization

This paper presents a global optimization approach for solving signomial geometric programming (SGP) problems. We employ an accelerated extended cutting plane (ECP) approach integrated with piecewise linear (PWL) approximations to solve the global optimization of SGP problems. In this approach, we separate the feasible regions determined by the constraints into convex and nonconvex ones in the logarithmic domain. In the nonconvex feasible regions, the corresponding constraint functions are converted into mixed integer linear constraints using PWL approximations, while the other constraints with convex feasible regions are handled by the ECP method. We also use pre-processed initial cuts and batched cuts to accelerate the proposed algorithm. Numerical results show that the proposed approach can solve the global optimization of SGP problems efficiently and effectively.     

An Inner Approximation Method for Optimization over the Weakly Efficient Set

In this paper, we consider an optimization problem which aims to minimize a convex function over the weakly efficient set of a multiobjective programming problem. To solve such a problem, we propose an inner approximation algorithm, in which two kinds of convex subproblems are solved successively. These convex subproblems are fairly easy to solve and therefore the proposed algorithm is practically useful. The algorithm always terminates after finitely many iterations by compromising the weak efficiency to a multiobjective programming problem. Moreover, for a subproblem which is solved at each iteration of the algorithm, we suggest a procedure for eliminating redundant constraints.     

A column generation approach to the discrete barycenter problem

The discrete Wasserstein barycenter problem is a minimum-cost mass transport problem for a set of discrete probability measures. Although an exact barycenter is computable through linear programming, the underlying linear program can be extremely large. For worst-case input, a best known linear programming formulation is exponential in the number of variables, but has a low number of constraints, making it an interesting candidate for column generation.In this paper, we devise and study two column generation strategies: a natural one based on a simplified computation of reduced costs, and one through a Dantzig–Wolfe decomposition. For the latter, we produce efficiently solvable subproblems, namely, a pricing problem in the form of a classical transportation problem. The two strategies begin with an efficient computation of an initial feasible solution. While the structure of the constraints leads to the computation of the reduced costs of all remaining variables for setup, both approaches may outperform a computation using the full program in speed, and dramatically so in memory requirement. In our computational experiments, we exhibit that, depending on the input, either strategy can become a best choice.