共查询到20条相似文献,搜索用时 578 毫秒
1.
Miles Lubin J. A. Julian Hall Cosmin G. Petra Mihai Anitescu 《Computational Optimization and Applications》2013,55(3):571-596
We present a parallelization of the revised simplex method for large extensive forms of two-stage stochastic linear programming (LP) problems. These problems have been considered too large to solve with the simplex method; instead, decomposition approaches based on Benders decomposition or, more recently, interior-point methods are generally used. However, these approaches do not provide optimal basic solutions, which allow for efficient hot-starts (e.g., in a branch-and-bound context) and can provide important sensitivity information. Our approach exploits the dual block-angular structure of these problems inside the linear algebra of the revised simplex method in a manner suitable for high-performance distributed-memory clusters or supercomputers. While this paper focuses on stochastic LPs, the work is applicable to all problems with a dual block-angular structure. Our implementation is competitive in serial with highly efficient sparsity-exploiting simplex codes and achieves significant relative speed-ups when run in parallel. Additionally, very large problems with hundreds of millions of variables have been successfully solved to optimality. This is the largest-scale parallel sparsity-exploiting revised simplex implementation that has been developed to date and the first truly distributed solver. It is built on novel analysis of the linear algebra for dual block-angular LP problems when solved by using the revised simplex method and a novel parallel scheme for applying product-form updates. 相似文献
2.
Parallel bundle-based decomposition for large-scale structured mathematical programming problems 总被引:2,自引:0,他引:2
Deepankar Medhi 《Annals of Operations Research》1990,22(1):101-127
In this paper, we present parallel bundle-based decomposition algorithms to solve a class of structured large-scale convex optimization problems. An example in this class of problems is the block-angular linear programming problem. By dualizing, we transform the original problem to an unconstrained nonsmooth concave optimization problem which is in turn solved by using a modified bundle method. Further, this dual problem consists of a collection of smaller independent subproblems which give rise to the parallel algorithms. We discuss the implementation on the CRYSTAL multi-computer. Finally, we present computational experience with block-angular linear programming problems and observe that more than 70% efficiency can be obtained using up to eleven processors for one group of test problems, and more than 60% efficiency can be obtained for relatively smaller problems using up to five processors for another group of problems. 相似文献
3.
4.
Cross decomposition for mixed integer programming 总被引:6,自引:0,他引:6
Tony J. Van Roy 《Mathematical Programming》1983,25(1):46-63
Many methods for solving mixed integer programming problems are based either on primal or on dual decomposition, which yield,
respectively, a Benders decomposition algorithm and an implicit enumeration algorithm with bounds computed via Lagrangean
relaxation. These methods exploit either the primal or the dual structure of the problem. We propose a new approach, cross
decomposition, which allows exploiting simultaneously both structures. The development of the cross decomposition method captures
profound relationships between primal and dual decomposition. It is shown that the more constraints can be included in the
Langrangean relaxation (provided the duality gap remains zero), the fewer the Benders cuts one may expect to need. If the
linear programming relaxation has no duality gap, only one Benders cut is needed to verify optimality. 相似文献
5.
Any linear (ordinary or semi-infinite) optimization problem, and also its dual problem, can be classified as either inconsistent or bounded or unbounded, giving rise to nine duality states, three of them being precluded by the weak duality theorem. The remaining six duality states are possible in linear semi-infinite programming whereas two of them are precluded in linear programming as a consequence of the existence theorem and the non-homogeneous Farkas Lemma. This paper characterizes the linear programs and the continuous linear semi-infinite programs whose duality state is preserved by sufficiently small perturbations of all the data. Moreover, it shows that almost all linear programs satisfy this stability property. 相似文献
6.
Bundle-based decomposition for large-scale convex optimization: Error estimate and application to block-angular linear programs 总被引:3,自引:0,他引:3
Robinson has proposed the bundle-based decomposition algorithm to solve a class of structured large-scale convex optimization problems. In this method, the original problem is transformed (by dualization) to an unconstrained nonsmooth concave optimization problem which is in turn solved by using a modified bundle method. In this paper, we give a posteriori error estimates on the approximate primal optimal solution and on the duality gap. We describe implementation and present computational experience with a special case of this class of problems, namely, block-angular linear programming problems. We observe that the method is efficient in obtaining the approximate optimal solution and compares favorably with MINOS and an advanced implementation of the Dantzig—Wolfe decomposition method. 相似文献
7.
We consider two-stage stochastic programming problems with integer recourse. The L-shaped method of stochastic linear programming
is generalized to these problems by using generalized Benders decomposition. Nonlinear feasibility and optimality cuts are
determined via general duality theory and can be generated when the second stage problem is solved by standard techniques.
Finite convergence of the method is established when Gomory’s fractional cutting plane algorithm or a branch-and-bound algorithm
is applied. 相似文献
8.
《European Journal of Operational Research》1997,101(2):306-316
We consider a mixed 0–1 integer programming problem with dual block-angular structure arising in two-stage stochastic programming. A relaxation is proposed such that the problem is decomposed into subproblems each corresponding to the outcomes of the random variable. The convex hull of feasible solutions for the relaxation is characterized using results from disjunctive programming and it is shown how Lift-and-Project cuts can be generated for one subproblem and made valid for different outcomes. 相似文献
9.
This paper proposes an implementation of a constrained analytic center cutting plane method to solve nonlinear multicommodity
flow problems. The new approach exploits the property that the objective of the Lagrangian dual problem has a smooth component
with second order derivatives readily available in closed form. The cutting planes issued from the nonsmooth component and
the epigraph set of the smooth component form a localization set that is endowed with a self-concordant augmented barrier.
Our implementation uses an approximate analytic center associated with that barrier to query the oracle of the nonsmooth component.
The paper also proposes an approximation scheme for the original objective. An active set strategy can be applied to the transformed
problem: it reduces the dimension of the dual space and accelerates computations. The new approach solves huge instances with
high accuracy. The method is compared to alternative approaches proposed in the literature.
An erratum to this article can be found at 相似文献
10.
A. L. Soyster 《Journal of Optimization Theory and Applications》1974,13(4):484-489
For certain types of mathematical programming problems, a related dual problem can be constructed in which the objective value of the dual problem is equal to the objective function of the given problem. If these two problems do not have equal values, a duality gap is said to exist. No such gap exists for pairs of ordinary dual linear programming problems, but this is not the case for linear programming problems in which the nonnegativity conditionx ? 0 is replaced by the condition thatx lies in a certain convex setK. Duffin (Ref. 1) has shown that, whenK is a cone and a certain interiority condition is fulfilled, there will be no duality gap. In this note, we show that no duality gap exists when the interiority condition is satisfied andK is an arbitrary closed convex set inR n . 相似文献
11.
In this paper, we examine duality for fractional programming problems in the face of data uncertainty within the framework
of robust optimization. We establish strong duality between the robust counterpart of an uncertain convex–concave fractional
program and the optimistic counterpart of its conventional Wolfe dual program with uncertain parameters. For linear fractional
programming problems with constraint-wise interval uncertainty, we show that the dual of the robust counterpart is the optimistic
counterpart in the sense that they are equivalent. Our results show that a worst-case solution of an uncertain fractional
program (i.e., a solution of its robust counterpart) can be obtained by solving a single deterministic dual program. In the
case of a linear fractional programming problem with interval uncertainty, such solutions can be found by solving a simple
linear program. 相似文献
12.
This paper develops a wholly linear formulation of the posynomial geometric programming problem. It is shown that the primal geometric programming problem is equivalent to a semi-infinite linear program, and the dual problem is equivalent to a generalized linear program. Furthermore, the duality results that are available for the traditionally defined primal-dual pair are readily obtained from the duality theory for semi-infinite linear programs. It is also shown that two efficient algorithms (one primal based and the other dual based) for geometric programming actually operate on the semi-infinite linear program and its dual. 相似文献
13.
R. J. Duffin 《Mathematical Programming》1973,4(1):125-143
The theme of this paper is the application of linear analysis to simplify and extend convex analysis. The central problem treated is the standard convex program — minimize a convex function subject to inequality constraints on other convex functions. The present approach uses the support planes of the constraint region to transform the convex program into an equivalent linear program. Then the duality theory of infinite linear programming shows how to construct a new dual program of bilinear type. When this dual program is transformed back into the convex function formulation it concerns the minimax of an unconstrained Lagrange function. This result is somewhat similar to the Kuhn—Tucker theorem. However, no constraint qualifications are needed and yet perfect duality maintains between the primal and dual programs.Work prepared under Research Grant DA-AROD-31-124-71-G17, Army Research Office (Durham). 相似文献
14.
Recently, linear programming problems with symmetric fuzzy numbers (LPSFN) have considered by some authors and have proposed
a new method for solving these problems without converting to the classical linear programming problem, where the cost coefficients
are symmetric fuzzy numbers (see in [4]). Here we extend their results and first prove the optimality theorem and then define
the dual problem of LPSFN problem. Furthermore, we give some duality results as a natural extensions of duality results for
linear programming problems with crisp data. 相似文献
15.
A Dinkelbach-type algorithm is proposed in this paper to solve a class of continuous-time linear fractional programming problems.
We shall transform this original problem into a continuous-time non-fractional programming problem, which unfortunately happens
to be a continuous-time nonlinear programming problem. In order to tackle this nonlinear problem, we propose the auxiliary
problem that will be formulated as parametric continuous-time linear programming problem. We also introduce a dual problem
of this parametric continuous-time linear programming problem in which the weak duality theorem also holds true. We introduce
the discrete approximation method to solve the primal and dual pair of parametric continuous-time linear programming problems
by using the recurrence method. Finally, we provide two numerical examples to demonstrate the usefulness of this practical
algorithm. 相似文献
16.
A numerical algorithm based on parametric approach is proposed in this paper to solve a class of continuous-time linear fractional max-min programming problems. We shall transform this original problem into a continuous-time non-fractional programming problem, which unfortunately happens to be a continuous-time nonlinear programming problem. In order to tackle this nonlinear problem, we propose the auxiliary problem that will be formulated as a parametric continuous-time linear programming problem. We also introduce a dual problem of this parametric continuous-time linear programming problem in which the weak duality theorem also holds true. We introduce the discrete approximation method to solve the primal and dual pair of parametric continuous-time linear programming problems by using the recurrence method. Finally, we provide two numerical examples to demonstrate the usefulness of this algorithm. 相似文献
17.
We survey some recent developments in duality theory with the idea of explaining and unifying certain basic duality results in both nonlinear and integer programming. The idea of replacing dual variables (prices) by price functions, suggested by Everett and developed by Gould, is coupled with an appropriate dual problem with the consequence that many of the results resemble those used in linear programming. The dual problem adopted has a (traditional) economic interpretation and dual feasibility then provides a simple alternative to concepts such as conjugate functions or subdifferentials used in the study of optimality. In addition we attempt to make precise the relationship between primal, dual and saddlepoint results in both the traditional Lagrangean and the more general duality theories and to see the implications of passing from prices to price functions. Finally, and perhaps surprisingly, it appears that all the standard algorithms terminate by constructing primal and dual feasible solutions of equal value, i.e., by satisfying generalised optimality conditions. 相似文献
18.
In this paper, we present a duality theory for fractional programming problems in the face of data uncertainty via robust optimization. By employing conjugate analysis, we establish robust strong duality for an uncertain fractional programming problem and its uncertain Wolfe dual programming problem by showing strong duality between the deterministic counterparts: robust counterpart of the primal model and the optimistic counterpart of its dual problem. We show that our results encompass as special cases some programming problems considered in the recent literature. Moreover, we also show that robust strong duality always holds for linear fractional programming problems under scenario data uncertainty or constraint-wise interval uncertainty, and that the optimistic counterpart of the dual is tractable computationally. 相似文献
19.
Donald C. Aucamp 《Applied Mathematical Modelling》1984,8(4):238-242
Careful inspection of the geometry of the primal linear programming problem reveals the Kuhn-Tucker conditions as well as the dual. Many of the well-known special cases in duality are also seen from the geometry, as well as the complementary slackness conditions and shadow prices. The latter at demonstrated to differ from the dual variables in situations involving primal degeneracy. Virtually all the special relationships between linear programming and duality theory can be seen from the geometry of the primal and an elementary application of vector analysis. 相似文献
20.
Several algorithms already exist for solving the uncapacitated facility location problem. The most efficient are based upon the solution of the strong linear programming relaxation. The dual of this relaxation has a condensed form which consists of minimizing a certain piecewise linear convex function. This paper presents a new method for solving the uncapacitated facility location problem based upon the exact solution of the condensed dual via orthogonal projections. The amount of work per iteration is of the same order as that of a simplex iteration for a linear program inm variables and constraints, wherem is the number of clients. For comparison, the underlying linear programming dual hasmn + m + n variables andmn +n constraints, wheren is the number of potential locations for the facilities. The method is flexible as it can handle side constraints. In particular, when there is a duality gap, the linear programming formulation can be strengthened by adding cuts. Numerical results for some classical test problems are included. 相似文献