共查询到20条相似文献,搜索用时 46 毫秒
1.
Gauss—Seidel type relaxation techniques are applied in the context of strictly convex pure networks with separable cost functions.
The algorithm is an extension of the Bertsekas—Tseng approach for solving the linear network problem and its dual as a pair
of monotropic programming problems. The method is extended to cover the class of generalized network problems. Alternative
internal tactics for the dual problem are examined. Computational experiments —aimed at the improved efficiency of the algorithm
— are presented.
This research was supported in part by National Science Foundation Grant No. DCR-8401098-A0l. 相似文献
2.
M. H. Schneider 《Annals of Operations Research》1986,5(1-4):439-462
In this paper, an algorithm is presented for the transshipment problem that is an adaption of the method used by Jones, Saigal,
and Schneider for solving singlecommodity, spatial-equilibrium problems. The approach uses a variable-dimension strategy in
which a sequence of subproblems is formed by solving the problem ‘one-node-at-a-time’. The algorithm is tested on uncapacitated
transportation problems. Although the computational results are not directly comparable to other methods (since the algorithm
is implemented in C under UNIX), the results show that the method is very effective and may be competitive with the best available
algorithms for linear network problems.
This research was supported, in part, by grant number ECS-8504195 from the National Science Foundation. 相似文献
3.
Gauss—Seidel type relaxation techniques are applied in the context of strictly convex pure networks with separable cost functions. The algorithm is an extension of the Bertsekas—Tseng approach for solving the linear network problem and its dual as a pair of monotropic programming problems. The method is extended to cover the class of generalized network problems. Alternative internal tactics for the dual problem are examined. Computational experiments — aimed at the improved efficiency of the algorithm — are presented.This research was supported in part by National Science Foundation Grant No. DCR-8401098-A01. 相似文献
4.
O. L. Mangasarian M. E. Thompson 《Journal of Optimization Theory and Applications》2006,131(3):315-325
A highly accurate algorithm, based on support vector machines formulated as linear programs (Refs. 1–2), is proposed here as a completely unconstrained minimization problem (Ref. 3). Combined with a chunking procedure (Ref. 4), this approach, which requires nothing more complex than a linear equation solver, leads to a simple and accurate method for classifying million-point datasets. Because a 1-norm support vector machine underlies the proposed approach, the method suppresses input space features as well. A state-of-the-art linear programming package (CPLEX, Ref. 5) fails to solve problems handled by the proposed algorithm.This research was supported by National Science Foundation Grants CCR-0138308 and IIS-0511905. 相似文献
5.
E. Mijangos 《Journal of Optimization Theory and Applications》2006,128(1):167-190
The minimization of nonlinearly constrained network flow problems can be performed by using approximate subgradient methods.
The idea is to solve this kind of problem by means of primal-dual methods, given that the minimization of nonlinear network
flow problems can be done efficiently exploiting the network structure. In this work, it is proposed to solve the dual problem
by using ε-subgradient methods, as the dual function is estimated by minimizing approximately a Lagrangian function, which
includes the side constraints (nonnetwork constraints) and is subject only to the network constraints. Some well-known subgradient
methods are modified in order to be used as ε-subgradient methods and the convergence properties of these new methods are
analyzed. Numerical results appear very promising and effective for this kind of problems
This research was partially supported by Grant MCYT DPI 2002-03330. 相似文献
6.
Horst W. Hamacher 《Annals of Operations Research》1995,57(1):65-72
It is shown that the problem of finding theK best solutions of a linear integer network flow problem can be solved by a polynomial time algorithm. This algorithm can be used in order to solve a multiple-criteria network flow problem which minimizes the maximum ofQ objectives.Partially supported by grants of the Deutsche Forschungsgemeinschaft and the HC&M programme of the European Union under ERBCHRXCT 930087. 相似文献
7.
This paper is concerned with classical concave cost multi-echelon production/inventory control problems studied by W. Zangwill
and others. It is well known that the problem with m production steps and n time periods can be solved by a dynamic programming algorithm in O(n
4
m) steps, which is considered as the fastest algorithm for solving this class of problems. In this paper, we will show that
an alternative 0–1 integer programming approach can solve the same problem much faster particularly when n is large and the number of 0–1 integer variables is relatively few. This class of problems include, among others problem
with set-up cost function and piecewise linear cost function with fewer linear pieces. The new approach can solve problems
with mixed concave/convex cost functions, which cannot be solved by dynamic programming algorithms. 相似文献
8.
O. Briant C. Lemaréchal Ph. Meurdesoif S. Michel N. Perrot F. Vanderbeck 《Mathematical Programming》2008,113(2):299-344
When a column generation approach is applied to decomposable mixed integer programming problems, it is standard to formulate
and solve the master problem as a linear program. Seen in the dual space, this results in the algorithm known in the nonlinear
programming community as the cutting-plane algorithm of Kelley and Cheney-Goldstein. However, more stable methods with better
theoretical convergence rates are known and have been used as alternatives to this standard. One of them is the bundle method;
our aim is to illustrate its differences with Kelley’s method. In the process we review alternative stabilization techniques
used in column generation, comparing them from both primal and dual points of view. Numerical comparisons are presented for
five applications: cutting stock (which includes bin packing), vertex coloring, capacitated vehicle routing, multi-item lot
sizing, and traveling salesman. We also give a sketchy comparison with the volume algorithm.
This research has been supported by Inria New Investigation Grant “Convex Optimization and Dantzig-Wolfe Decomposition”. 相似文献
9.
A new dual problem for convex generalized fractional programs with no duality gap is presented and it is shown how this dual
problem can be efficiently solved using a parametric approach. The resulting algorithm can be seen as “dual” to the Dinkelbach-type
algorithm for generalized fractional programs since it approximates the optimal objective value of the dual (primal) problem
from below. Convergence results for this algorithm are derived and an easy condition to achieve superlinear convergence is
also established. Moreover, under some additional assumptions the algorithm also recovers at the same time an optimal solution
of the primal problem. We also consider a variant of this new algorithm, based on scaling the “dual” parametric function.
The numerical results, in case of quadratic-linear ratios and linear constraints, show that the performance of the new algorithm
and its scaled version is superior to that of the Dinkelbach-type algorithms. From the computational results it also appears
that contrary to the primal approach, the “dual” approach is less influenced by scaling.
This research was carried out at the Econometric Institute, Erasmus University, Rotterdam, the Netherlands and was supported
by J.N.I.C.T. (Portugal) under contract BD/707/90-RM. 相似文献
10.
R. Zenklusen 《Discrete Applied Mathematics》2010,158(13):1441-1455
The network flow interdiction problem asks to reduce the value of a maximum flow in a given network as much as possible by removing arcs and vertices of the network constrained to a fixed budget. Although the network flow interdiction problem is strongly NP-complete on general networks, pseudo-polynomial algorithms were found for planar networks with a single source and a single sink and without the possibility to remove vertices. In this work, we introduce pseudo-polynomial algorithms that overcome various restrictions of previous methods. In particular, we propose a planarity-preserving transformation that enables incorporation of vertex removals and vertex capacities in pseudo-polynomial interdiction algorithms for planar graphs. Additionally, a new approach is introduced that allows us to determine in pseudo-polynomial time the minimum interdiction budget needed to remove arcs and vertices of a given network such that the demands of the sink node cannot be completely satisfied anymore. The algorithm works on planar networks with multiple sources and sinks satisfying that the sum of the supplies at the sources equals the sum of the demands at the sinks. A simple extension of the proposed method allows us to broaden its applicability to solve network flow interdiction problems on planar networks with a single source and sink having no restrictions on the demand and supply. The proposed method can therefore solve a wider class of flow interdiction problems in pseudo-polynomial time than previous pseudo-polynomial algorithms and is the first pseudo-polynomial algorithm that can solve non-trivial planar flow interdiction problems with multiple sources and sinks. Furthermore, we show that the k-densest subgraph problem on planar graphs can be reduced to a network flow interdiction problem on a planar graph with multiple sources and sinks and polynomially bounded input numbers. 相似文献
11.
A characteristic feature of the primal network simplex algorithm (NSA) is that it usually makes a large number of degenerate iterations. Though cycling and even stalling can be avoided by recently introduced pivot rules for NSA, the practical efficiency of these rules is not known yet. For the case when the simplex algorithm is used to solve the continuous linear programming (LP) problem there exists a practical anti-cycling procedure that proved to be efficient. It is based on an expanding relaxation of the individual bound on the variables. In this paper we discuss the adaptation of this method to NSA, taking advantage of the special integer nature of network problems. We also give an account of our experience with these ideas as they are experimentally implemented in the MINET network LP solver. Reductions of CPU time have been achieved on a smaller set of specially structured real-life problems.This research was supported in part by Hungarian Research Fund OTKA 2587, and by DAAD 314 108 060 0 while the author was at Universität Heidelberg, Germany, October, 1990. 相似文献
12.
This paper studies an inventory routing problem (IRP) with split delivery and vehicle fleet size constraint. Due to the complexity of the IRP, it is very difficult to develop an exact algorithm that can solve large scale problems in a reasonable computation time. As an alternative, an approximate approach that can quickly and near-optimally solve the problem is developed based on an approximate model of the problem and Lagrangian relaxation. In the approach, the model is solved by using a Lagrangian relaxation method in which the relaxed problem is decomposed into an inventory problem and a routing problem that are solved by a linear programming algorithm and a minimum cost flow algorithm, respectively, and the dual problem is solved by using the surrogate subgradient method. The solution of the model obtained by the Lagrangian relaxation method is used to construct a near-optimal solution of the IRP by solving a series of assignment problems. Numerical experiments show that the proposed hybrid approach can find a high quality near-optimal solution for the IRP with up to 200 customers in a reasonable computation time. 相似文献
13.
M. H. Schneider 《Annals of Operations Research》1986,5(2):439-462
In this paper, an algorithm is presented for the transshipment problem that is an adaption of the method used by Jones, Saigal, and Schneider for solving single-commodity, spatial-equilibrium problems. The approach uses a variable-dimension strategy in which a sequence of subproblems is formed by solving the problem one-node-at-a-time. The algorithm is tested on uncapacitated transportation problems. Although the computational results are not directly comparable to other methods (since the algorithm is implemented in C under UNIX), the results show that the method is very effective and may e competitive with the best available algorithms for linear network problems.This research was supported, in part, by grant number ECS-85 04 195 from the National Science Foundation. 相似文献
14.
We approximate the objective function of the fixed charge network flow problem (FCNF) by a piecewise linear one, and construct
a concave piecewise linear network flow problem (CPLNF). A proper choice of parameters in the CPLNF problem guarantees the
equivalence between those two problems. We propose a heuristic algorithm for solving the FCNF problem, which requires solving
a sequence of CPLNF problems. The algorithm employs the dynamic cost updating procedure (DCUP) to find a solution to the CPLNF
problems. Preliminary numerical experiments show the effectiveness of the proposed algorithm. In particular, it provides a
better solution than the dynamic slope scaling procedure in less CPU time.
Research was partially supported by NSF and Air Force grants. 相似文献
15.
I. Bykadorov A. Ellero S. Funari E. Moretti 《Journal of Optimization Theory and Applications》2009,142(1):55-66
We consider optimal control problems with functional given by the ratio of two integrals (fractional optimal control problems). In particular, we focus on a special case with affine integrands and linear dynamics with respect to state and control.
Since the standard optimal control theory cannot be used directly to solve a problem of this kind, we apply Dinkelbach’s approach
to linearize it. Indeed, the fractional optimal control problem can be transformed into an equivalent monoparametric family
{Pq} of linear optimal control problems. The special structure of the class of problems considered allows solving the fractional
problem either explicitly or requiring straightforward classical numerical techniques to solve a single equation. An application
to advertising efficiency maximization is presented.
This work was partially supported by the Università Ca’ Foscari, Venezia, Italy, the MIUR (PRIN cofinancing 2005), the Council
for Grants (under RF President) and State Aid to Fundamental Science Schools (Grant NSh-4113.2008.6).
We thank Angelo Miele, Panos Pardalos and the anonymous referees for comments and suggestions. 相似文献
16.
Malcolm C. Pullan 《Mathematical Programming》2002,93(3):415-451
Separated continuous linear programs (SCLP) are a class of continuous linear programs which, among other things, can serve
as a useful model for dynamic network problems where storage is permitted at the nodes. Recent work on SCLP has produced a
detailed duality theory, conditions under which an optimal solution exists with a finite number of breakpoints, a purification
algorithm, as well as a convergent algorithm for solving SCLP under certain assumptions on the problem data. This paper combines
much of this work to develop a possible approach for solving a wider range of SCLP problems, namely those with fairly general
costs. The techniques required to implement the algorithm are no more than standard (finite-dimensional) linear programming
and line searching, and the resulting algorithm is simplex-like in nature. We conclude the paper with the numerical results
obtained by using a simple implementation of the algorithm to solve a small problem.
Received: May 1994 / Accepted: March 2002?Published online June 25, 2002 相似文献
17.
Robust discrete optimization and network flows 总被引:17,自引:0,他引:17
We propose an approach to address data uncertainty for discrete optimization and network flow problems that allows controlling the degree of conservatism of the solution, and is computationally tractable both practically and theoretically. In particular, when both the cost coefficients and the data in the constraints of an integer programming problem are subject to uncertainty, we propose a robust integer programming problem of moderately larger size that allows controlling the degree of conservatism of the solution in terms of probabilistic bounds on constraint violation. When only the cost coefficients are subject to uncertainty and the problem is a 0–1 discrete optimization problem on n variables, then we solve the robust counterpart by solving at most n+1 instances of the original problem. Thus, the robust counterpart of a polynomially solvable 0–1 discrete optimization problem remains polynomially solvable. In particular, robust matching, spanning tree, shortest path, matroid intersection, etc. are polynomially solvable. We also show that the robust counterpart of an NP-hard -approximable 0–1 discrete optimization problem, remains -approximable. Finally, we propose an algorithm for robust network flows that solves the robust counterpart by solving a polynomial number of nominal minimum cost flow problems in a modified network.
The research of the author was partially supported by the Singapore-MIT alliance.The research of the author is supported by a graduate scholarship from the National University of Singapore.Mathematics Subject Classification (2000): 90C10, 90C15 相似文献
18.
In this paper, an approach is proposed for solving a nonlinear-quadratic optimal regulator problem with linear static state feedback and infinite planning horizon. For such a problem, approximate problems are introduced and considered, which are obtained by combining a finite-horizon problem with an infinite-horizon linear problem in a certain way. A gradient-flow based algorithm is derived for these approximate problems. It is shown that an optimal solution to the original problem can be found as the limit of a sequence of solutions to the approximate problems. Several important properties are obtained. For illustration, two numerical examples are presented.This project was partially supported by a research grant from the Australian Research Council. 相似文献
19.
Satoru Hashizume Masao Fukushima Naoki Katoh Toshihide Ibaraki 《Mathematical Programming》1987,37(3):255-267
We are concerned with a combinatorial optimization problem which has the ratio of two linear functions as the objective function.
This type of problems can be solved by an algorithm that uses an auxiliary problem with a parametrized linear objective function.
Because of its combinatorial nature, however, it is often difficult to solve the auxiliary problem exactly. In this paper,
we propose an algorithm which assumes that the auxiliary problems are solved only approximately, and prove that it gives an
approximate solution to the original problem, of which the accuracy is at least as good as that of approximate solutions to
the auxiliary problems. It is also shown that the time complexity is bounded by the square of the computation time of the
approximate algorithm for the auxiliary problem. As an example of the proposed algorithm, we present a fully polynomial time
approximation scheme for the fractional 0–1 knapsack problem. 相似文献
20.
《European Journal of Operational Research》2005,161(3):618-635
Many nonlinear network flow problems (in addition to the balance constraints in the nodes and capacity constraints on the arc flows) have nonlinear side constraints, which specify a flow relationship between several of the arcs in the network flow model. The short-term hydrothermal coordination of electric power generation is an example of this type. In this work we solve this kind of problem using an approach in which the efficiency of the well-known techniques for network flow can be preserved. It lies in relaxing the side constraints in an augmented Lagrangian function, and minimizing a sequence of these functions subject only to the network constraints for different estimates of the Lagrange multipliers of the side constraints. This method gives rise to an algorithm, which combines first- and superlinear-order multiplier methods to estimate these multipliers. When the number of free variables is very high we can obtain a superlinear-order estimate by means of the limited memory BFGS method fitted to our problem. An extensive computational comparison with other methods has been performed. The numerical results reported indicate that the algorithm described may be employed advantageously to solve large-scale network flow problems with nonlinear side constraints. 相似文献