共查询到20条相似文献,搜索用时 15 毫秒
1.
In this paper we consider a class of semi-infinite transportation problems. We develop an algorithm for this class of semi-infinite transportation problems. The algorithm is a primal dual method which is a generalization of the classical algorithm for finite transportation problems. The most important aspect of our paper is that we can prove the convergence result for the algorithm. Finally, we implement some examples to illustrate our algorithm. 相似文献
2.
Balinski uses his signature method for the proof of the Hirsch-conjecture for dual transportation polyhedra to obtain an efficient
algorithm for the assignment problem. We will show how to extend this method to other primal transportation problems, including
transportation problems with unit demands. We then prove that Balinski's assignment algorithm is equivalent, cycle by cycle,
to that of Hung and Rom. We demonstrate that, under some assumptions for our probability model, a modification of the latter
algorithm has an average complexity of O(n
2logn) and present some computational results confirming this. We also present results that indicate that this modification compares
favorably with Balinski's algorithm and other codes.
Research of both authors supported, in part, by grants of the Alexander von Humboldt-Stiftung.
Supported, in part, by NSF grant DMS-8504050. 相似文献
3.
A. Ouorou 《Computational Optimization and Applications》2000,15(2):125-143
This paper presents a new primal-dual algorithm for solving a class of monotropic programming problems. This class involves many problems arising in a number of important applications in telecommunications networks, transportation and water distribution. The proposed algorithm is inspired by Kallio and Ruszczyski approach for linear programming [M. Kallio and A. Ruszczyski, WP-94-15, IIASA, 1994]. The problem is replaced by a game using two different augmented Lagrangian functions defined for the primal and the dual problems. It is then possible to develop a block-wise Gauss-Seidel method to reach an equilibrium of the game with alternating steps made in each component of the primal and dual variables. Finally, we show how this algorithm may be applied to some important problems in Network Optimization such as the minimum quadratic cost single flow problems and convex multicommodity flow problems. 相似文献
4.
This paper surveys a new and comprehensive class of algorithms for solving the classical linear network flow problem and its various special cases such as shortest path, max-flow, assignment, transportation, and transhipment problems. The prototype method, from which the other algorithms can be derived, is the auction algorithm for the assignment problem. This is an intuitive method that operates like a rel auction where persons compete for objects by raising their prices through competitive bidding; the prices can be viewed as dual variables. Conceptually, auction algorithms represent a significant departure from the cost improvement idea that underlies primal simplex and dual ascent methods; at any one iteration, they may deteriorate both the primal and the dual cost. Auction algorithms perform very well for several important types of problems, both in theory and in practice, and they are also well suited for parallel computation. 相似文献
5.
A primal transportation algorithm is devised via post-optimization on the costs of a modified problem. The procedure involves altering the costs corresponding to the basic cells of the initial (primal feasible) solution so that it is dual feasible as well. The altered costs are then successively restored to their true values with appropriate changes in the optimal solution by the application of cell or area cost operators discussed elsewhere. The cell cost operator algorithm converges to optimum within (2T – 1) steps for primal nondegenerate transportation problems and [(2T + 1) min (m, n)] – 1 steps for primal degenerate transportation problems, whereT is the sum of the (integer) warehouse availabilities (also the sum of the (integer) market requirements) andm andn denote the number of warehouses and markets respectively. For the area cost operator algorithm the corresponding bounds on the number of steps areT and (T + 1) min (m, n) respectively.This report was prepared as part of the activities of the Management Sciences Research Group, Carnegie—Mellon University, under Contract N00014-67-A-0314-0007 NR 047-048 with the U.S. Office of Naval Research. 相似文献
6.
Application of the alternating direction method of multipliers to separable convex programming problems 总被引:3,自引:0,他引:3
Masao Fukushima 《Computational Optimization and Applications》1992,1(1):93-111
This paper presents a decomposition algorithm for solving convex programming problems with separable structure. The algorithm is obtained through application of the alternating direction method of multipliers to the dual of the convex programming problem to be solved. In particular, the algorithm reduces to the ordinary method of multipliers when the problem is regarded as nonseparable. Under the assumption that both primal and dual problems have at least one solution and the solution set of the primal problem is bounded, global convergence of the algorithm is established. 相似文献
7.
线性规划的最钝角CRISS-CROSS算法 总被引:1,自引:0,他引:1
1 引言 考虑如下标准线性规划问题 minimize c~Tx (1) subject to Ax=b, x≥0 其中A∈R~(m×n) (m相似文献
8.
《European Journal of Operational Research》1999,113(3):544-559
Facility location problems are often encountered in many areas such as distribution, transportation and telecommunication. We describe a new solution approach for the capacitated facility location problem in which each customer is served by a single facility. An important class of heuristic solution methods for these problems are Lagrangian heuristics which have been shown to produce high quality solutions and at the same time be quite robust. A primal heuristic, based on a repeated matching algorithm which essentially solves a series of matching problems until certain convergence criteria are satisfied, is incorporated into the Lagrangian heuristic. Finally, a branch-and-bound method, based on the Lagrangian heuristic is developed, and compared computationally to the commercial code CPLEX. The computational results indicate that the proposed method is very efficient. 相似文献
9.
In the conic optimization problems, it is well-known that a positive duality gap may occur, and that solving such a problem is numerically difficult or unstable. For such a case, we propose a facial reduction algorithm to find a primal–dual pair of conic optimization problems having the zero duality gap and the optimal value equal to one of the original primal or dual problems. The conic expansion approach is also known as a method to find such a primal–dual pair, and in this paper we clarify the relationship between our facial reduction algorithm and the conic expansion approach. Our analysis shows that, although they can be regarded as dual to each other, our facial reduction algorithm has ability to produce a finer sequence of faces of the cone including the feasible region. A simple proof of the convergence of our facial reduction algorithm for the conic optimization is presented. We also observe that our facial reduction algorithm has a practical impact by showing numerical experiments for graph partition problems; our facial reduction algorithm in fact enhances the numerical stability in those problems. 相似文献
10.
R. J. Vanderbei 《Mathematical Programming》1989,43(1-3):31-44
The affine-scaling modification of Karmarkar's algorithm is extended to solve problems with free variables. This extended primal algorithm is used to prove two important results. First the geometrically elegant feasibility algorithm proposed by Chandru and Kochar is the same algorithm as the one obtained by appending a single column of residuals to the constraint matrix. Second the dual algorithm as first described by Adler et al., is the same as the extended primal algorithm applied to the dual. 相似文献
11.
In this paper, we propose a primal majorized semismooth Newton-CG augmented Lagrangian method for large-scale linearly constrained convex programming problems, especially for some difficult problems. The basic idea of this method is to apply the majorized semismooth Newton-CG augmented Lagrangian method to the primal convex problem. And we take two special nonlinear semidefinite programming problems as examples to illustrate the algorithm. Furthermore, we establish the global convergence and the iteration complexity of the algorithm. Numerical experiments demonstrate that our method works very well for the testing problems, especially for many ill-conditioned ones. 相似文献
12.
Optimization problems with network constraints arise in several instances in engineering, management, statistical and economic applications. The (usually) large size of such problems motivated research in designing efficient algorithms and software for this problem class. The introduction of parallelism in the design of computer systems adds a new element of complexity to the field. This paper describes the implementation of a distributed relaxation algorithm for strictly convex network problems on a massively parallel computer. A Connection Machine CM-1 configured with 16,384 processing elements serves as the testbed of the implementation. We report computational results with a series of stick percolation and quadratic transportation problems. The algorithm is compared with an implementation of the primal truncated Newton on an IBM 3081-D mainframe, an Alliant FX/8 shared memory vector multiprocessor and the IBM 3090-600 vector supercomputer. One of the larger test problems with approximately 2500 nodes and 8000 arcs requires 1.5 minutes of CPU time on the vector supercomputer. The same problem is solved using relaxation on the CM-1 in less that a second. 相似文献
13.
14.
《European Journal of Operational Research》1997,101(3):519-531
An important operational problem arises during the transportation and delivery of several products, which cannot be mixed, in the same vehicle at regular intervals. The vehicle has compartments to keep the products separately. Therefore, a scheme of allocation of compartments which we call vehicle loading problem to maximize the efficiency of the system while the demands for the products at the destination(s) are satisfied. A mixed binary model is developed for this multi-product loading problem. The solution method is based on simultaneously exploring the primal and dual structures derived from the Lagrangian relaxation. Subset sum problems are obtained as subproblems to the partial Lagrangian. An algorithm is developed and its convergence is proved. The efficiency of the method is demonstrated by running, randomly chosen test problems. An initial solution finding method is also developed. 相似文献
15.
An efficient and numerically stable dual algorithm for positive definite quadratic programming is described which takes advantage
of the fact that the unconstrained minimum of the objective function can be used as a starting point. Its implementation utilizes
the Cholesky and QR factorizations and procedures for updating them. The performance of the dual algorithm is compared against
that of primal algorithms when used to solve randomly generated test problems and quadratic programs generated in the course
of solving nonlinear programming problems by a successive quadratic programming code (the principal motivation for the development
of the algorithm). These computational results indicate that the dual algorithm is superior to primal algorithms when a primal
feasible point is not readily available. The algorithm is also compared theoretically to the modified-simplex type dual methods
of Lemke and Van de Panne and Whinston and it is illustrated by a numerical example.
This research was supported in part by the Army Research Office under Grant No. DAAG 29-77-G-0114 and in part by the National
Science Foundation under Grant No. MCS-6006065. 相似文献
16.
In this paper we list several useful properties of central points in linear programming problems. We study the logarithmic barrier function, the analytic center and the central path, relating the proximity measures and scaled Euclidean distances defined for the primal and primal–dual problems. We study the Newton centering steps, and show how large the short steps used in path following algorithms can actually be, and what variation can be ensured for the barrier function in each iteration of such methods. We relate the primal and primal–dual Newton centering steps and propose a primal-only path following algorithm for linear programming. 相似文献
17.
Magnus Önnheim Emil Gustavsson Ann-Brith Strömberg Michael Patriksson Torbjörn Larsson 《Mathematical Programming》2017,163(1-2):57-84
Consider the utilization of a Lagrangian dual method which is convergent for consistent convex optimization problems. When it is used to solve an infeasible optimization problem, its inconsistency will then manifest itself through the divergence of the sequence of dual iterates. Will then the sequence of primal subproblem solutions still yield relevant information regarding the primal program? We answer this question in the affirmative for a convex program and an associated subgradient algorithm for its Lagrange dual. We show that the primal–dual pair of programs corresponding to an associated homogeneous dual function is in turn associated with a saddle-point problem, in which—in the inconsistent case—the primal part amounts to finding a solution in the primal space such that the Euclidean norm of the infeasibility in the relaxed constraints is minimized; the dual part amounts to identifying a feasible steepest ascent direction for the Lagrangian dual function. We present convergence results for a conditional \(\varepsilon \)-subgradient optimization algorithm applied to the Lagrangian dual problem, and the construction of an ergodic sequence of primal subproblem solutions; this composite algorithm yields convergence of the primal–dual sequence to the set of saddle-points of the associated homogeneous Lagrangian function; for linear programs, convergence to the subset in which the primal objective is at minimum is also achieved. 相似文献
18.
Sparse covariance selection problems can be formulated as log-determinant (log-det) semidefinite programming (SDP) problems with large numbers of linear constraints. Standard primal–dual interior-point methods that are based on solving the Schur complement equation would encounter severe computational bottlenecks if they are applied to solve these SDPs. In this paper, we consider a customized inexact primal–dual path-following interior-point algorithm for solving large scale log-det SDP problems arising from sparse covariance selection problems. Our inexact algorithm solves the large and ill-conditioned linear system of equations in each iteration by a preconditioned iterative solver. By exploiting the structures in sparse covariance selection problems, we are able to design highly effective preconditioners to efficiently solve the large and ill-conditioned linear systems. Numerical experiments on both synthetic and real covariance selection problems show that our algorithm is highly efficient and outperforms other existing algorithms. 相似文献
19.
This paper presents a primal-dual conjugate subgradient algorithm for solving convex programming problems. The motivation, however, is to employ it for solving specially structured or decomposable linear programming problems. The algorithm coordinates a primal penalty function and a Lagrangian dual function, in order to generate a (geometrically) convergent sequence of primal and dual iterates. Several refinements are discussed to improve the performance of the algorithm. These are tested on some network problems, with side constraints and variables, faced by the Freight Equipment Management Program of the Association of American Railroads, and suggestions are made for implementation.This research was supported by the Association of American Railroads. 相似文献
20.
Satoru Ibaraki Masao Fukushima Toshihide Ibaraki 《Computational Optimization and Applications》1992,1(2):207-226
A primal-dual version of the proximal point algorithm is developed for linearly constrained convex programming problems. The algorithm is an iterative method to find a saddle point of the Lagrangian of the problem. At each iteration of the algorithm, we compute an approximate saddle point of the Lagrangian function augmented by quadratic proximal terms of both primal and dual variables. Specifically, we first minimize the function with respect to the primal variables and then approximately maximize the resulting function of the dual variables. The merit of this approach exists in the fact that the latter function is differentiable and the maximization of this function is subject to no constraints. We discuss convergence properties of the algorithm and report some numerical results for network flow problems with separable quadratic costs. 相似文献