Search

For linear optimization problems with a parametric objective, so-called parametric linear programs (PLP), we show that the optimal decision values are, under few technical restrictions, unimodal functions of the parameter, at least in the two-degrees-of-freedom case. Assuming that the parameter is random and follows a known probability distribution, this allows for an efficient algorithm to determe the quantiles of linear combinations of the optimal decisions. The novel results are demonstrated with probabilistic economic dispatch. For an example setup with uncertain fuel costs, quantiles of the resulting inter-regional power flows are computed. The approach is compared against Monte Carlo and piecewise computation techniques, proving significantly reduced computation times for the novel procedure. This holds especially when the feasible set is complex and/or extreme quantiles are desired. This work is limited to problems with two effective degrees of freedom and a one-dimensional uncertainty. Future extensions to higher dimensions could yield a key tool for the analysis of probabilistic PLPs and, specifically, risk management in energy systems. [ABSTRACT FROM AUTHOR]

For linear optimization problems with a parametric objective, so-called parametric linear programs (PLP), we show that the optimal decision values are, under few technical restrictions, unimodal functions of the parameter, at least in the two-degrees-of-freedom case. Assuming that the parameter is random and follows a known probability distribution, this allows for an efficient algorithm to determe the quantiles of linear combinations of the optimal decisions. The novel results are demonstrated with probabilistic economic dispatch. For an example setup with uncertain fuel costs, quantiles of the resulting inter-regional power flows are computed. The approach is compared against Monte Carlo and piecewise computation techniques, proving significantly reduced computation times for the novel procedure. This holds especially when the feasible set is complex and/or extreme quantiles are desired. This work is limited to problems with two effective degrees of freedom and a one-dimensional uncertainty. Future extensions to higher dimensions could yield a key tool for the analysis of probabilistic PLPs and, specifically, risk management in energy systems.

The model of using the resources optimally is a well-known one in the theory of linear optimization. It provides an opportunity for determining an optimal production plan for a certain number of products based on given cost rates of each resource to produce one unit of each product, given stock quantities of raw materials used and given prices of the final products. In the present paper an opportunity to determine the optimal production plan is revealed if some of the cost rates are not fixed but depend on a parameter. The methods of parametric linear optimization are used, demonstrating options to apply the graphical method for solving a two-dimensional problem for using the resources. [ABSTRACT FROM AUTHOR]

Depending on the nature, objectives, and constraints of the decision variables; linear programming, nonlinear programming, integer programming, mixed integer programming etc. can be classified. Extensive research has been conducted to solve all types of these problems in a parametric context. In this paper, to solve optimization problems having uncertainties represented by a single parameter on the objective function, a systematic linearization approach is developed considering the parametric expression as nonlinear. In the proposed approach, the objective function is considered as nonlinear which is converted into linear by using first order Taylor series expansion at the points making the parametric costs zero. Thus, the optimal solution is obtained from the constructed linear programming problem. In this way, by determining the intervals in which the optimal solution changes, the solution of the parametric linear programming problem is obtained. A numerical experiment is illustrated to present the effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]

Debottlenecking is highly desirable to increase the production throughput for the oil sands industry. In this work, the bottleneck identification and capacity expansion problem is solved through optimization techniques. In the proposed debottlenecking procedure, first-principles method and Gaussian process modeling approach are applied to build process models. Depending on the type of process model used, the optimization problem is solved either as a parametric linear programming problem or as a nonlinear optimization problem. By solving the optimization problem, the bottlenecks can be identified and the necessary capacity expansion for process units for bottleneck removal is reported. The proposed method is demonstrated through applications in oil sands production process. [ABSTRACT FROM AUTHOR]

We consider the problem of determining the interval hull solution l∗ to a parametric linear programming (PLP) problem l(x, p) = cT(p)x, where ci(p) can be in general nonlinear functions of p, and x satisfy the constraint A(p)x = b(p), p ∈ p. A new iterative method for determining l∗ is suggested. The method exploits the concept of the p-solution to a square linear interval parametric (LIP) system, having the parametric form x(p) = Lp + a, p ∈ p, where L is a real n × m matrix (n and m are, respectively, the sizes of the square matrix A and vector p), whereas a is an interval vector. A numerical example is provided to illustrate the new approach. [ABSTRACT FROM AUTHOR]

We propose a new approach to computing a parametric solution (the so-called p-solution) to parametric interval linear systems. Solving such system is an important part of many scientific and engineering problems involving uncertainties. The parametric solution has many useful properties. It permits to compute an outer solution, an inner estimate of the interval hull solution, and intervals containing the lower and upper bounds of the interval hull solution. It can also be employed for solving various constrained optimisation problems related to the parametric interval linear system. The proposed approach improves both outer and inner bounds for the parametric solution set. In this respect, the new approach is competitive to most of the existing methods for solving parametric interval linear systems. Improved bounds on the parametric solution set guarantees improved bounds for the solutions of related optimisation problems. [ABSTRACT FROM AUTHOR]

The fuzzy sets theory has been applied in many fields, such as operations research, control theory and management sciences, etc. In particular, an application of this theory in decision making problem is linear programming problems with fuzzy technological coefficients numbers, as well as studying the parametric linear programming problems in the case of changes in the objective function. In this paper presenting a new procedure which connects and makes link between fuzzy linear programming problem with fuzzy technological coefficients numbers and parametric linear programming problem with change in coefficients of the objective function, then develop a numerical example illustrates the steps of solution to this kind of problems.

El uso de la teoría de los conjuntos difusos como una metodología para el modelado y análisis de sistemas de decisión es de particular interés para investigadores en ingeniería industrial, debido a la capacidad para permitir un análisis cualitativo y cuantitativo de los problemas que implican vaguedad e imprecisión. Es así como, en un esfuerzo por obtener una mejor compresión del uso de la lógica difusa en la ingeniería industrial y más específicamente en el campo de la planificación de la producción, se proporciona en el presente artículo un problema de planeación de requerimiento de materiales (MRP) bajo condiciones de incertidumbre aplicado a la industria automotriz, y el cual es solucionado a través de programación lineal paramétrica difusa.

Electric energy market participants face risks and uncertainties associated with the ever-changing market environment. A profit-driven bidding decision tool is thus crucial for generation companies (GENCOs) to maintain a competitive position. Although optimal bidding strategies have been extensively studied in the literature, most previous research assumes continuous and differentiable generation offer curves, whereas actual offer curves are piecewise staircase curves. Based on the foregoing, this paper presents an optimal bidding strategy for GENCOs, derived by using parametric linear programming, and extends the proposed method to consider incomplete information. We show that the proposed algorithm is able to utilize the characteristics of piecewise staircase energy offer curves in contrast to the findings of previous researchers. [ABSTRACT FROM AUTHOR]

We consider statistical procedures for feature selection defined by a family of regularization problems with convex piecewise linear loss functions and penalties of l nature. Many known statistical procedures (e.g. quantile regression and support vector machines with l-norm penalty) are subsumed under this category. Computationally, the regularization problems are linear programming (LP) problems indexed by a single parameter, which are known as 'parametric cost LP' or 'parametric right-hand-side LP' in the optimization theory. Exploiting the connection with the LP theory, we lay out general algorithms, namely, the simplex algorithm and its variant for generating regularized solution paths for the feature selection problems. The significance of such algorithms is that they allow a complete exploration of the model space along the paths and provide a broad view of persistent features in the data. The implications of the general path-finding algorithms are outlined for several statistical procedures, and they are illustrated with numerical examples. [ABSTRACT FROM AUTHOR]

In the last decades, many efforts have been devoted to develop methods for automatic scene understanding in the context of video surveillance applications. This paper presents a novel nonobject centric approach for complex scene analysis. Similarly to previous methods, we use low-level cues to individuate atomic activities and create clip histograms. Differently from recent works, the task of discovering high-level activity patterns is formulated as a convex prototype learning problem. This problem results in a simple linear program that can be solved efficiently with standard solvers. The main advantage of our approach is that, using as the objective function the Earth Mover's Distance (EMD), the similarity among elementary activities is taken into account in the learning phase. To improve scalability we also consider some variants of EMD adopting L_1 as ground distance for 1D and 2D, linear and circular histograms. In these cases, only the similarity between neighboring atomic activities, corresponding to adjacent histogram bins, is taken into account. Therefore, we also propose an automatic strategy for sorting atomic activities. Experimental results on publicly available datasets show that our method compares favorably with state-of-the-art approaches, often outperforming them. [ABSTRACT FROM AUTHOR]

Abstract: This study intends to develop easy-to-implement and effective approaches to help decision makers cope with the challenges of designing their optimal systems, and determine the corresponding optimal budgets. The approaches are realized by constructing optimal system design (OSD) data envelopment analysis (DEA) models that build on the concepts and techniques of DEA, de novo programming and parametric linear programming with a parametric right-hand side. The proposed models explicitly take the important issue of congestion in system design into account. Therefore, the OSD DEA models can help decision makers not only optimally design their systems, but also determine their optimal budgets. Numerical examples are used to evaluate the strengths of the proposed models. [Copyright &y& Elsevier]

Abstract: This paper discusses properties of the graphs of 2-way and 3-way transportation polytopes, in particular, their possible numbers of vertices and their diameters. Our main results include a quadratic bound on the diameter of axial 3-way transportation polytopes and a catalogue of non-degenerate transportation polytopes of small sizes. The catalogue disproves five conjectures about these polyhedra stated in the monograph by Yemelichev et al. (1984). It also allowed us to discover some new results. For example, we prove that the number of vertices of an transportation polytope is a multiple of the greatest common divisor of m and n. [Copyright &y& Elsevier]

This paper presents a parametric approach for duality in fuzzy multi-criteria and multi-constraint level linear programming (MC2LP) which extends fuzzy linear programming approaches. First, the MC2-simplex method is used to solve the crisp prima–dual MC2LP pair and then, through these crisp formulations, separate membership functions are constructed for fuzzy primal and dual program by considering the corresponding primal and dual decisions. For each program, a set of fuzzy potential solutions is determined in terms of the membership function and the related optimal solution with a certain range of decision parameters. Finally, using the primal and dual membership functions, a fuzzy weak duality function is obtained for any pair of primal and dual fuzzy potential solutions. [Copyright &y& Elsevier]

Copyright of INFOR is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

The objective of this paper is to deal with a kind of fuzzy linear programming problem based on interval-valued fuzzy sets (IVFLP) through the medium of procedure that turns IVFLP into parametric linear programming via the mathematical programming. Some useful results for the benefit of solving IVFLP are expounded and proved, developed and discussed. Furthermore, that the proposed techniques in this paper allow the decision-maker to assign a different degree of importance can provide a useful way to efficiently help the decision-maker make their decisions. [ABSTRACT FROM AUTHOR]

We present a decomposition method for indefinite quadratic programming problems having n variables and m linear constraints. The given problem is decomposed into at most m QP subproblems each having m linear constraints and n-1 variables. All global minima, all isolated local minima and some of the non-isolated local minima for the given problem are obtained from those of the lower dimensional subproblems. One way to continue solving the given problem is to apply the decomposition method again to the subproblems and repeatedly doing so until subproblems of dimension 1 are produced and these can be solved directly. A technique to reduce the potentially large number of subproblems is formulated. [ABSTRACT FROM AUTHOR]

A path-following philosophy (continuation method, global Newton method) is used to compute equilibria for piecewise linear economies while taking advantage of the linear structure of the model. The existence of a path leading through certain faces of a polyhedral set to an equilibrium point is demonstrated. Computational experience is reported which indicates that this method is promising for models dealing with many commodities and relatively few consumers. [ABSTRACT FROM AUTHOR]

We consider a linear programming problem, with two parameters in the objective function, and present an algorithm for finding the decomposition of the parameter space into maximal polyhedral areas in which particular basic solutions are optimal. Special attention is paid to fill up areas of degenerate solutions. [ABSTRACT FROM AUTHOR]

We present a new definition of optimality intervals for the parametric right-hand side linear programming (parametric RHS LP) Problem ϑ(λ) = min{ c x¦ Ax = b + λ¯b, x ≥ 0}. We then show that an optimality interval consists either of a breakpoint or the open interval between two consecutive breakpoints of the continuous piecewise linear convex function ϑ(λ). As a consequence, the optimality intervals form a partition of the closed interval {λ; ¦ϑ(λ)¦ < ∞}. Based on these optimality intervals, we also introduce an algorithm for solving the parametric RHS LP problem which requires an LP solver as a subroutine. If a polynomial-time LP solver is used to implement this subroutine, we obtain a substantial improvement on the complexity of those parametric RHS LP instances which exhibit degeneracy. When the number of breakpoints of ϑ(λ) is polynomial in terms of the size of the parametric problem, we show that the latter can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

A new zero-one integer programming model for the job shop scheduling problem with minimum makespan criterion is presented. The algorithm consists of two parts: (a) a branch and bound parametric linear programming code for solving the job shop problem with fixed completion time; (b) a problem expanding algorithm for finding the optimal completion time. Computational experience for problems having up to thirty-six operations is presented. The largest problem solved was limited by memory space, not computation time. Efforts are under way to improve the efficiency of the algorithm and to reduce its memory requirements. [ABSTRACT FROM AUTHOR]