We propose a 'build-down' scheme for Karmarkar's algorithm and the simplex method for linearprogramming. The scheme starts with an optimal basis 'candidate' set E including all columns of the cons...
详细信息
We propose a 'build-down' scheme for Karmarkar's algorithm and the simplex method for linearprogramming. The scheme starts with an optimal basis 'candidate' set E including all columns of the constraint matrix, then constructs a dual ellipsoid containing all optimal dual solutions. A pricing rule is developed for checking whether or not a dual hyperplane corresponding to a column intersects the containing ellipsoid. If the dual hyperplane has no intersection with the ellipsoid, its corresponding column will not appear in any of the optimal bases, and can be eliminated from E. As these methods iterate, E is eventually built-down to a set that contains only the optimal basic columns.
Although numerous exact algorithms have been proposed so far for the linear assignment problem, they are not necessarily satisfactory from the viewpoint of computation time when considered for application to practical...
详细信息
Although numerous exact algorithms have been proposed so far for the linear assignment problem, they are not necessarily satisfactory from the viewpoint of computation time when considered for application to practical large-scale problems. This paper proposes a new algorithm which can reduce the expected computation time needed to find an exact solution for the linear assignment problem by limiting the search space as much as possible within the scope in which no optimal solution is missed. Here, first, an equation is derived to give an upper bound of the search space so as not to miss an optimal solution in the process of finding an alternating path. Next, data structure is described for developing an operation to limit the search space based on this equation and an assignment algorithm is derived.
We give a short proof of the finiteness of Murty's principal pivoting algorithm for solving the linear complementarity problem y = Mz + q, yT z = 0, y ≥ 0, z ≥ 0 with P-matrix M.
We give a short proof of the finiteness of Murty's principal pivoting algorithm for solving the linear complementarity problem y = Mz + q, yT z = 0, y ≥ 0, z ≥ 0 with P-matrix M.
In this paper, we first give a counterexample showing the falsehood of the convergence theorem of Choo and Kim. We then prove a convergence theorem for their algorithm.
In this paper, we first give a counterexample showing the falsehood of the convergence theorem of Choo and Kim. We then prove a convergence theorem for their algorithm.
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 linearprogramming p...
详细信息
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 linearprogramming 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.
Version 5.1 of MINOS was used to analyze a set of linearprogramming test problems, which were run with different sets of options for scaling and partial pricing to illustrate the effects of these options on the perfo...
详细信息
Version 5.1 of MINOS was used to analyze a set of linearprogramming test problems, which were run with different sets of options for scaling and partial pricing to illustrate the effects of these options on the performance of the simplex method. Testing was performed on a DEC VAXstation II with 13 megabytes of main memory. The solution time was measured by timing the MINOS subroutine M5SOLV. The results demonstrate that the different options can significantly improve or degrade the performance of the simplex method. Scaling and partial pricing can improve the performance of the simplex method in most cases. However, options must be carefully chosen - a difficult task - in order not to degrade the performance of the simplex method.
A new algorithm is presented which efficiently incorporates the regular and dual simplex algorithms. The strategy adapted for the new algorithm is summarized by the following two phases: Phase I. Push toward a neighbo...
详细信息
A new algorithm is presented which efficiently incorporates the regular and dual simplex algorithms. The strategy adapted for the new algorithm is summarized by the following two phases: Phase I. Push toward a neighboring vertex of the optimal solution while trying to maintain feasibility. Phase II. If pushed too far in Phase I, pull back toward the optimal vertex (if any).
In this paper we present a decomposition approach to solve large scale linearprogramming models for production scheduling when there are multiple capacity-constrained facilities. The formulation assumes that there ar...
详细信息
In this paper we present a decomposition approach to solve large scale linearprogramming models for production scheduling when there are multiple capacity-constrained facilities. The formulation assumes that there are no initial inventories, and hence is most useful in a planning environment where the current shop status is not the primary concern. The approach can be implemented as an exact procedure or with heuristic stopping rules. We determine problem characteristics for which the decomposition approach is faster than LP, so that very large problems could be solved. Problem difficulty is found to be related to size and tightness of the capacity constraints. Quality-of-solution versus CPU time tradeoffs are given for various stopping rules. Finally, we discuss the potential importance of this formulation and approach in manufacturing problems.
The minimum cost, multiperiod network flow problem is an optimization model that often is used to help decision makers in resource planning, scheduling, and distribution. The forward network simplex algorithm, which ...
详细信息
The minimum cost, multiperiod network flow problem is an optimization model that often is used to help decision makers in resource planning, scheduling, and distribution. The forward network simplex algorithm, which exploits the natural decomposition of the problem by limiting its pivoting activity to later time periods, uses the multiperiod structure. It is a forward algorithm, which solves dynamic problems by solving successively longer finite subproblems, terminating when a stopping rule can be invoked or a decision horizon found. Computational results indicate that the forward network simplex implementation is significantly more efficient then standard network optimization codes that do not exploit the multiperiod structure. The primary-secondary storage implementation of the forward network simplex method is discussed. Problems having 700 time periods for a total of 3,500 nodes and 9,095 arcs were solved in less than 1/3 the time of the standard code on which the forward network implementation was based.
Integer programming is widely applicable to problems in industry and business. A special type of integer program, the binary knapsack problem, is examined. The binary knapsack problem is of major importance because ...
详细信息
Integer programming is widely applicable to problems in industry and business. A special type of integer program, the binary knapsack problem, is examined. The binary knapsack problem is of major importance because it is a subproblem that must be repeatedly solved in the solution of more general mathematical programs, such as vehicle scheduling and routing. Of the several efficient algorithms for the solution of binary knapsack problems that have appeared in the literature, the direct descent algorithm suggested by Zoltners (1978) is generally considered one of the most efficient. Zoltners' direct descent algorithm is improved through a more general fathom and backtrack methodology and stronger reduction tests. The improvements result in substantially, often dramatically, shortened solution times. The efficiency of these improvements is verified via extensive computational testing.
暂无评论