Determining maximal efficient faces in multiobjective linear programming problem

Finding an efficient or weakly efficient solution in a multiobjective linear programming (MOLP) problem is not a difficult task. The difficulty lies in finding all these solutions and representing their structures. Since there are many convenient approaches that obtain all of the (weakly) efficient extreme points and (weakly) efficient extreme rays in an MOLP, this paper develops an algorithm which effectively finds all of the (weakly) efficient maximal faces in an MOLP using all of the (weakly) efficient extreme points and extreme rays. The proposed algorithm avoids the degeneration problem, which is the major problem of the most of previous algorithms and gives an explicit structure for maximal efficient (weak efficient) faces. Consequently, it gives a convenient representation of efficient (weak efficient) set using maximal efficient (weak efficient) faces. The proposed algorithm is based on two facts. Firstly, the efficiency and weak efficiency property of a face is determined using a relative interior point of it. Secondly, the relative interior point is achieved using some affine independent points. Indeed, the affine independent property enable us to obtain an efficient relative interior point rapidly.     

Interior-Point Methods with Decomposition for Solving Large-Scale Linear Programs

This paper deals with an algorithm incorporating the interior-point method into the Dantzig–Wolfe decomposition technique for solving large-scale linear programming problems. The algorithm decomposes a linear program into a main problem and a subproblem. The subproblem is solved approximately. Hence, inexact Newton directions are used in solving the main problem. We show that the algorithm is globally linearly convergent and has polynomial-time complexity.     

A methodology for assessing eco-efficiency in logistics networks

Recent literature on sustainable logistics networks points to two important questions: (i) How to spot the preferred solution(s) balancing environmental and business concerns? (ii) How to improve the understanding of the trade-offs between these two dimensions? We posit that a visual exploration of the efficient frontier and trade-offs between profitability and environmental impacts are particularly suitable to answer these two questions. The visual representation of the efficient frontier, however, presents two challenges. The first is to obtain a good approximation for such frontier without enumerating all extreme efficient solutions. The second is to obtain a good visual representation of the efficient frontier. We propose a two-phased heuristic to handle these two problems. The algorithm is designed for the multi-objective linear problem with three objectives: minimize costs, cumulative energy demand and waste in a reverse logistics network. We illustrate our approach by designing a complex recycling logistics network in Germany.     

A dynamic programming algorithm for the bilevel knapsack problem

We propose an efficient dynamic programming algorithm for solving a bilevel program where the leader controls the capacity of a knapsack, and the follower solves the resulting knapsack problem. We propose new recursive rules and show how to solve the problem as a sequence of two standard knapsack problems.     

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

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

Finding DEA-efficient hyperplanes using MOLP efficient faces

This paper suggests a method for finding efficient hyperplanes with variable returns to scale the technology in data envelopment analysis (DEA) by using the multiple objective linear programming (MOLP) structure. By presenting an MOLP problem for finding the gradient of efficient hyperplanes, We characterize the efficient faces. Thus, without finding the extreme efficient points of the MOLP problem and only by identifying the efficient faces of the MOLP problem, we characterize the efficient hyperplanes which make up the DEA efficient frontier. Finally, we provide an algorithm for finding the efficient supporting hyperplanes and efficient defining hyperplanes, which uses only one linear programming problem.     

Complexity of linear programming

The complexity of linear programming is discussed in the “integer” and “real number” models of computation. Even though the integer model is widely used in theoretical computer science, the real number model is more useful for estimating an algorithm's running time in actual computation.Although the ellipsoid algorithm is a polynomial-time algorithm in the integer model, we prove that it has unbounded complexity in the real number model. We conjecture that there exists no polynomial-time algorithm for the linear inequalities problem in the real number model. We also conjecture that linear inequalities are strictly harder than linear equalities in all “reasonable” models of computation.     

On Extracting Maximum Stable Sets in Perfect Graphs Using Lovász's Theta Function

We study the maximum stable set problem. For a given graph, we establish several transformations among feasible solutions of different formulations of Lovász's theta function. We propose reductions from feasible solutions corresponding to a graph to those corresponding to its induced subgraphs. We develop an efficient, polynomial-time algorithm to extract a maximum stable set in a perfect graph using the theta function. Our algorithm iteratively transforms an approximate solution of the semidefinite formulation of the theta function into an approximate solution of another formulation, which is then used to identify a vertex that belongs to a maximum stable set. The subgraph induced by that vertex and its neighbors is removed and the same procedure is repeated on successively smaller graphs. We establish that solving the theta problem up to an adaptively chosen, fairly rough accuracy suffices in order for the algorithm to work properly. Furthermore, our algorithm successfully employs a warm-start strategy to recompute the theta function on smaller subgraphs. Computational results demonstrate that our algorithm can efficiently extract maximum stable sets in comparable time it takes to solve the theta problem on the original graph to optimality. This work was supported in part by NSF through CAREER Grant DMI-0237415. Part of this work was performed while the first author was at the Department of Applied Mathematics and Statisticsat Stony Brook University, Stony Brook, NY, USA.     

An efficient and simple model for multiple criteria supplier selection problem

Simply looking for vendors offering the lowest prices is not “efficient sourcing” any more. Selection of suppliers is a multiple criteria decision. We propose a weighted linear program for the multi-criteria supplier selection problem. In addition to mathematical formulation, this paper studies a transformation technique which enables our proposed model to be solved without an optimizer. The model for multi-criteria supplier selection problem can be easily implemented with a spreadsheet package. The model can be widely applied to practical situations and does not require the user with any optimization background.     

Random problem generation and the computation of efficient extreme points in multiple objective linear programming

This paper looks at the task of computing efficient extreme points in multiple objective linear programming. Vector maximization software is reviewed and the ADBASE solver for computing all efficient extreme points of a multiple objective linear program is described. To create MOLP test problems, models for random problem generation are discussed. In the computational part of the paper, the numbers of efficient extreme points possessed by MOLPs (including multiple objective transportation problems) of different sizes are reported. In addition, the way the utility values of the efficient extreme points might be distributed over the efficient set for different types of utility functions is investigated. Not surprisingly, results show that it should be easier to find good near-optimal solutions with linear utility functions than with, for instance, Tchebycheff types of utility functions.Dedicated to Professor George B. Dantzig on the occasion of his eightieth birthday.     

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.     

Optimal Prioritized Infeasibility Handling in Model Predictive Control: Parametric Preemptive Multiobjective Linear Programming Approach

All practical implementations of model-based predictive control (MPC) require a means to recover from infeasibility. We propose a strategy designed for linear state-space MPC with prioritized constraints. It relaxes optimally an infeasible MPC optimization problem into a feasible one by solving a single-objective linear program (LP) online in addition to the standard online MPC optimization problem at each sample. By optimal, it is meant that the violation of a lower prioritized constraint cannot be made less without increasing the violation of a higher prioritized constraint. The problem of computing optimal constraint violations is naturally formulated as a parametric preemptive multiobjective LP. By extending well-known results from parametric LP, the preemptive multiobjective LP is reformulated into an equivalent standard single-objective LP. An efficient algorithm for offline design of this LP is given, and the algorithm is illustrated on an example.     

A computer graphics-based Decision Support System for multiple objective linear programming

In this paper we propose a computer-graphics based Decision Support System for multiple objective linear programming that builds on the VIG system (Visual Interactive Goal programming). The essential part of the VIG system is Pareto Race, a dynamic and visual approach for exploring the efficient frontier of a multiple objective linear programming problem. Our objective is to extend Pareto Race to large-scale multiple objective linear programming. The approach works with any efficient solutions that are in general not extreme point solutions. Interactive use of computer graphics plays a central role. The approach, the underlying theory, and an illustrative example are described.     

A modified method for constructing efficient solutions structure of MOLP

This paper deals with a recently proposed algorithm for obtaining all weak efficient and efficient solutions in a multi objective linear programming (MOLP) problem. The algorithm is based on solving some weighted sum problems, and presents an easy and clear solution structure. We first present an example to show that the algorithm may fail when at least one of these weighted sum problems has not a finite optimal solution. Then, the algorithm is modified to overcome this problem. The modified algorithm determines whether an efficient solution exists for a given MOLP and generates the solution set correctly (if exists) without any change in the complexity.     

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.     

Rescheduling unrelated parallel machines with total flow time and total disruption cost criteria

In this paper, we consider a rescheduling problem where a set of jobs has already been assigned to unrelated parallel machines. When a disruption occurs on one of the machines, the affected jobs are rescheduled, considering the efficiency and the schedule deviation measures. The efficiency measure is the total flow time, and the schedule deviation measure is the total disruption cost caused by the differences between the initial and current schedules. We provide polynomial-time solution methods to the following hierarchical optimization problems: minimizing total disruption cost among the minimum total flow time schedules and minimizing total flow time among the minimum total disruption cost schedules. We propose exponential-time algorithms to generate all efficient solutions and to minimize a specified function of the measures. Our extensive computational tests on large size problem instances have revealed that our optimization algorithm finds the best solution by generating only a small portion of all efficient solutions.     

Fathoming rules for biobjective mixed integer linear programs: Review and extensions

We consider the class of biobjective mixed integer linear programs (BOMILPs). We review fathoming rules for general BOMILPs and present them in a unified manner. We then propose new fathoming rules that rely on solving specially designed LPs, hence making no assumption on the type of problem and only using polynomial-time algorithms. We describe an enhancement for carrying out these rules by performing a limited number of pivot operations on an LP, and then we provide insight that helps to make these rules even more efficient by either focusing on a smaller number of feasible solutions or by resorting to heuristics that limit the number of LPs solved.     

Lot-sizing with non-stationary cumulative capacities

We study a new class of capacitated economic lot-sizing problems. We show that the problem is NP-hard in general and derive a fully polynomial-time approximation algorithm under mild conditions on the cost functions. Furthermore, we develop a polynomial-time algorithm for the case where all cost functions are concave.     

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.