An evolutionary algorithm for the multi‐objective pick‐up and delivery pollution‐routing problem

The design of sustainable logistics solutions poses new challenges for the study of vehicle‐routing problems. The design of efficient systems for transporting products via a heterogeneous fleet of vehicles must consider the minimization of cost, emissions of greenhouse gases, and the ability to serve every customer within an available time slot. This phenomenon gives rise to a multi‐objective problem that considers the emission of greenhouse gases, the total traveling time, and the number of customers served. The proposed model is approached with an ε‐constraint technique that allows small instances to be solved and an evolutionary algorithm is proposed to deal with complex instances. Results for small instances show that all the points that approach the Pareto frontier found by the evolutionary algorithm are nondominated by any solution found by the multi‐objective model. For complex instances, nondominated solutions that serve most of the requests are found with low computational requirements.     

Interior point methods meet simplex in L∞, fitting problems

Interior point methods specialized to the L_∞ fitting problem are surveyed, improved, and compared with the traditional simplex approach. A primal affine‐scaling interior point method is presented, completing the affine‐scaling interior point family approach to the L_∞ fitting problem. Computational complexity and data storage are reduced for interior point approaches when dealing with polynomial fitting problems. Numerical experiments indicate that interior point approaches rarely perform better than the simplex method for the tested problems. The primal affine‐scaling method presented in this paper achieved the best results among the interior point family.     

Network dual steepest-edge methods for solving capacitated multicommodity network problems

This paper presents a two-phased network dual steepest-edge method for solving capacitated multicommodity network problems. In the first phase, an advanced starting solution in concert with a dual steepest-edge method is applied to solve each capacitated single-commodity network problem. At each iteration, either the primal infeasibility is improved or the dual objective value is inceased. In the second phase, the steepest-edge selection criterion is used to determine the leaving infeasible coupling constraint. By maintaining dual feasibility while improving the dual objective value, the number of infeasible coupling constraints is monotonically reduced to zero. The finite convergency property of this algorithm is shown. Finally, this algorithm is coded using Pascal language and tested in several problems. Results show this algorithm is promising.     

Rough‐fuzzy quadratic minimum spanning tree problem

A quadratic minimum spanning tree problem determines a minimum spanning tree of a network whose edges are associated with linear and quadratic weights. Linear weights represent the edge costs whereas the quadratic weights are the interaction costs between a pair of edges of the graph. In this study, a bi‐objective rough‐fuzzy quadratic minimum spanning tree problem has been proposed for a connected graph, where the linear and the quadratic weights are represented as rough‐fuzzy variables. The proposed model is formulated by using rough‐fuzzy chance‐constrained programming technique. Subsequently, three related theorems are also proposed for the crisp transformation of the proposed model. The crisp equivalent models are solved with a classical multi‐objective solution technique, the epsilon‐constraint method and two multi‐objective evolutionary algorithms: (a) nondominated sorting genetic algorithm II (NSGA‐II) and (b) multi‐objective cross‐generational elitist selection, heterogeneous recombination, and cataclysmic mutation (MOCHC) algorithm. A numerical example is provided to illustrate the proposed model when solved with different methodologies. A sensitivity analysis of the example is also performed at different confidence levels. The performance of NSGA‐II and MOCHC are analysed on five randomly generated instances of the proposed model. Finally, a numerical illustration of an application of the proposed model is also presented in this study.     

An extension of Karmarkar's algorithm for linear programming using dual variables

We describe an extension of Karmarkar's algorithm for linear programming that handles problems with unknown optimal value and generates primal and dual solutions with objective values converging to the common optimal primal and dual value. We also describe an implementation for the dense case and show how extreme point solutions can be obtained naturally, with little extra computation.     

无线多跳网络联合拥塞控制和功率分配的快速二阶算法

针对节点功率受限的无线多跳网络,研究业务流路由确知时的联合功率分配、流量分配和拥塞控制问题,并基于原始对偶内点法设计一种具有二阶收敛性能的算法.该算法利用矩阵分裂方法实现业务流源速率和节点功率的分布式更新,最终优化网络效用.仿真结果表明,算法能有效降低网络中的功率消耗,提高网络的能量效用,同时相较于传统拉格朗日对偶分解法,所提出算法具有非常好的收敛性能.     

An extension of Karmarkar's algorithm for linear programming using dual variables

We describe an extension of Karmarkar's algorithm for linear programming that handles problems with unknown optimal value and generates primal and dual solutions with objective values converging to the common optimal primal and dual value. We also describe an implementation for the dense case and show how extreme point solutions can be obtained naturally, with little extra computation.Research supported in part by a fellowship from the Alfred P. Sloan Foundation and by NSF Grant ECS-15361.     

A proximal trust-region algorithm for column generation stabilization

This paper proposes a generalization of the proximal point algorithm using both penalty and trust-region concepts. Finite convergence is established while assuming the trust regions are of full dimension and never shrink to a single point. The approach is specialized to the cutting plane/column generation context. The resulting algorithm ensures convergence to a pair of primal and dual optimal solutions. Computational experiments carried over multi-depot vehicle scheduling instances show a great stabilizing and accelerating effect on the column generation method.     

Hessian distances and their applications in the complexity analysis of interior-point methods

For interior points in convex cones, we introduce the Hessian distance function, and show that it is convenient for complexity analysis of polynomial-time interior-point methods (IPMs). As an example of its application, we develop new infeasible-start IPM for the linear conic optimization problem. In our setting, the primal and dual cones need not to be self-dual. We can start from any primal–dual point in the interior of the cones. Then, the damped Newton's method can be used for obtaining an approximate solution for the strictly feasible case, or for detecting primal/dual infeasibility. The complexity of these cases depends on the Hessian distance between the starting point and the feasibility/infeasibility certificates. We also present some numerical results.     

Prox-regularization of the dual method of centers for generalized fractional programs

We present in this paper a prox-dual regularization algorithm for solving generalized fractional programming problems. The algorithm combines the dual method of centres for generalized fractional programs and the proximal point algorithm and can handle nondifferentiable convex problems with possibly unbounded feasible constraints set. The proposed procedure generates two sequences of dual and primal values that approximate the optimal value of the considered problem respectively from below and from above at each step. It also generates a sequence of dual solutions that converges to a solution of the dual problem, and a sequence of primal solutions whose every accumulation point is a solution of the primal problem. For a class of problems, including linear fractional programs, the algorithm converges linearly.     

Distributed primal–dual stochastic subgradient algorithms for multi‐agent optimization under inequality constraints

We consider the multi‐agent optimization problem where multiple agents try to cooperatively optimize the sum of their local convex objective functions, subject to global inequality constraints and a convex constraint set over a network. Through characterizing the primal and dual optimal solutions as the saddle points of the associated Lagrangian function, which can be evaluated with stochastic errors, we propose the distributed primal–dual stochastic subgradient algorithms for two cases: (i) the time model is synchronous and (ii) the time model is asynchronous. In the first case, we obtain bounds on the convergence properties of the algorithm for a diminishing step size. In the second case, for a constant step size, we establish some error bounds on the algorithm's performance. In particular, we prove that the error bounds scale as in the number of n agents. Copyright © 2012 John Wiley & Sons, Ltd.     

Multi‐mode resource‐constrained project scheduling using modified variable neighborhood search heuristic

This paper aims at providing a fast near‐optimum solution to the multi‐mode resource‐constrained project scheduling problems (MRCPSPs), for projects with activities that have known deterministic renewable and nonrenewable resource requirements. The MRCPSP is known to be nondeterministic polynomial‐time hard and has been solved using various exact, heuristic, and meta‐heuristic procedures. In this paper, a modified variable neighborhood search heuristic algorithm is used as an advanced optimization technique that suits scheduling problems. For the experimental study, we have considered a standard set of 3929 multi‐mode benchmark instances from the project scheduling library with a range of projects comprising 10–30 activities. Moreover, for a better comparison, this research also considers a standard set of 4320 newly developed multi‐mode instances from MMLIB50, MMLIB100, and MMLIB+ datasets. With the limit of 50,000 schedules on these datasets, our proposed algorithm provides better makespan for 106, 34, and 1601 instances, respectively, which justifies the efficiency of the proposed algorithm, particularly for projects with a larger number of activities. The results reported in this paper can be used as a benchmark for other researchers to compare and improve.     

A negative dual rectangle cancellation algorithm for the linear assignment problem

In this paper, we consider three alternative primal models and their corresponding alternative dual models for the linear assignment problem. We then define the concept of Negative Dual Rectangle (NDR) and suggest an algorithm that solves two of these dual problems by repeatedly finding and cancelling NDRs until it yields an optimal solution to the assignment problem. The algorithm is simple, flexible, efficient, and unified. We also introduce the notion of partial zero cover as an interpretation of an NDR. We then introduce some heuristic methods for finding NDRs. We also state and prove a lemma to establish the optimal use of an NDR. Furthermore, we show that on a new class of benchmark instances that is introduced in this paper the running time of our algorithm is highly superior to a well-known pure shortest path algorithm.     

A Dual‐Type Method Based Algorithm for Nonlinear Large Network Optimization Problems

In previous research, we have proposed a Dual Projected Pseudo Quasi Newton (DPPQN) method which differs from the conventional Lagrange relaxation method by treating the inequality constraints as the domain of the primal variables in the dual function and using Projection Theory to handle the inequality constraints. We have combined this dual‐type method with a Projected Jacobi (PJ) method to solve nonlinear large network optimization problems with decomposable inequality constraints, and have achieved several attractive features. To retain the attractive features and to remedy the flaw of the previous method, in the current paper, we propose an active set strategy based DPPQN method to solve the projection problem formed by coupling functional inequality constraints. This method associated with the DPPQN method and the PJ method can be used to solve general nonlinear large network optimization problems. We present this algorithm, demonstrate its computational efficiency through numerical simulations and compare it with the previous method.     

A model for a reliable single allocation hub network design under massive disruption

Hub facilities may fail to operate in networks because of accidental failures such as natural disasters. In this paper, a quadratic model was presented for a reliable single allocation hub network under massive random failure of hub facilities which more than one hub may be disrupted in a route. It determines the location of the hub facilities and the primal allocation of non-hub nodes. It also determines the backup allocation in case of failure of the primal hub. First, a new lexicographic form of a bi-objective quadratic model is presented where the first objective maximizes served demands or equivalently, minimizes lost flows and the second objective minimizes total cost under a to massive disruption in the network. Then, by adding a structure-based constraint, the model is transformed to a single objective one. A linearization technique reported in the literature is applied on the quadratic model to convert it into classic linear zero–one mixed integer model while enhancing it by finding tighter bounds. The tight bounds’ technique is compared with other techniques in terms of computational time and its better performance was approved in some problem instances. Finally, due to the NP-hardness of the problem, an iterated local search algorithm was developed to solve large sized instances in a reasonable computational time and the computational results confirm the efficiency of the proposed heuristic, ILS can solve all CAB and IAD data set instances in less than 15 and 24 seconds, respectively. Moreover, the proposed model was compared with the classical hub network using a network performance measure, and the results show the increased efficiency of the model.     

Implementation and analysis of alternative algorithms for generalized shortest path problems

This paper addresses a special class of deterministic dynamic programming problems which can be formulated as a generalized network problem. Because of the similarities between this class of dynamic programming problems and shortest path problems, we are naming it the Generalized Shortest Path problem. A new primal extreme point algorithm and a new special dual algorithm are proposed here. While researchers have presented a variety of algorithms to solve this class of problems, there has been no comuptational analysis of these algorithms. An in-depth computational analysis is performed to determine the most efficient set of rules for implementing the algorithms of this paper.     

Multi‐objective memetic algorithm: comparing artificial neural networks and pattern search filter method approaches

In this work, two methodologies to reduce the computation time of expensive multi‐objective optimization problems are compared. These methodologies consist of the hybridization of a multi‐objective evolutionary algorithm (MOEA) with local search procedures. First, an inverse artificial neural network proposed previously, consisting of mapping the decision variables into the multiple objectives to be optimized in order to generate improved solutions on certain generations of the MOEA, is presented. Second, a new approach based on a pattern search filter method is proposed in order to perform a local search around certain solutions selected previously from the Pareto frontier. The results obtained, by the application of both methodologies to difficult test problems, indicate a good performance of the approaches proposed.     

Warm start by Hopfield neural networks for interior point methods

Hopfield neural networks and interior point methods are used in an integrated way to solve linear optimization problems. The Hopfield network gives warm start for the primal–dual interior point methods, which can be way ahead in the path to optimality. The approaches were applied to a set of real world linear programming problems. The integrated approaches provide promising results, indicating that there may be a place for neural networks in the “real game” of optimization.     

Performance Analysis of The Auxiliary‐Model‐Based Multi‐Innovation Stochastic Newton Recursive Algorithm for Dual‐Rate Systems

The stochastic Newton recursive algorithm is studied for dual‐rate system identification. Owing to a lack of intersample measurements, the single‐rate model cannot be identified directly. The auxiliary model technique is adopted to provide the intersample estimations to guarantee the recursion process continues. Intersample estimations have a great influence on the convergence of parameter estimations, and one‐step innovation may lead to a large fluctuation or even divergence during the recursion. In the meantime, the sample covariance matrix may appear singular. The recursive process would cease for these reasons. In order to guarantee the recursion process and to also improve estimation accuracy, multi‐innovation is utilized for correcting the parameter estimations. Combining the auxiliary model and multi‐innovation theory, the auxiliary‐model‐based multi‐innovation stochastic Newton recursive algorithm is proposed for time‐invariant dual‐rate systems. The consistency of this algorithm is analyzed in detail. The final simulations confirm the effectiveness of the proposed algorithm.     

Lagrangian bounds for large‐scale multicommodity network design: a comparison between Volume and Bundle methods

The Bundle Method and the Volume Algorithm are among the most efficient techniques to obtain accurate Lagrangian dual bounds for hard combinatorial optimization problems. We propose here to compare their performance on very large scale Fixed‐Charge Multicommodity Capacitated Network Design problems. The motivation is not only the quality of the approximation of these bounds as a function of the computational time but also the ability to produce feasible primal solutions and thus to reduce the gap for very large instances for which optimal solutions are out of reach. Feasible solutions are obtained through the use of Lagrangian information in constructive and improving heuristic schemes. We show in particular that, if the Bundle implementation has provided great quality bounds in fewer iterations, the Volume Algorithm is able to reduce the gaps of the largest instances, taking profit of the low computational cost per iteration compared to the Bundle Method.