A Bilinear Algorithm for Optimizing a Linear Function over the Efficient Set of a Multiple Objective Linear Programming Problem

The problem Q of optimizing a linear function over the efficient set of a multiple objective linear program serves several useful purposes in multiple criteria decision making. However, Q is in itself a difficult global optimization problem, whose local optima, frequently large in number, need not be globally optimal. Indeed, this is due to the fact that the feasible region of Q is, in general, a nonconvex set. In this paper we present a monotonically increasing algorithm that finds an exact, globally-optimal solution for Q. Our approach does not require any hypothesis on the boundedness of neither the efficient set EP nor the optimal objective value. The proposed algorithm relies on a simplified disjoint bilinear program that can be solved through the use of well-known specifically designed methods within nonconvex optimization. The algorithm has been implemented in C and preliminary numerical results are reported.     

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.     

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

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

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.     

An Outcome Space Branch and Bound-Outer Approximation Algorithm for Convex Multiplicative Programming

This article presents a new global solution algorithm for Convex Multiplicative Programming called the Outcome Space Algorithm. To solve a given convex multiplicative program (P _D), the algorithm solves instead an equivalent quasiconcave minimization problem in the outcome space of the original problem. To help accomplish this, the algorithm uses branching, bounding and outer approximation by polytopes, all in the outcome space of problem (P _D). The algorithm economizes the computations that it requires by working in the outcome space, by avoiding the need to compute new vertices in the outer approximation process, and, except for one convex program per iteration, by requiring for its execution only linear programming techniques and simple algebra.     

Outcome Space Partition of the Weight Set in Multiobjective Linear Programming

Approaches for generating the set of efficient extreme points of the decision set of a multiple-objective linear program (P) that are based upon decompositions of the weight set W⁰ suffer from one of two special drawbacks. Either the required computations are redundant, or not all of the efficient extreme point set is found. This article shows that the weight set for problem (P) can be decomposed into a partition based upon the outcome set Y of the problem, where the elements of the partition are in one-to-one correspondence with the efficient extreme points of Y. As a result, the drawbacks of the decompositions of W⁰ based upon the decision set of problem (P) disappear. The article explains also how this new partition offers the potential to construct algorithms for solving large-scale applications of problem (P) in the outcome space, rather than in the decision space.     

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

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

An Outer Approximation Algorithm Guaranteeing Feasibility of Solutions and Approximate Accuracy of Optimality

We treat a concave programming problem with a compact convex feasible set. Assuming the differentiability of the convex functions which define the feasible set, we propose two solution methods. Those methods utilize the convexity of the feasible set and the property of the normal cone to the feasible set at each point over the boundary. Based on the proposed two methods, we propose a solution algorithm. This algorithm takes advantages over classical methods: (1) the obtained approximate solution is always feasible, (2) the error of such approximate value can be evaluated properly for the optimal value of such problem, (3) the algorithm does not have any redundant iterations.     

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

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

Hybrid Approach for Solving Multiple-Objective Linear Programs in Outcome Space

Various difficulties arise 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 begun to develop tools for analyzing and solving problem (MOLP) in outcome space, rather than in decision space. In this article, we present and validate a new hybrid vector maximization approach for solving problem (MOLP) in outcome space. The approach systematically integrates a simplicial partitioning technique into an outer approximation procedure to yield an algorithm that generates the set of all efficient extreme points in the outcome set of problem (MOLP) in a finite number of iterations. Some key potential practical and computational advantages of the approach are indicated.     

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.     

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.     

解可分离约束双凹规划问题的一种外逼近方法[英文]

在本文中，我们提出了双凹规划问题和更一般的广义凹规划问题。我们给出了双凹规划问题的整体最优性条件，并构造了一个有限终止外逼近算法。     

带惩罚的动态设施选址问题的近似算法

本文研究带惩罚的动态设施选址问题,在该问题中假设不同时段内设施的开放费用、用户的需求及连接费用可以不相同,而且允许用户的需求不被满足,但是要有惩罚.对此问题我们给出了第-个近似比为1.8526的原始对偶(组合)算法.     

一类多乘积规划的加速算法

针对一类多乘积规划问题(MP),给出一个加速算法.首先导出一个与(MP)等价的逆凸问题(RCP),然后构造问题(RCP)的线性松弛化问题.算法的主要特点是提出了两个加速技巧,这些技巧可以用于改善算法的收敛速度.数值算例表明算法是可行的.     

A Linear Time Algorithm for the Minimum-weight Feedback Vertex Set Problem in Series-parallel Graphs

A feedback vertex set is a subset of vertices in a graph, whose deletion from the graph makes the resulting graph acyclic. In this paper, we study the minimum-weight feedback vertex set problem in seriesparallel graphs and present a linear-time exact algorithm to solve it.     

An all-linear programming relaxation algorithm for optimizing over the efficient set

The problem (P) of optimizing a linear function over the efficient set of a multiple objective linear program has many important applications in multiple criteria decision making. Since the efficient set is in general a nonconvex set, problem (P) can be classified as a global optimization problem. Perhaps due to its inherent difficulty, it appears that no precisely-delineated implementable algorithm exists for solving problem (P) globally. In this paper a relaxation algorithm is presented for finding a globally optimal solution for problem (P). The algorithm finds an exact optimal solution to the problem after a finite number of iterations. A detailed discussion is included of how to implement the algorithm using only linear programming methods. Convergence of the algorithm is proven, and a sample problem is solved.Research supported by a grant from the College of Business Administration, University of Florida, Gainesville, Florida, U.S.A.     

线性分式规划最优解集的求法

本文使用多面集的表示定理，导出了线性分式规划最优解集的结构，并给出确定全部最优解的计算步骤。     

Enumeration of All Possibly Optimal Vertices with Possible Optimality Degrees in Linear Programming Problems with a Possibilistic Objective Function

In this paper, we treat linear programming problems with fuzzy objective function coefficients. To such a problem, the possibly optimal solution set is defined as a fuzzy set. It is shown that any possibly optimal solution can be represented by a convex combination of possibly optimal vertices. A method to enumerate all possibly optimal vertices with their membership degrees is developed. It is shown that, given a possibly optimal extreme point with a higher membership degree, the membership degree of an adjacent extreme point is calculated by solving a linear programming problem and that all possibly optimal vertices are enumerated sequentially by tracing adjacent possibly optimal extreme points from a possibly optimal extreme point with the highest membership degree.