Nonsmooth optimization methods for parallel decomposition of multicommodity flow problems

We develop an iterative algorithm based on right-hand side decomposition for the solution of multicommodity network flow problems. At each step of the proposed iterative procedure the coupling constraints are eliminated by subdividing the shared capacity resource among the different commodities and a master problem is constructed which attempts to improve sharing of the resources at each iteration.As the objective function of the master problem is nonsmooth, we apply to it a new optimization technique which does not require the exact solutions of the single commodity flow subproblems. This technique is based on the notion of - subgradients instead of subgradients and is suitable for parallel implementation. Extensions to the nonlinear, convex separable case are also discussed.The work of this author has been supported by the Air Force Office of Scientific Research Grant AFOSR-89-0410.     

An integer fixed-charge multicommodity flow (FCMF) model for train unit scheduling

An integer fixed-charge multicommodity flow (FCMF) model is used as the first part of a two-phase approach for train unit scheduling, and solved by an exact branch- and-price method. To strengthen knapsack constraints and deal with complicated scenarios arisen in the integer linear program (ILP) from the integer FCMF model, preprocessing is used by computing convex hulls of sets of points representing all possible train formations utilizing multiple unit types.     

A TRUST REGION ALGORITHM VIA BILEVEL LINEAR PROGRAMMING FOR SOLVING THE GENERAL MULTICOMMODITY MINIMAL COST FLOW PROBLEMS

This paper proposes a nonmonotonic backtracking trust region algorithm via bilevel linear programming for solving the general multicommodity minimal cost flow problems. Using the duality theory of the linear programming and convex theory, the generalized directional derivative of the general multicommodity minimal cost flow problems is derived. The global convergence and superlinear convergence rate of the proposed algorithm are established under some mild conditions.     

Sequential optimality conditions for composed convex optimization problems

Using a general approach which provides sequential optimality conditions for a general convex optimization problem, we derive necessary and sufficient optimality conditions for composed convex optimization problems. Further, we give sequential characterizations for a subgradient of the precomposition of a K-increasing lower semicontinuous convex function with a K-convex and K-epi-closed (continuous) function, where K is a nonempty convex cone. We prove that several results from the literature dealing with sequential characterizations of subgradients are obtained as particular cases of our results. We also improve the above mentioned statements.     

Relaxation methods for problems with strictly convex separable costs and linear constraints

We consider the minimization problem with strictly convex, possibly nondifferentiable, separable cost and linear constraints. The dual of this problem is an unconstrained minimization problem with differentiable cost which is well suited for solution by parallel methods based on Gauss-Seidel relaxation. We show that these methods yield the optimal primal solution and, under additional assumptions, an optimal dual solution. To do this it is necessary to extend the classical Gauss-Seidel convergence results because the dual cost may not be strictly convex, and may have unbounded level sets. Work supported by the National Science Foundation under grant NSF-ECS-3217668.     

Asynchronous gradient algorithms for a class of convex separable network flow problems

We consider the single commodity strictly convex network flow problem. The dual of this problem is unconstrained, differentiable, and well suited for solution via distributed or parallel iterative methods. We present and prove convergence of gradient and asynchronous gradient algorithms for solving the dual problem. Computational results are given and analysed.     

Sufficient global optimality conditions for weakly convex minimization problems

In this paper, we present sufficient global optimality conditions for weakly convex minimization problems using abstract convex analysis theory. By introducing (L,X)-subdifferentials of weakly convex functions using a class of quadratic functions, we first obtain some sufficient conditions for global optimization problems with weakly convex objective functions and weakly convex inequality and equality constraints. Some sufficient optimality conditions for problems with additional box constraints and bivalent constraints are then derived.      

Non-convex quadratic minimization problems with quadratic constraints: global optimality conditions

In this paper, we first examine how global optimality of non-convex constrained optimization problems is related to Lagrange multiplier conditions. We then establish Lagrange multiplier conditions for global optimality of general quadratic minimization problems with quadratic constraints. We also obtain necessary global optimality conditions, which are different from the Lagrange multiplier conditions for special classes of quadratic optimization problems. These classes include weighted least squares with ellipsoidal constraints, and quadratic minimization with binary constraints. We discuss examples which demonstrate that our optimality conditions can effectively be used for identifying global minimizers of certain multi-extremal non-convex quadratic optimization problems. The work of Z. Y. Wu was carried out while the author was at the Department of Applied Mathematics, University of New South Wales, Sydney, Australia.     

Uniform multicommodity flows in the hypercube with random edge‐capacities

We give two results for multicommodity flows in the d‐dimensional hypercube with independent random edge‐capacities distributed like a random variable C where . Firstly, with high probability as , the network can support simultaneous multicommodity flows of volume close to between all antipodal vertex pairs. Secondly, with high probability, the network can support simultaneous multicommodity flows of volume close to between all vertex pairs. Both results are best possible. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 437–463, 2017     

A hybrid algorithm for solving convex separable network flow problems

Based on computational experiments with different approaches to convex separable network flow problems a hybrid algorithm is developed and implemented. Phase one of the algorithm uses a rapidly converging series of piecewise linear secant approximations in order to determine a good solution within some distance of the optimum. Starting from this solution, a feasible direction method, based on reduced Newton directions, is used in the second phase of the algorithm to determine the optimal solution. Since nonlinear network flow problems tend to be degenerate, special emphasis is put on the construction of a basis that yields a strictly positive step length at the beginning of phase two of the hybrid algorithm.A number of test problems have been solved successfully. It is expected that the approach can be extended to solve large-scale problems with convex separable objective functions. Details of the implementation and computational results are presented.

---

Zusammenfassung Ausgehend von experimentellen Ergebnissen mit unterschiedlichen Lösungsverfahren für separable Netzwerkflußprobleme wurde ein zweistufiges Verfahren entwickelt und implementiert. Auf der ersten Stufe wird in einem iterativen Prozeß das zu lösende Problem mehrfach stückweise linearisiert. Man erhält eine bereits sehr gute Lösung. Mit dieser wird ein Richtungsverfahren initialisiert, das unter Verwendung reduzierter Newton Richtungen die optimale Lösung bestimmt. Das Richtungsverfahren bildet die zweite Stufe des Verfahrens. Da nichtlineare Netzwerkflußprobleme im allgemeinen stark entartet sind, wird zu Beginn der zweiten Stufe des beschriebenen Verfahrens eine Basis konstruiert, die eine positive Schrittlänge zuläßt.Es wurden zahlreiche Testprobleme mit bis zu 600 Knoten und 1400 Kanten mit dem beschriebenen Verfahren erfolgreich gelöst. Es wird erwartet, daß das Verfahren auch auf sehr viel größere Probleme mit konvexer, separabler Zielfunktion angewendet werden kann. Es wird auf Fragen zur Implementation eingegangen und es werden numerische Ergebnisse diskutiert.

     

An alternating linearization bundle method for convex optimization and nonlinear multicommodity flow problems

We give a bundle method for minimizing the sum of two convex functions, one of them being known only via an oracle of arbitrary accuracy. Each iteration involves solving two subproblems in which the functions are alternately represented by their linearizations. Our approach is motivated by applications to nonlinear multicommodity flow problems. Encouraging numerical experience on large scale problems is reported.     

A tabu search procedure for multicommodity location/allocation with balancing requirements

We propose a tabu search heuristic for the location/allocation problem with balancing requirements. This problem typically arises in the context of the medium term management of a fleet of containers of multiple types, where container depots have to be selected, the assignment of customers to depots has to be established for each type of container, and the interdepot container traffic has to be planned to account for differences in supplies and demands in various zones of the geographical territory served by a container shipping company. It is modeled as a mixed integer program, which combines zero-one location variables and a multicommodity network flow structure. Extensive computational results on a set of benchmark problems and comparisons with an efficient dual ascent procedure are reported. These show that tabu search is a competitive approach for this class of problems.     

Lagrangian based heuristics for the multicommodity network flow problem with fixed costs on paths

We study the multicommodity network flow problem with fixed costs on paths, with specific application to the empty freight car distribution process of a rail operator. The classification costs for sending a group of cars do not depend on the number of cars in the group, as long as the group is kept together as one unit. Arcs correspond to trains, so we have capacity restrictions on arcs but fixed costs on the paths corresponding to routes for groups of cars. As solution method, we propose a Lagrangian based heuristic using dual subgradient search and primal heuristics based on path information of the Lagrangian subproblem solutions. The method illustrates several ways of exploiting the specific structures of the problem. Computational tests indicate that the method is able to generate fairly good primal feasible solutions and lower bounds on the optimal objective function value.     

Fractional multi-commodity flow problem: Duality and optimality conditions

This paper deals with multi-commodity flow problem with fractional objective function. The optimality conditions and the duality concepts of this problem are given. For this aim, the fractional linear programming formulation of this problem is considered and the weak duality, the strong direct duality and the weak complementary slackness theorems are proved applying the traditional duality theory of linear programming problems which is different from same results in Chadha and Chadha (2007) [1]. In addition, a strong (strict) complementary slackness theorem is derived which is firstly presented based on the best of our knowledge. These theorems are transformed in order to find the new reduced costs for fractional multi-commodity flow problem. These parameters can be used to construct some algorithms for considered multi-commodity flow problem in a direct manner. Throughout the paper, the boundedness of the primal feasible set is reduced to a weaker assumption about solvability of primal problem which is another contribution of this paper. Finally, a real world application of the fractional multi-commodity flow problem is presented.     

一个局部带优先权的最大多物资网络流问题

给出一个局部带优先权的最大多物资网络流问题(MMFP-LPRI),证明它的解存在,并给出其η-松弛解的定义.通过做辅助网络,并运用程丛电等根据Korte和Vygen于2000年在Young,Garg和K(o|¨)nemann等工作的基础上给出的求最大多种物资网络流问题的ε-近似解的多项式方案设计的一个算法作为子程序进行二分收索建立了一个求所给问题的η-松弛解的拟多项式算法.最后,进行算法分析,证明了所设计的算法的输出结果确实是MMFP-LPRT的一个η-松弛解.     

Using copositivity for global optimality criteria in concave quadratic programming problems

In this note we specify a necessary and sufficient condition for global optimality in concave quadratic minimization problems. Using this condition, it follows that, from the perspective of worst-case complexity of concave quadratic problems, the difference between local and global optimality conditions is not as large as in general. As an essential ingredient, we here use the-subdifferential calculus via an approach of Hiriart-Urruty and Lemarechal (1990).     

The optimality conditions for optimization problems with convex constraints and multiple fuzzy-valued objective functions

The optimality conditions for multiobjective programming problems with fuzzy-valued objective functions are derived in this paper. The solution concepts for these kinds of problems will follow the concept of nondominated solution adopted in the multiobjective programming problems. In order to consider the differentiation of fuzzy-valued functions, we invoke the Hausdorff metric to define the distance between two fuzzy numbers and the Hukuhara difference to define the difference of two fuzzy numbers. Under these settings, the optimality conditions for obtaining the (strongly, weakly) Pareto optimal solutions are elicited naturally by introducing the Lagrange multipliers.     

A unified method for a class of convex separable nonlinear knapsack problems

In this paper, a unified algorithm is proposed for solving a class of convex separable nonlinear knapsack problems, which are characterized by positive marginal cost (PMC) and increasing marginal loss–cost ratio (IMLCR). By taking advantage of these two characteristics, the proposed algorithm is applicable to the problem with equality or inequality constraints. In contrast to the methods based on Karush–Kuhn–Tucker (KKT) conditions, our approach has linear computation complexity. Numerical results are reported to demonstrate the efficacy of the proposed algorithm for different problems.     

On a constructive approach to optimality conditions for convex SIP problems with polyhedral index sets

In the paper, we consider a problem of convex Semi-Infinite Programming with an infinite index set in the form of a convex polyhedron. In study of this problem, we apply the approach suggested in our recent paper [Kostyukova OI, Tchemisova TV. Sufficient optimality conditions for convex Semi Infinite Programming. Optim. Methods Softw. 2010;25:279–297], and based on the notions of immobile indices and their immobility orders. The main result of the paper consists in explicit optimality conditions that do not use constraint qualifications and have the form of criterion. The comparison of the new optimality conditions with other known results is provided.