Branch-and-Bound Variant of an Outcome-Based Algorithm for Optimizing over the Efficient Set of a Bicriteria Linear Programming Problem

The paper presents a finite branch-and-bound variant of an outcome-based algorithm proposed by Benson and Lee for minimizing a lower-semicontinuous function over the efficient set of a bicriteria linear programming problem. Similarly to the Benson-Lee algorithm, we work primarily in the outcome space. Dissimilarly, instead of constructing a sequence of consecutive efficient edges in the outcome space, we use the idea of generating a refining sequence of partitions covering the at most two-dimensional efficient set in the outcome space. Computational experience is also presented.     

An Outer Approximation Algorithm for Generating All Efficient Extreme Points in the Outcome Set of a Multiple Objective Linear Programming Problem

Various difficulties have been encountered in using decision set-based vector maximization methods to solve a multiple objective linear programming problem (MOLP). Motivated by these difficulties, some researchers in recent years have suggested that outcome set-based approaches should instead be developed and used to solve problem (MOLP). In this article, we present a finite algorithm, called the Outer Approximation Algorithm, for generating the set of all efficient extreme points in the outcome set of problem (MOLP). To our knowledge, the Outer Approximation Algorithm is the first algorithm capable of generating this set. As a by-product, the algorithm also generates the weakly efficient outcome set of problem (MOLP). Because it works in the outcome set rather than in the decision set of problem (MOLP), the Outer Approximation Algorithm has several advantages over decision set-based algorithms. It is also relatively easy to implement. Preliminary computational results for a set of randomly-generated problems are reported. These results tangibly demonstrate the usefulness of using the outcome set approach of the Outer Approximation Algorithm instead of a decision set-based approach. This revised version was published online in July 2006 with corrections to the Cover Date.     

Conical Algorithm in Global Optimization for Optimizing over Efficient Sets

The problem of optimizing some contiuous function over the efficient set of a multiple objective programming problem can be formulated as a nonconvex global optimization problem with special structure. Based on the conical branch and bound algorithm in global optimization, we establish an algorithm for optimizing over efficient sets and discuss about the implementation of this algorithm for some interesting special cases including the case of biobjective programming problems.     

求多目标线性规划妥协解的旋转迭代算法

本应用单纯形旋转迭代算法，求解多目标线性规划的妥协解，得到满意效果。     

Global Optimization in Practice: An Application to Interactive Multiple Objective Linear Programming

A multiple objective linear programming problem (P) involves the simultaneous maximization of two or more conflicting linear objective functions over a nonempty polyhedron X. Many of the most popular methods for solving this type of problem, including many well-known interactive methods, involve searching the efficient set X _E of the problem. Generally, however, X _E is a complicated, nonconvex set. As a result, concepts and methods from global optimization may be useful in searching X _E. In this paper, we will explain in theory, and show via an actual application to citrus rootstock selection in Florida, how the potential usefulness of the well-known interactive method STEM for solving problem (P) in this way, can depend crucially upon how accurately certain global optimization problems involving minimizations over X _E are solved. In particular, we will show both in theory and in practice that the choice of whether to use the popular but unreliable payoff table approach or to use one of the lesser known, more accurate global optimization methods to solve these problems can determine whether STEM succeeds or fails as a decision aid. Several lessons and conclusions of transferable value derived from this research are also given.     

A Parallel Algorithm for Multiple Objective Linear Programs

This paper presents an ADBASE-based parallel algorithm forsolving multiple objective linear programs (MOLPs). Job balance,speedup and scalability are of primary interest in evaluatingefficiency of the new algorithm. The scalability of a parallelalgorithm is a measure of its capacity to increase performance withrespect to the number of processors used. Implementation results onIntel iPSC/2 and Paragon multiprocessors show that the algorithmsignificantly speeds up the process of solving MOLPs, which isunderstood as generating all or some efficient extreme points andunbounded efficient edges. The algorithm is shown to be scalable andgives better results for large problems. Motivation andjustification for solving large MOLPs are also included.     

On Optimization over the Efficient Set in Linear Multicriteria Programming

The efficient set of a linear multicriteria programming problem can be represented by a reverse convex constraint of the form g(z)≤0, where g is a concave function. Consequently, the problem of optimizing some real function over the efficient set belongs to an important problem class of global optimization called reverse convex programming. Since the concave function used in the literature is only defined on some set containing the feasible set of the underlying multicriteria programming problem, most global optimization techniques for handling this kind of reverse convex constraint cannot be applied. The main purpose of our article is to present a method for overcoming this disadvantage. We construct a concave function which is finitely defined on the whole space and can be considered as an extension of the existing function. Different forms of the linear multicriteria programming problem are discussed, including the minimum maximal flow problem as an example. The research was partly done while the third author was visiting the Department of Mathematics, University of Trier with the support by the Alexander von Humboldt Foundation. He thanks the university as well as the foundation.     

求解多目标规划的一种思路

本文提出了一种求解多目标规划问题的思路,其综合运用下包络点、帕雷托 拟合率等知识,去搜寻多目标规划问题的一组有效点且可逼近全部的有效点.     

Further Analysis of an Outcome Set-Based Algorithm for Multiple-Objective Linear Programming

Various difficulties have been encountered in using decision set-based vector maximization methods to solve a multiple-objective linear programming problem (MOLP). Motivated by these difficulties, Benson recently developed a finite, outer-approximation algorithm for generating the set of all efficient extreme points in the outcome set, rather than in the decision set, of problem (MOLP). In this article, we show that the Benson algorithm also generates the set of all weakly efficient points in the outcome set of problem (MOLP). As a result, the usefulness of the algorithm as a decision aid in multiple objective linear programming is further enhanced.     

Solving Bilevel Linear Programs Using Multiple Objective Linear Programming

We present an algorithm for solving bilevel linear programs that uses simplex pivots on an expanded tableau. The algorithm uses the relationship between multiple objective linear programs and bilevel linear programs along with results for minimizing a linear objective over the efficient set for a multiple objective problem. Results in multiple objective programming needed are presented. We report computational experience demonstrating that this approach is more effective than a standard branch-and-bound algorithm when the number of leader variables is small.     

Simplicially-Constrained DC Optimization over Efficient and Weakly Efficient Sets

We formulate optimization problems over efficient and weakly efficient sets as DC problems over a simplex in the criteria space. This formulation allows developing a decomposition algorithm using an adaptive simplex subdivision and a convex envelope function for solving both problems. Randomly generated problems up to the size of 150 decision variables and 7 criteria are solved.     

Optimizing a linear function over an efficient set

The problem (P) of optimizing a linear functiond ^T x over the efficient set for a multiple-objective linear program (M) is difficult because the efficient set is typically nonconvex. Given the objective function directiond and the set of domination directionsD, ifd ^T 0 for all nonzero D, then a technique for finding an optimal solution of (P) is presented in Section 2. Otherwise, given a current efficient point , if there is no adjacent efficient edge yielding an increase ind ^T x, then a cutting plane is used to obtain a multiple-objective linear program ( ) with a reduced feasible set and an efficient set . To find a better efficient point, we solve the problem (I_i) of maximizingc _i ^T x over the reduced feasible set in ( ) sequentially fori. If there is a that is an optimal solution of (I_i) for somei and , then we can choosex ⁱ as a current efficient point. Pivoting on the reduced feasible set allows us to find a better efficient point or to show that the current efficient point is optimal for (P). Two algorithms for solving (P) in a finite sequence of pivots are presented along with a numerical example.The authors would like to thank an anonymous referee, H. P. Benson, and P. L. Yu for numerous helpful comments on this paper.     

A Finite Branch-and-Bound Algorithm for Linear Multiplicative Programming

On the basis of Soland's rectangular branch-and-bound, we develop an algorithm for minimizing a product of p (2) affine functions over a polytope. To tighten the lower bound on the value of each subproblem, we install a second-stage bounding procedure, which requires O(p) additional time in each iteration but remarkably reduces the number of branching operations. Computational results indicate that the algorithm is practical if p is less than 15, both in finding an exact optimal solution and an approximate solution.     

双层线性规划的一个全局优化方法

用线性规划对偶理论分析了双层线性规划的最优解与下层问题的对偶问题可行域上极点之间的关系，通过求得下层问题的对偶问题可行域上的极点，将双层线性规划转化为有限个线性规划问题，从而用线性规划方法求得问题的全局最优解．由于下层对偶问题可行域上只有有限个极点，所以方法具有全局收敛性．     

求解二层线性规划问题的一种算法

对下层含有约束的二层线性规划问题,提出了求全局最优解的一种算法.首先由该算法求出约束凸集的全部极点,再对极点进行可行性检验,从而得到了二层线性规划问题的全局最优解,最后以实例验证了算法的有效性.     

多属性决策中的目标规划

针对只有部分权重信息的对方案有偏好的多属性决策问题,本文给出了一种简单的目标规划模型,通过对该模型的求解却可得到决策方案的排序。最后给出了一个算例。     

综合型模糊线性规划分析

模糊线性规划问题是模糊数学规划的研究基础，已经有许多学在这一领域取得了卓有成效的研究成果。但这些研究都是针对特定类型的模糊线性规划开展的，而没有将模糊线性规划放在一般环境下进行综合考虑。本对模糊线性规划的一般模型进行了分析，提出了综合型模糊线性规划问题的求解方法。     

线性规划的目标函数最速递减算法

在对偶单纯形方法的基础上，提出了线性规划的目标函数最速递减算法。它避开求初始可行基或初始基，以目标函数全局快速递减作为选基准则，将选基过程与换基迭代合二为一，从而大大减少了迭代次数。数值算例显示了该算法的有效性和优越性。     

一个改进的解线性规划问题的熵函数法

本文将有效因子的概念引入到Shannon熵的信息结构中,提出了一个改进的解线规划问题的熵函数法,随后的理论结果和数值例子表明了本文提出了的方法是有效的。     

一种改进的双层规划内点算法(英文)

本文针对线性双层规划问题提出一个由KMY算法演变而来的原对偶内点算法.与现在很多线性双层规划单纯型算法不同,作者提出的算法从一可行初始点穿过约束多面体内部直接得到近似最优解,当约束条件和变量数目增加时,本算法的迭代次数和计算时间变化很小.所以大大提高实际可操作性能和运算效率.