In the cluster analysis problem one seeks to partition a finite set of objects into disjoint groups (or clusters) such that each group contains relatively similar objects and, relatively dissimilar objects are placed ...
详细信息
In the cluster analysis problem one seeks to partition a finite set of objects into disjoint groups (or clusters) such that each group contains relatively similar objects and, relatively dissimilar objects are placed in different groups. For certain classes of the problem or, under certain assumptions, the partitioning exercise can be formulated as a sequence of linear programs (LPs), each with a parametric objective function. Such LPs can be solved using the parametric linear programming procedure developed by Gass and Saaty [(Gass, S., Saaty, T. (1955), Naval Research Logistics Quarterly 2, 39-45)]. In this paper, a parametric linear programming model for solving cluster analysis problems is presented. We show how this model can be used to find optimal solutions for certain variations of the clustering problem or, in other cases, for an approximation of the general clustering problem. (C) 1998 Elsevier Science B.V. All rights reserved.
We present a new definition of optimality intervals for the parametric right-hand side linearprogramming (parametric RHS LP) Problem phi(lambda) = min{c(T)x\Ax = b + lambda-bBAR, x greater-than-or-equal-to 0}. We the...
详细信息
We present a new definition of optimality intervals for the parametric right-hand side linearprogramming (parametric RHS LP) Problem phi(lambda) = min{c(T)x\Ax = b + lambda-bBAR, x greater-than-or-equal-to 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 phi(lambda). As a consequence, the optimality intervals form a partition of the closed interval {lambda;\phi(lambda)\ < infinity}. 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 phi(lambda) is polynomial in terms of the size of the parametric problem, we show that the latter can be solved in polynomial time.
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 maintai...
详细信息
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. (C) 2014 Elsevier Ltd. All rights reserved.
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...
详细信息
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.
We consider the problem of determining the interval hull solution l (au) to a parametric linear programming (PLP) problem l(x, p) = c (T) (p)x, where c (i) (p) can be in general nonlinear functions of p, and x satisfy...
详细信息
We consider the problem of determining the interval hull solution l (au) to a parametric linear programming (PLP) problem l(x, p) = c (T) (p)x, where c (i) (p) can be in general nonlinear functions of p, and x satisfy the constraint A(p)x = b(p), p a p. A new iterative method for determining l (au) 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) = L p + a, p a p, where L is a real n x 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.
For the widest class of parametriclinear programs with continuous dependence of coefficients on parameters, the following theorem is proven: for any parameter vectort 0 in the domain of definition of the maximum, if ...
详细信息
For the widest class of parametriclinear programs with continuous dependence of coefficients on parameters, the following theorem is proven: for any parameter vectort 0 in the domain of definition of the maximum, if the set of optimal solutions is bounded, then the maximum is upper semicontinuous att 0. If the same proviso is met also in the dual program, then the maximum must be continuous att 0.
Polyhedral projection is a main operation of the polyhedron abstract domain. It can be computed via parametric linear programming (PLP), which is more efficient than the classic Fourier-Motzkin elimination method. In ...
详细信息
ISBN:
(纸本)9783030323042;9783030323035
Polyhedral projection is a main operation of the polyhedron abstract domain. It can be computed via parametric linear programming (PLP), which is more efficient than the classic Fourier-Motzkin elimination method. In prior work, PLP was done in arbitrary precision rational arithmetic. In this paper, we present an approach where most of the computation is performed in floating-point arithmetic, then exact rational results are reconstructed. We also propose a workaround for a difficulty that plagued previous attempts at using PLP for computations on polyhedra: in general the linearprogramming problems are degenerate, resulting in redundant computations and geometric descriptions.
Convex polyhedra capture linear relations between variables. They are used in static analysis and optimizing compilation. Their high expressiveness is however barely used in verification because of their cost, often p...
详细信息
ISBN:
(数字)9783319667065
ISBN:
(纸本)9783319667065;9783319667058
Convex polyhedra capture linear relations between variables. They are used in static analysis and optimizing compilation. Their high expressiveness is however barely used in verification because of their cost, often prohibitive as the number of variables involved increases. Our goal in this article is to lower this cost. Whatever the chosen representation of polyhedra - as constraints, as generators or as both - expensive operations are unavoidable. That cost is mostly due to four operations: conversion between representations, based on Chernikova's algorithm, for libraries in double description;convex hull, projection and minimization, in the constraints-only representation of polyhedra. Libraries operating over generators incur exponential costs on cases common in program analysis. In the Verimag Polyhedra Library this cost was avoided by a constraints-only representation and reducing all operations to variable projection, classically done by Fourier-Motzkin elimination. Since Fourier-Motzkin generates many redundant constraints, minimization was however very expensive. In this article, we avoid this pitfall by expressing projection as a parametric linear programming problem. This dramatically improves efficiency, mainly because it avoids the post-processing minimization. We show how our new approach can be up to orders of magnitude faster than the previous approach implemented in the Verimag Polyhedra Library that uses only constraints and Fourier-Motzkin elimination, and on par with the conventional double description approach, as implemented in well-known libraries.
A procedure is proposed for the parametric linear programming problem where all the coefficients are linear or polynomial functions of a scalar parameter. The solution vector and the optimum value are determined expli...
详细信息
A procedure is proposed for the parametric linear programming problem where all the coefficients are linear or polynomial functions of a scalar parameter. The solution vector and the optimum value are determined explicitly as rational functions of the parameter. In addition to standard linearprogramming technique, only the determination of eigenvalues is required. The procedure is compared to those by Dinkelbach and Zsigmond, and a numerical example is given.
This paper presents a parametric approach for duality in fuzzy multi-criteria and multi-constraint level linearprogramming ((MCLP)-L-2) which extends fuzzy linearprogramming approaches. First, the MC2-simplex method...
详细信息
This paper presents a parametric approach for duality in fuzzy multi-criteria and multi-constraint level linearprogramming ((MCLP)-L-2) which extends fuzzy linearprogramming approaches. First, the MC2-simplex method is used to solve the crisp prima-dual (MCLP)-L-2 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. (C) 2002 Elsevier Science B.V. All rights reserved.
暂无评论