Application of the dual active set algorithm to quadratic network optimization

A new algorithm, the dual active set algorithm, is presented for solving a minimization problem with equality constraints and bounds on the variables. The algorithm identifies the active bound constraints by maximizing an unconstrained dual function in a finite number of iterations. Convergence of the method is established, and it is applied to convex quadratic programming. In its implementable form, the algorithm is combined with the proximal point method. A computational study of large-scale quadratic network problems compares the algorithm to a coordinate ascent method and to conjugate gradient methods for the dual problem. This study shows that combining the new algorithm with the nonlinear conjugate gradient method is particularly effective on difficult network problems from the literature.     

Application of the alternating direction method of multipliers to separable convex programming problems

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.     

A hybrid algorithm for the minimum bounding sphere problem

Two primal approaches, the shrinking approach and the dual approach, have been studied for the exact Minimum Bounding Sphere (MBS) problem. In this paper, we present a dual algorithm that uses the shrinking approach to solve subproblems. The experiments show our hybrid algorithm is faster than the dedicated shrinking algorithm and dual algorithm for solving the exact MBS problem in large point sets.     

A primal–dual algorithm for the economic lot-sizing problem with multi-mode replenishment

The classical economic lot-sizing problem assumes that a single supplier and a single transportation mode are used to replenish the inventory. This paper studies an extension of this problem where several suppliers and transportation modes are available. The decision-making process in this case involves identifying (i) the timing for an order; (ii) the choice of shipment modes; and (iii) the order size for each mode. The problem is defined as a network flow problem with multiple setups cost function and additional side constraints. This study provides an MIP formulation for the problem. We also provide an additional formulation of the problem by redefining its decision variables and show that the dual of the corresponding LP-relaxation has a special structure. We take advantage of the structure of the dual problem to develop a primal–dual algorithm that generates tight lower and upper bounds. Computational results demonstrate the effectiveness of the algorithm.     

A primal–dual algorithm for minimizing a sum of Euclidean norms

We study the problem of minimizing a sum of Euclidean norms. This nonsmooth optimization problem arises in many different kinds of modern scientific applications. In this paper we first transform this problem and its dual problem into a system of strongly semismooth equations, and give some uniqueness theorems for this problem. We then present a primal–dual algorithm for this problem by solving this system of strongly semismooth equations. Preliminary numerical results are reported, which show that this primal–dual algorithm is very promising.     

New geometry-inspired relaxations and algorithms for the metric Steiner tree problem

Determining the integrality gap of the bidirected cut relaxation for the metric Steiner tree problem, and exploiting it algorithmically, is a long-standing open problem. We use geometry to define an LP whose dual is equivalent to this relaxation. This opens up the possibility of using the primal-dual schema in a geometric setting for designing an algorithm for this problem. Using this approach, we obtain a 4/3 factor algorithm and integrality gap bound for the case of quasi-bipartite graphs; the previous best integrality gap upper bound being 3/2 (Rajagopalan and Vazirani in On the bidirected cut relaxation for the metric Steiner tree problem, 1999). We also obtain a factor \({\sqrt{2}}\) strongly polynomial algorithm for this class of graphs. A key difficulty experienced by researchers in working with the bidirected cut relaxation was that any reasonable dual growth procedure produces extremely unwieldy dual solutions. A new algorithmic idea helps finesse this difficulty—that of reducing the cost of certain edges and constructing the dual in this altered instance—and this idea can be extracted into a new technique for running the primal-dual schema in the setting of approximation algorithms.     

双层指派模型及算法

介绍了指派问题应用中出现的一种新类型——双层指派问题,建立了双层指派问题的数学模型,并提出了针对双层指派模型的算法,最后给出它在铁路客车车底周转运用中的实例.     

An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts

This paper presents a new exact algorithm for the Capacitated Vehicle Routing Problem (CVRP) based on the set partitioning formulation with additional cuts that correspond to capacity and clique inequalities. The exact algorithm uses a bounding procedure that finds a near optimal dual solution of the LP-relaxation of the resulting mathematical formulation by combining three dual ascent heuristics. The first dual heuristic is based on the q-route relaxation of the set partitioning formulation of the CVRP. The second one combines Lagrangean relaxation, pricing and cut generation. The third attempts to close the duality gap left by the first two procedures using a classical pricing and cut generation technique. The final dual solution is used to generate a reduced problem containing only the routes whose reduced costs are smaller than the gap between an upper bound and the lower bound achieved. The resulting problem is solved by an integer programming solver. Computational results over the main instances from the literature show the effectiveness of the proposed algorithm.      

Using duality to solve generalized fractional programming problems

In this paper we explore the relations between the standard dual problem of a convex generalized fractional programming problem and the partial dual problem proposed by Barros et al. (1994). Taking into account the similarities between these dual problems and using basic duality results we propose a new algorithm to directly solve the standard dual of a convex generalized fractional programming problem, and hence the original primal problem, if strong duality holds. This new algorithm works in a similar way as the algorithm proposed in Barros et al. (1994) to solve the partial dual problem. Although the convergence rates of both algorithms are similar, the new algorithm requires slightly more restrictive assumptions to ensure a superlinear convergence rate. An important characteristic of the new algorithm is that it extends to the nonlinear case the Dinkelbach-type algorithm of Crouzeix et al. (1985) applied to the standard dual problem of a generalized linear fractional program. Moreover, the general duality results derived for the nonlinear case, yield an alternative way to derive the standard dual of a generalized linear fractional program. The numerical results, in case of quadratic-linear ratios and linear constraints, show that solving the standard dual via the new algorithm is in most cases more efficient than applying directly the Dinkelbach-type algorithm to the original generalized fractional programming problem. However, the numerical results also indicate that solving the alternative dual (Barros et al., 1994) is in general more efficient than solving the standard dual.This research was carried out at the Econometric Institute, Erasmus University Rotterdam, the Netherlands and was supported by the Tinbergen Institute Rotterdam     

双层线性规划的一个全局优化方法

用线性规划对偶理论分析了双层线性规划的最优解与下层问题的对偶问题可行域上极点之间的关系，通过求得下层问题的对偶问题可行域上的极点，将双层线性规划转化为有限个线性规划问题，从而用线性规划方法求得问题的全局最优解．由于下层对偶问题可行域上只有有限个极点，所以方法具有全局收敛性．     

Approximating the nondominated set of an MOLP by approximately solving its dual problem

The geometric duality theory of Heyde and Löhne (2006) defines a dual to a multiple objective linear programme (MOLP). In objective space, the primal problem can be solved by Benson’s outer approximation method (Benson 1998a,b) while the dual problem can be solved by a dual variant of Benson’s algorithm (Ehrgott et al. 2007). Duality theory then assures that it is possible to find the (weakly) nondominated set of the primal MOLP by solving its dual. In this paper, we propose an algorithm to solve the dual MOLP approximately but within specified tolerance. This approximate solution set can be used to calculate an approximation of the weakly nondominated set of the primal. We show that this set is a weakly ε-nondominated set of the original primal MOLP and provide numerical evidence that this approach can be faster than solving the primal MOLP approximately.     

An Algorithm for the Design of Multitype Concentrator Networks

In recent years we have witnessed remarkable progress in the development of the topological design of computer communication networks. One of the important aspects of the topological design of computer communication networks is the concentrator location problem. This problem is a complex combinatorial problem that belongs to the difficult class of NP-complete problems where the computation of an optimal solution is still a challenging task. This paper extends the standard capacitated concentrator location problem to a generalization of multitype capacitated concentrator location problems and presents an efficient algorithm based on cross decomposition. This algorithm incorporates the Benders decomposition and Lagrangean relaxation methods into a single framework and exploits the resulting primal and dual structure simultaneously. Computational results are quite satisfactory and encouraging and show this algorithm to be both efficient and effective. The use of cross decomposition as a heuristic algorithm is also discussed.     

Canonical dual approach to solving the maximum cut problem

This paper presents a canonical dual approach for finding either an optimal or approximate solution to the maximum cut problem (MAX CUT). We show that, by introducing a linear perturbation term to the objective function, the maximum cut problem is perturbed to have a dual problem which is a concave maximization problem over a convex feasible domain under certain conditions. Consequently, some global optimality conditions are derived for finding an optimal or approximate solution. A gradient decent algorithm is proposed for this purpose and computational examples are provided to illustrate the proposed approach.     

The traveling salesman problem: A duality approach

In this study we formulate the dual of the traveling salesman problem, which extends in a natural way the dual problem of Held and Karp to the nonsymmetric case. The dual problem is solved by a subgradient optimization technique. A branch and bound scheme with stepped fathoming is then used to find optimal and suboptimal tours. Computational experience for the algorithm is presented.This author's work was partially supported by NSF Grant #GK-38337.     

A dual algorithm for the one-machine scheduling problem

A branch and bound algorithm is presented for the problem of schedulingn jobs on a single machine to minimize tardiness. The algorithm uses a dual problem to obtain a good feasible solution and an extremely sharp lower bound on the optimal objective value. To derive the dual problem we regard the single machine as imposing a constraint for each time period. A dual variable is associated with each of these constraints and used to form a Lagrangian problem in which the dualized constraints appear in the objective function. A lower bound is obtained by solving the Lagrangian problem with fixed multiplier values. The major theoretical result of the paper is an algorithm which solves the Lagrangian problem in a number of steps proportional to the product ofn ² and the average job processing time. The search for multiplier values which maximize the lower bound leads to the formulation and optimization of the dual problem. The bounds obtained are so sharp that very little enumeration or computer time is required to solve even large problems. Computational experience with 20-, 30-, and 50-job problems is presented.     

An efficient algorithm for the Lagrangean dual of nonlinear knapsack problems with additional nested constraints

This paper presents an efficient algorithm for solving the Lagrangean dual of nonlinear knapsack problems with additional nested constraints. The dual solution provides a feasible primal solution (if it exists) and associated lower and upper bounds on the optimal objective function value of the primal problem. Computational experience is cited indicating computation time, number of dual iterations, and “tightness” of the bounds.     

Ergodic,primal convergence in dual subgradient schemes for convex programming,II: the case of inconsistent primal problems

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.     

Exact Algorithm for the Surrogate Dual of an Integer Programming Problem: Subgradient Method Approach

One of the critical issues in the effective use of surrogate relaxation for an integer programming problem is how to solve the surrogate dual within a reasonable amount of computational time. In this paper, we present an exact and efficient algorithm for solving the surrogate dual of an integer programming problem. Our algorithm follows the approach which Sarin et al. (Ref. 8) introduced in their surrogate dual multiplier search algorithms. The algorithms of Sarin et al. adopt an ad-hoc stopping rule in solving subproblems and cannot guarantee the optimality of the solutions obtained. Our work shows that this heuristic nature can actually be eliminated. Convergence proof for our algorithm is provided. Computational results show the practical applicability of our algorithm.     

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.     

Optimal filter design subject to output sidelobe constraints: Computational algorithm and numerical results

An algorithm is presented for the design of optimal detection filters in radar and communications systems, subject to inequality constraints on the maximum output sidelobe levels. This problem was reduced in an earlier paper (Ref. 1) to an unconstrained one in the dual space of regular Borel measures, with a nondifferentiable cost functional. Here, the dual problem is solved via steepest descent, using the directional Gateaux differential. The algorithm is shown to be convergent, and numerical results are presented.This research was supported by the Australian Research Grants Committee.