On approximation of the best case optimal value in interval linear programming

Interval linear programming addresses problems with uncertain coefficients and the only information that we have is that the true values lie somewhere in the prescribed intervals. For the inequality constraint problem, computing the worst case scenario and the corresponding optimal value is an easy task, but the best case optimal value calculation is known to be NP-hard. In this paper, we discuss lower and upper bound approximation for the best case optimal value, and propose suitable methods for both of them. We also propose a not apriori exponential algorithm for computing the best case optimal value. The presented techniques are tested by randomly generated data, and also applied in a simple data classification problem.     

Complexity of necessary efficiency in interval linear programming and multiobjective linear programming

We present some complexity results on checking necessary efficiency in interval multiobjective linear programming. Supposing that objective function coefficients perturb within prescribed intervals, a feasible point x* is called necessarily efficient if it is efficient for all instances of interval data. We show that the problem of checking necessary efficiency is co-NP-complete even for the case of only one objective. Provided that x* is a non-degenerate basic solution, the problem is polynomially solvable for one objective, but remains co-NP-hard in the general case. Some open problems are mentioned at the end of the paper.     

Generalized linear fractional programming under interval uncertainty

Data in many real-life engineering and economical problems suffer from inexactness. Herein we assume that we are given some intervals in which the data can simultaneously and independently perturb. We consider a generalized linear fractional programming problem with interval data and present an efficient method for computing the range of optimal values. The method reduces the problem to solving from two to four real-valued generalized linear fractional programs, which can be computed in polynomial time using an appropriate interior point method solver.     

On strong optimality of interval linear programming

We consider a linear programming problem with interval data. We discuss the problem of checking whether a given solution is optimal for each realization of interval data. This problem was studied for particular forms of linear programming problems. Herein, we extend the results to a general model and simplify the overall approach. Moreover, we inspect computational complexity, too. Eventually, we investigate a related optimality concept of semi-strong optimality, showing its characterization and complexity.     

Strong optimal solutions of interval linear programming

This paper considers optimal solutions of general interval linear programming problems. The new concepts of optimal solutions are introduced in a unified framework. Some existed optimal solution concepts of interval linear program such as weak and strong optimal solutions are special cases in this framework. Necessary and sufficient conditions for checking optimality are developed. Also, the features of the proposed methods are illustrated by some examples.     

Optimal value function in semi-infinite programming

In this paper, we provide a systematic approach to the main topics in linear semi-infinite programming by means of a new methodology based on the many properties of the sub-differential mapping and the closure of a given convex function. In particular, we deal with the duality gap problem and its relation to the discrete approximation of the semi-infinite program. Moreover, we have made precise the conditions that allow us to eliminate the duality gap by introducing a perturbation in the primal objective function. As a by-product, we supply different extensions of well-known results concerning the subdifferential mapping.     

Optimal value functions in parametric programming

Optimal value functions in parametric programming are studied as compositions of objective functions and point-to-set mappings which define the constrained sets. Sufficiency conditions for the common regularity properties of optimal value functions are derived.

---

Zusammenfassung Der Optimalwert eines parametrischen Programms wird aufgefaßt als Verknüpfung der Zielfunktion mit einer mengenwertigen Abbildung, die den zulässigen Bereich definiert. Es werden hinreichende Bedingungen für einige häufig benutzte Regularitätseigenschaften der Optimalwertfunktion hergeleitet.

     

Optimal portfolios using linear programming models

The classical quadratic programming (QP) formulation of the well-known portfolio selection problem has traditionally been regarded as cumbersome and time consuming. This paper formulates two additional models: (i) maximin, and (ii) minimization of mean absolute deviation. Data from 67 securities over 48 months are used to examine to what extent all three formulations provide similar portfolios. As expected, the maximin formulation yields the highest return and risk, while the QP formulation provides the lowest risk and return, which also creates the efficient frontier. The minimization of mean absolute deviation is close to the QP formulation. When the expected returns are confronted with the true ones at the end of a 6-month period, the maximin portfolios seem to be the most robust of all.     

How to determine basis stability in interval linear programming

Interval linear programming (ILP) was introduced in order to deal with linear programming problems with uncertainties that are modelled by ranges of admissible values. Basic tasks in ILP such as calculating the optimal value bounds or set of all possible solutions may be computationally very expensive. However, if some basis stability criterion holds true then the problems becomes much more easy to solve. In this paper, we propose a method for testing basis stability. Even though the method is exponential in the worst case (not surprisingly due to NP-hardness of the problem), it is fast in many cases.     

A new equivalent transformation for interval inequality constraints of interval linear programming

In this paper, we have introduced a new approach to solve a class of interval linear programming (ILP) problems. Firstly, the novel concept of an interval ordering relation is further developed to make desired solution feasible. Secondly, according to the 3\(\upsigma \) law of normal distribution, a new equivalent transformation for constraints with the interval-valued coefficients of ILP is justified. Accordingly, the uncertainty stemmed from interval number could be replaced by the uncertainty of random variables. Consequently, the classical methodology of stochastic linear programming, a chance constrained programming model based on normal distribution is designed to work out the equivalent form of the original problem. This is because it allows us to carry out the optimization operation with a certain calibrated probability. A typical numerical example is given to illustrate how to apply equivalent transformation in order to realize ILP. Finally, we conclude this paper by elaborated comparisons among our method and selected existing solutions to advance our confidence of our research results as to their correctness and effectiveness.     

Optimal 3-terminal cuts and linear programming

Given an undirected graph G=(V,E) and three specified terminal nodes t ₁,t ₂,t ₃, a 3-cut is a subset A of E such that no two terminals are in the same component of G\A. If a non-negative edge weight c _e is specified for each e∈E, the optimal 3-cut problem is to find a 3-cut of minimum total weight. This problem is -hard, and in fact, is max- -hard. An approximation algorithm having performance guarantee has recently been given by Călinescu, Karloff, and Rabani. It is based on a certain linear-programming relaxation, for which it is shown that the optimal 3-cut has weight at most times the optimal LP value. It is proved here that can be improved to , and that this is best possible. As a consequence, we obtain an approximation algorithm for the optimal 3-cut problem having performance guarantee . In addition, we show that is best possible for this algorithm. Research of this author was supported by NSERC PGSB. Research supported by a grant from NSERC of Canada.     

Various approaches to multiobjective linear programming problems with interval costs and interval weights

Central European Journal of Operations Research - Optimization problems are often subject to various kinds of inexactness or inaccuracy of input data. Here, we consider multiobjective linear...     

Fuzzy linear programming under interval uncertainty based on IFS representation

The equivalence between the interval-valued fuzzy set (IVFS) and the intuitionistic fuzzy set (IFS) is exploited to study linear programming problems involving interval uncertainty modeled using IFS. The non-membership of IFS is constructed with three different viewpoints viz., optimistic, pessimistic, and mixed. These constructions along with their indeterminacy factors result in S-shaped membership functions in the fuzzy counterparts of the intuitionistic fuzzy linear programming models. The solution methodology of Yang et al. [45], and its subsequent generalization by Lin and Chen [33] are used to compute the optimal solutions of the three fuzzy linear programming models.     

A comparison of interval linear programming with the simplex method

A detailed comparison of the simplex method for linear programming with a recent interval linear programming algorithm reveals that the methods are identical in the sense that the same sequence of extreme points can be generated by either algorithm.     

The optimal solution set of the interval linear programming problems

Several methods exist for solving the interval linear programming (ILP) problem. In most of these methods, we can only obtain the optimal value of the objective function of the ILP problem. In this paper we determine the optimal solution set of the ILP as the intersection of some regions, by the best and the worst case (BWC) methods, when the feasible solution components of the best problem are positive. First, we convert the ILP problem to the convex combination problem by coefficients 0 ≤ λ _j , μ _ij , μ _i  ≤ 1, for i = 1, 2, . . . , m and j = 1, 2, . . . , n. If for each i, j, μ _ij  = μ _i  = λ _j  = 0, then the best problem has been obtained (in case of minimization problem). We move from the best problem towards the worst problem by tiny variations of λ _j , μ _ij and μ _i from 0 to 1. Then we solve each of the obtained problems. All of the optimal solutions form a region that we call the optimal solution set of the ILP. Our aim is to determine this optimal solution set by the best and the worst problem constraints. We show that some theorems to validity of this optimal solution set.     

The range of the efficient frontier in multiple objective linear programming

Because a rational decision maker should only select an efficient alternative in multiple criterion decision problems, the efficient frontier defined as the set of all efficient alternatives has become a central solution concept in multiple objective linear programming. Normally this set reduces the set of available alternatives of the underlying problem. There are several methods, mainly based on the simplex method, for computing the efficient frontier. This paper presents a quite different approach which uses a nonlinear parametric program, solved by Wolfe's algorithm, to determine the range of the efficient frontier.     

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.     

Optimal stopping,exponential utility,and linear programming

This paper uses linear programming to compute an optimal policy for a stopping problem whose utility function is exponential. This is done by transforming the problem into an equivalent one having additive utility and nonnegative (not necessarily substochastic) transition matrices.Research was supported by NSF Grant ENG 76-15599.     

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.