The auction algorithm: A distributed relaxation method for the assignment problem

We propose a massively parallelizable algorithm for the classical assignment problem. The algorithm operates like an auction whereby unassigned persons bid simultaneously for objects thereby raising their prices. Once all bids are in, objects are awarded to the highest bidder. The algorithm can also be interpreted as a Jacobi — like relaxation method for solving a dual problem. Its (sequential) worst — case complexity, for a particular implementation that uses scaling, is O(NAlog(NC)), where N is the number of persons, A is the number of pairs of persons and objects that can be assigned to each other, and C is the maximum absolute object value. Computational results show that, for large problems, the algorithm is competitive with existing methods even without the benefit of parallelism. When executed on a parallel machine, the algorithm exhibits substantial speedup.Work supported by Grant NSF-ECS-8217668. Thanks are due to J. Kennington and L. Hatay of Southern Methodist Univ. for contributing some of their computational experience.     

Relaxation techniques for strictly convex network problems

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.     

Computational experience with a globally convergent primal—dual predictor—corrector algorithm for linear programming

Kojima, Megiddo, and Mizuno proved global convergence of a primal—dual algorithm that corresponds to methods used in practice. Here, the numerical efficiency of a predictor—corrector extension of that algorithm is tested. Numerical results are extremely positive, indicating that the safety of a globally convergent algorithm can be obtained at little computational cost. The algorithm is tested on infeasible problems with less success. Finally, the algorithm is applied to a warm started problem, with very encouraging preliminary results.Corresponding author. The research of this author is sponsored by the Air Force Office of Scientific Research, Air Force System Command under Grant AFOSR-92-J0046. The United States Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notations thereon.     

Feasible directions algorithms for optimization problems with equality and inequality constraints

In this paper two algorithms, of the feasible-directions and dual feasible-directions type, are presented for optimization problems with equality and inequality constraints. An associated problem, having only inequality constraints, is defined, and shown to be equivalent to the original problem if a certain parameter is sufficiently large. The algorithms solve the associated problem, but incorporate a method for automatically increasing this parameter in order to ensure global convergence to a solution to the original problem. Any feasible directions algorithm can be similarly modified to enable it to handle equality constraints.Research sponsored by the US Army Research Office — Durham, Contract DAHCO4-73-C-0025 and the National Science Foundation Grant GK-37572.     

Polynomiality of infeasible-interior-point algorithms for linear programming

Kojima, Megiddo, and Mizuno investigate an infeasible-interior-point algorithm for solving a primal—dual pair of linear programming problems and they demonstrate its global convergence. Their algorithm finds approximate optimal solutions of the pair if both problems have interior points, and they detect infeasibility when the sequence of iterates diverges. Zhang proves polynomial-time convergence of an infeasible-interior-point algorithm under the assumption that both primal and dual problems have feasible points. In this paper, we show that a modification of the Kojima—Megiddo—Mizuno algorithm solves the pair of problems in polynomial time without assuming the existence of the LP solution. Furthermore, we develop anO(nL)-iteration complexity result for a variant of the algorithm.The original title was Polynomiality of the Kojima—Megiddo—Mizuno infeasible-interior-point algorithm for linear programming.Research performed while visiting Cornell University (April 1992 – January 1993) as an Overseas Research Scholar of the Ministry of Science, Education and Culture of Japan.     

The primal-dual algorithm as a constraint-set-manipulation device

A general primal—dual algorithm for linearly constrained optimization problems is formulated in which the dual variables are updated by a dual algorithmic operator. Convergence is proved under the assumption that the dual algorithmic operator implies asymptotic feasibility of the primal iterates with respect to the linear constraints. A general result relating the minimal values of an infinite sequence of constrained problems to the minimal value of a limiting problem (constrained by the limit of the sequence of constraints sets) is established and invoked. The applicability of the general theory is demonstrated by analyzing a specific dual algorithmic operator. This leads to the MART algorithm for constrained entropy maximization used in image reconstruction from projections.     

Formulation of linear problems and solution by a universal machine

Using the predicate language for ordered fields a class of problems referred to aslinear problems is defined. This class contains, for example, all systems of linear equations and inequalities, all linear programming problems, all integer programming problems with bounded variables, all linear complementarity problems, the testing of whether sets that are defined by linear inequalities are semilattices, all satisfiability problems in sentenial logic, the rank-computation of matrices, the computation of row-reduced echelon forms of matrices, and all quadratic programming problems with bounded variables. A single, one, algorithm, to which we refer as theUniversal Linear Machine, is described. It solves any instance of any linear problem. The Universal Linear Machine runs in two phases. Given a linear problem, in the first phase a Compiler running on a Turing Machine generates alinear algorithm for the problem. Then, given an instance of the linear problem, in the second phase the linear algorithm solves the particular instance of the linear problem. The linear algorithm is finite, deterministic, loopless and executes only the five ordered field operations — additions, multiplications, subtractions, divisions and comparisons. Conversely, we show that for each linear algorithm there is a linear problem which the linear algorithm solves uniquely. Finally, it is shown that with a linear algorithm for a linear problem, one can solve certain parametric instances of the linear problem.Research was supported in part by the National Science Foundation Grant DMS 92-07409, by the Department of Energy Grant DE-FG03-87-ER-25028, by the United States—Israel Binational Science Foundation Grant 90-00434 and by ONR Grant N00014-92-J1142.Corresponding author.     

Dual estimates in multiextremal problems

We propose a technique of improving the dual estimates in nonconvex multiextremal problems of mathematical programming, by adding some additional constraints which are the consequences of the original constraints. This technique is used for the problems of finding the global minimum of polynomial functions, and extremal quadratic and boolean quadratic problems. In the article one ecological multiextremal problem and an algorithm for finding the dual estimate for it also considered. This algorithm is based upon a scheme of decomposition and nonsmooth optimization methods.This paper was presented at the II. IIASA Workshop on Global Optimization, Sopron (Hungary), December 9–14, 1990.     

A method for solving to optimality uncapacitated location problems

In this paper we develop a method for solving to optimality a general 0–1 formulation for uncapacitated location problems. This is a 3-stage method that solves large problems in reasonable computing times.The 3-stage method is composed of a primal-dual algorithm, a subgradient optimization to solve a Lagrangean dual and a branch-and-bound algorithm. It has a hierarchical structure, with a given stage being activated only if the optimal solution could not be identified in the preceding stage.The proposed method was used in the solution of three well-known uncapacitated location problems: the simple plant location problem, thep-median problem and the fixed-chargep-median problem. Computational results are given for problems of up to the size 200 customers ×200 potential facility sites.     

Global minimization by reducing the duality gap

We derive a general principle demonstrating that by partitioning the feasible set, the duality gap, existing between a nonconvex program and its lagrangian dual, can be reduced, and in important special cases, even eliminated. The principle can be implemented in a Branch and Bound algorithm which computes an approximate global solution and a corresponding lower bound on the global optimal value. The algorithm involves decomposition and a nonsmooth local search. Numerical results for applying the algorithm to the pooling problem in oil refineries are given.Research supported by Shell Laboratorium, Amsterdam, and GIF—The German—Israel Foundation for Scientific Research and Development.     

On the convergence of cross decomposition

Cross decomposition is a recent method for mixed integer programming problems, exploiting simultaneously both the primal and the dual structure of the problem, thus combining the advantages of Dantzig—Wolfe decomposition and Benders decomposition. Finite convergence of the algorithm equipped with some simple convergence tests has been proved. Stronger convergence tests have been proposed, but not shown to yield finite convergence.In this paper cross decomposition is generalized and applied to linear programming problems, mixed integer programming problems and nonlinear programming problems (with and without linear parts). Using the stronger convergence tests finite exact convergence is shown in the first cases. Unbounded cases are discussed and also included in the convergence tests. The behaviour of the algorithm when parts of the constraint matrix are zero is also discussed. The cross decomposition procedure is generalized (by using generalized Benders decomposition) in order to enable the solution of nonlinear programming problems.     

On weighted multiway cuts in trees

A min—max theorem is developed for the multiway cut problem of edge-weighted trees. We present a polynomial time algorithm to construct an optimal dual solution, if edge weights come in unary representation. Applications to biology also require some more complex edge weights. We describe a dynamic programming type algorithm for this more general problem from biology and show that our min—max theorem does not apply to it.Corresponding author.Research of the author was supported by the A. v. Humboldt-Stiftung and the U.S. Office of Naval Research under the contract N-0014-91-J-1385.     

Geometric separation and exact solutions for the parameterized independent set problem on disk graphs

We consider the parameterized problem, whether for a given set  of n disks (of bounded radius ratio) in the Euclidean plane there exists a set of k non-intersecting disks. For this problem, we expose an algorithm running in time that is—to our knowledge—the first algorithm with running time bounded by an exponential with a sublinear exponent. For λ-precision disk graphs of bounded radius ratio, we show that the problem is fixed parameter tractable with a running time  . The results are based on problem kernelization and a new “geometric ( -separator) theorem” which holds for all disk graphs of bounded radius ratio. The presented algorithm then performs, in a first step, a “geometric problem kernelization” and, in a second step, uses divide-and-conquer based on our new “geometric separator theorem.”     

A technique for speeding up the solution of the Lagrangean dual

We propose techniques for the solution of the LP relaxation and the Lagrangean dual in combinatorial optimization and nonlinear programming problems. Our techniques find the optimal solution value and the optimal dual multipliers of the LP relaxation and the Lagrangean dual in polynomial time using as a subroutine either the Ellipsoid algorithm or the recent algorithm of Vaidya. Moreover, in problems of a certain structure our techniques find not only the optimal solution value, but the solution as well. Our techniques lead to significant improvements in the theoretical running time compared with previously known methods (interior point methods, Ellipsoid algorithm, Vaidya's algorithm). We use our method to the solution of the LP relaxation and the Langrangean dual of several classical combinatorial problems, like the traveling salesman problem, the vehicle routing problem, the Steiner tree problem, thek-connected problem, multicommodity flows, network design problems, network flow problems with side constraints, facility location problems,K-polymatroid intersection, multiple item capacitated lot sizing problem, and stochastic programming. In all these problems our techniques significantly improve the theoretical running time and yield the fastest way to solve them.     

Dynamic Network Flow with Uncertain Arc Capacities: Decomposition Algorithm and Computational Results

In a multiperiod dynamic network flow problem, we model uncertain arc capacities using scenario aggregation. This model is so large that it may be difficult to obtain optimal integer or even continuous solutions. We develop a Lagrangian decomposition method based on the structure recently introduced in G.D. Glockner and G.L. Nemhauser, Operations Research, vol. 48, pp. 233–242, 2000. Our algorithm produces a near-optimal primal integral solution and an optimum solution to the Lagrangian dual. The dual is initialized using marginal values from a primal heuristic. Then, primal and dual solutions are improved in alternation. The algorithm greatly reduces computation time and memory use for real-world instances derived from an air traffic control model.     

An algorithm for large scale 0–1 integer programming with application to airline crew scheduling

We present an approximation algorithm for solving large 0–1 integer programming problems whereA is 0–1 and whereb is integer. The method can be viewed as a dual coordinate search for solving the LP-relaxation, reformulated as an unconstrained nonlinear problem, and an approximation scheme working together with this method. The approximation scheme works by adjusting the costs as little as possible so that the new problem has an integer solution. The degree of approximation is determined by a parameter, and for different levels of approximation the resulting algorithm can be interpreted in terms of linear programming, dynamic programming, and as a greedy algorithm. The algorithm is used in the CARMEN system for airline crew scheduling used by several major airlines, and we show that the algorithm performs well for large set covering problems, in comparison to the CPLEX system, in terms of both time and quality. We also present results on some well known difficult set covering problems that have appeared in the literature.     

On dual minimum cost flow algorithms

We describe a new dual algorithm for the minimum cost flow problem. It can be regarded as a variation of the best known strongly polynomial minimum cost flow algorithm, due to Orlin. Indeed we obtain the same running time of O(m log m(m+n log n)), where n and m denote the number of vertices and the number of edges. However, in contrast to Orlin's algorithm we work directly with the capacitated network (rather than transforming it to a transshipment problem). Thus our algorithm is applicable to more general problems (like submodular flow) and is likely to be more efficient in practice.  Our algorithm can be interpreted as a cut cancelling algorithm, improving the best known strongly polynomial bound for this important class of algorithms by a factor of m. On the other hand, our algorithm can be considered as a variant of the dual network simplex algorithm. Although dual network simplex algorithms are reportedly quite efficient in practice, the best worst-case running time known so far exceeds the running time of our algorithm by a factor of n.     

Discretization of the dynamic problem of elasticity theory with a discontinuous solution

A discretization algorithm for initial boundary-value problems is developed for systems of two linear equations of hyperbolic type with discontinuous solutions. A Crank—Nicholson scheme is constructed for discretization of the Cauchy problem and error bounds are obtained for the approximate solution. A model example is solved.Institute of Cybernetics of the Ukrainian Academy of Sciences. Kiev University. Translated from Vychislitel'naya i Prikladnaya Matematika, No. 75, pp. 75–83, 1991.     

On polynomiality of the Mehrotra-type predictor—corrector interior-point algorithms

Recently, Mehrotra [3] proposed a predictor—corrector primal—dual interior-point algorithm for linear programming. At each iteration, this algorithm utilizes a combination of three search directions: the predictor, the corrector and the centering directions, and requires only one matrix factorization. At present, Mehrotra's algorithmic framework is widely regarded as the most practically efficient one and has been implemented in the highly successful interior-point code OB1 [2]. In this paper, we study the theoretical convergence properties of Mehrotra's interior-point algorithmic framework. For generality, we carry out our analysis on a horizontal linear complementarity problem that includes linear and quadratic programming, as well as the standard linear complementarity problem. Under the monotonicity assumption, we establish polynomial complexity bounds for two variants of the Mehrotra-type predictor—corrector interior-point algorithms. These results are summarized in the last section in a table.Research supported in part by NSF DMS-9102761, DOE DE-FG05-91ER25100 and DOE DE-FG02-93ER25171.Corresponding author.     

Quasiperiodic solutions of variational problems of motion in a central force field

A method is proposed for computing nearly optimal trajectories of dynamic systems with a small parameter by splitting the original variational problem into two separate problems for "fast" and "slow" variables. The problem for "fast" variables is solved by improving the zeroth approximation — the extremals of the linearized problem — by the Ritz method. The solution of the problem for "slow" variables is constructed by passing from a discrete argument — the number of revolutions around the attracting center— to a continuous argument. The proposed method does not require numerical integration of systems of differential equations and produces a highly accurate approximate solution of the problem.Kiev University. Translated from Vychislitel'naya i Prikladnaya Matematika, No. 68, pp. 113–118, 1989.