Solving large scale Max Cut problems via tabu search

In recent years many algorithms have been proposed in the literature for solving the Max-Cut problem. In this paper we report on the application of a new Tabu Search algorithm to large scale Max-cut test problems. Our method provides best known solutions for many well-known test problems of size up to 10,000 variables, although it is designed for the general unconstrained quadratic binary program (UBQP), and is not specialized in any way for the Max-Cut problem.     

An algorithm for a selection procedure

When we have a selection problem that involves qualitative information, we can use the qualitative programming method and find the optimal choice by using integer programming. However, in practice after formulation of the problem we have a large scale model. In this note we introduce a very effective method for solving a qualitative programming problem. The only operations used in this method are scalar and matrix addition, and hence for problems of reasonable size, the method does not need high speed computers, and can be supplemented using hand calculators.     

The Multidimensional 0-1 Knapsack Problem—Bounds and Computational Aspects

The multidimensional 0-1 knapsack problem (MKP) is a resource allocation model that is one of the most well-known integer programming problems. During the last few decades, an impressive amount of research on the 0-1 knapsack problem has been published in the literature, and efficient special-purpose methods have become available for solving very large-scale instances. However, the multidimensional case has received less attention from the operational research community. Although recent advances have made solving medium size instances possible, solving the NP-hard problem remains a very interesting challenge, especially when the number of constraints increases. This paper surveys the principal results published in the literature concerning both the problem's theoretical properties and its approximate or exact solutions. The paper focuses on the more recent results—for example, those relevant to surrogate and composite duality, new preprocessing approaches creating enhanced versions of leading commercial software, and efficient metaheuristic-based methods.     

Interior point methods 25 years later

Interior point methods for optimization have been around for more than 25 years now. Their presence has shaken up the field of optimization. Interior point methods for linear and (convex) quadratic programming display several features which make them particularly attractive for very large scale optimization. Among the most impressive of them are their low-degree polynomial worst-case complexity and an unrivalled ability to deliver optimal solutions in an almost constant number of iterations which depends very little, if at all, on the problem dimension. Interior point methods are competitive when dealing with small problems of dimensions below one million constraints and variables and are beyond competition when applied to large problems of dimensions going into millions of constraints and variables.In this survey we will discuss several issues related to interior point methods including the proof of the worst-case complexity result, the reasons for their amazingly fast practical convergence and the features responsible for their ability to solve very large problems. The ever-growing sizes of optimization problems impose new requirements on optimization methods and software. In the final part of this paper we will therefore address a redesign of interior point methods to allow them to work in a matrix-free regime and to make them well-suited to solving even larger problems.     

A trust region method for solving semidefinite programs

When using interior point methods for solving semidefinite programs (SDP), one needs to solve a system of linear equations at each iteration. For problems of large size, solving the system of linear equations can be very expensive. In this paper, we propose a trust region algorithm for solving SDP problems. At each iteration we perform a number of conjugate gradient iterations, but do not need to solve a system of linear equations. Under mild assumptions, the convergence of this algorithm is established. Numerical examples are given to illustrate the convergence results obtained.     

The impact of energy function structure on solving generalized assignment problem using Hopfield neural network

In the last 20 years, neural networks researchers have exploited different penalty based energy functions structures for solving combinatorial optimization problems (COPs) and have established solutions that are stable and convergent. These solutions, however, have in general suffered from lack of feasibility and integrality. On the other hand, operational researchers have exploited different methods for converting a constrained optimization problem into an unconstrained optimization problem. In this paper we have investigated these methods for solving generalized assignment problems (GAPs). Our results concretely establishes that the augmented Lagrangean method can produce superior results with respect to feasibility and integrality, which are currently the main concerns in solving neural based COPs.     

Inexact Newton methods for the nonlinear complementarity problem

An exact Newton method for solving a nonlinear complementarity problem consists of solving a sequence of linear complementarity subproblems. For problems of large size, solving the subproblems exactly can be very expensive. In this paper we study inexact Newton methods for solving the nonlinear, complementarity problem. In such an inexact method, the subproblems are solved only up to a certain degree of accuracy. The necessary accuracies that are needed to preserve the nice features of the exact Newton method are established and analyzed. We also discuss some extensions as well as an application. This research was based on work supported by the National Science Foundation under grant ECS-8407240.     

On the computational efficiency of subgradient methods: a case study with Lagrangian bounds

Subgradient methods (SM) have long been the preferred way to solve the large-scale Nondifferentiable Optimization problems arising from the solution of Lagrangian Duals (LD) of Integer Programs (IP). Although other methods can have better convergence rate in practice, SM have certain advantages that may make them competitive under the right conditions. Furthermore, SM have significantly progressed in recent years, and new versions have been proposed with better theoretical and practical performances in some applications. We computationally evaluate a large class of SM in order to assess if these improvements carry over to the IP setting. For this we build a unified scheme that covers many of the SM proposed in the literature, comprised some often overlooked features like projection and dynamic generation of variables. We fine-tune the many algorithmic parameters of the resulting large class of SM, and we test them on two different LDs of the Fixed-Charge Multicommodity Capacitated Network Design problem, in order to assess the impact of the characteristics of the problem on the optimal algorithmic choices. Our results show that, if extensive tuning is performed, SM can be competitive with more sophisticated approaches when the tolerance required for solution is not too tight, which is the case when solving LDs of IPs.     

Quasi-human seniority-order algorithm for unequal circles packing

In the existing methods for solving unequal circles packing problems, the initial configuration is given arbitrarily or randomly, but the impact of different initial configurations for existing packing algorithm to the speed of existing packing algorithm solving unequal circles packing problems is very large. The quasi-human seniority-order algorithm proposed in this paper can generate a better initial configuration for existing packing algorithm to accelerate the speed of existing packing algorithm solving unequal circles packing problems. In experiments, the quasi-human seniority-order algorithm is applied to generate better initial configurations for quasi-physical elasticity methods to solve the unequal circles packing problems, and the experimental results show that the proposed quasi-human seniority-order algorithm can greatly improve the speed of solving the problem.     

New Multivalue Methods for Differential Algebraic Equations

Multivalue methods are slightly different from the general linear methods John Butcher proposed over 30 years ago. Multivalue methods capable of solving differential algebraic equations have not been developed. In this paper, we have constructed three new multivalue methods for solving DAEs of index 1, 2 or 3, which include multistep methods and multistage methods as special cases. The concept of stiff accuracy will be introduced and convergence results will be given based on the stage order of the methods. These new methods have the diagonal implicit property and thus are cheap to implement and will have order 2 or more for both the differential and algebraic components. We have implemented these methods with fixed step size and they are shown to be very successful on a variety of problems. Some numerical experiments with these methods are presented.     

New crash procedures for large systems of linear constraints

Many algorithms for solving linearly constrained optimization problems maintain sets of basic variables. The calculation of the initial basis is of great importance as it determines to a large extent the amount of computation that will then be required to solve the problem. In this paper, we suggest a number of simple methods for obtaining an initial basis and perform tests to indicate how they perform on a variety of real-life problems.     

Computational results of an interior point algorithm for large scale linear programming

This paper gives computational results for an efficient implementation of a variant of dual projective algorithm for linear programming. The implementation uses the preconditioned conjugate gradient method for computing projections. Our computational experience reported in this paper indicates that this algorithm has potential as an alternative for solving very large LPs in which the direct methods fail due to memory and CPU time requirements. The conjugate gradient algorithm was able to find very accurate directions even when the system was ill-conditioned. The paper also discusses a new mathematical technique called the reciprocal estimates for estimating the primal variables. We have conducted extensive computational experiments on problems representative of large classes of applications of current interest. We have also chosen instances of the problems of future potential interest, which could not be solved in the past due to the weakness of the prior solution methods, but which represent a large class of new applications. The hypergraph model is such an example. Comparison of our implementation with MINOS 5.1 shows that our implementation is orders of magnitude faster than MINOS 5.1 for these problems.     

Economic lot sizes and vehicle scheduling

In this paper a relationship between the vehicle scheduling problem and the dynamic lot size problem is considered. For the latter problem we assume that order quantities for different products can be determined separately. Demand is known over our n-period production planning horizon. For a certain product our task is to decide for each period if it should be produced or not. If it is produced, what is its economic lot size? Our aim here is to minimize the combined set-up and inventory holding costs. The optimal solution of this problem is given by the well-known Wagner-Whitin dynamic lot size algorithm. Also many heuristics for solving this problem have been presented. In this article we point out the analogy of the dynamic lot size problem to a certain vehicle scheduling problem. For solving vehicle scheduling problems the heuristic algorithm developed by Clark and Wright in very often used. Applying this algorithm to the equivalent vehicle scheduling problem we obtain by analogy a simple heuristic algorithm for the dynamic lot size problem. Numerical results indicate that computation time is reduced by about 50% compared to the Wagner-Whitin algorithm. The average cost appears to be approximately 0.8% higher than optimum.     

A SCALED CENTRAL PATH FOR LINEAR PROGRAMMING

1. IntroductionIllterior poillt methods are one of the most illtensively studied topics in optinistion. Thousands of publications have been appeared on inferior point ndhods. A very good recent reviewis given by [4]. Interior point methods have very good theoretical properties including thenice polynomial complexity prOPerty. And more haportat is that numerous applications haveshown that interior point methods are very efficient for solving large sparse linear progr~ngproblemS. Interior poil…     

An efficient hierarchical preconditioner for quadratic discretizations of finite element problems

Higher order finite element discretizations, although providing higher accuracy, are considered to be computationally expensive and of limited use for large‐scale problems. In this paper, we have developed an efficient iterative solver for solving large‐scale quadratic finite element problems. The proposed approach shares some common features with geometric multigrid methods but does not need structured grids to create the coarse problem. This leads to a robust method applicable to finite element problems discretized by unstructured meshes such as those from adaptive remeshing strategies. The method is based on specific properties of hierarchical quadratic bases. It can be combined with an algebraic multigrid (AMG) preconditioner or with other algebraic multilevel block factorizations. The algorithm can be accelerated by flexible Krylov subspace methods. We present some numerical results on the convection–diffusion and linear elasticity problems to illustrate the efficiency and the robustness of the presented algorithm. In these experiments, the performance of the proposed method is compared with that of an AMG preconditioner and other iterative solvers. Our approach requires less computing time and less memory storage. Copyright © 2010 John Wiley & Sons, Ltd.     

一类多商品设施选址问题的基于线性松弛解的启发式方法

多商品设施选址问题是众多设施选址问题中一类重要而困难的问题.在这一问题中,顾客的需求可能包含不止一种商品.对于大规模问题,成熟的商业求解器往往不能在满意的时间内找到高质量的可行解.研究了无容量限制的单货源多商品设施选址问题的一般形式,并给出了应用于此类问题的两个启发式方法.这两个方法基于原选址问题的线性规划松弛问题的最优解,分别通过求解紧问题和邻域搜索的方式给出了原问题的一个可行上界.理论分析指出所提方法可以实施于任意可行问题的实例.数值结果表明所提方法可以显著地提高求解器求解此类设施选址问题的求解效率.     

基于坏单元指示子的p自适应RKDG算法

Runge-Kutta间断Galerkin(RKDG)方法是求解双曲守恒律方程的主流方法之一.很多双曲守恒律问题的规模特别巨大,数值计算求解时需要耗费大量的时间和计算机存储空间.为此我们设计了一个基于坏单元指示子的p自适应RKDG算法,它不仅能够保持原RKDG方法在光滑区域的高阶逼近,而且能够有效降低存储空间.同时,这也为后续进一步开展hp自适应RKDG算法的研究奠定了基础.     

Matching-based preprocessing algorithms to the solution of saddle-point problems in large-scale nonconvex interior-point optimization

Interior-point methods are among the most efficient approaches for solving large-scale nonlinear programming problems. At the core of these methods, highly ill-conditioned symmetric saddle-point problems have to be solved. We present combinatorial methods to preprocess these matrices in order to establish more favorable numerical properties for the subsequent factorization. Our approach is based on symmetric weighted matchings and is used in a sparse direct LDL ^T factorization method where the pivoting is restricted to static supernode data structures. In addition, we will dynamically expand the supernode data structure in cases where additional fill-in helps to select better numerical pivot elements. This technique can be seen as an alternative to the more traditional threshold pivoting techniques. We demonstrate the competitiveness of this approach within an interior-point method on a large set of test problems from the CUTE and COPS sets, as well as large optimal control problems based on partial differential equations. The largest nonlinear optimization problem solved has more than 12 million variables and 6 million constraints.     

基于正弦型光滑打磨函数对0-1规划问题的连续化求解方法

传统的求解0-1规划问题方法大多属于直接离散的解法.现提出一个包含严格转换和近似逼近三个步骤的连续化解法:(1)借助阶跃函数把0-1离散变量转化为[0,1]区间上的连续变量;(2)对目标函数采用逼近折中阶跃函数近光滑打磨函数,约束条件采用线性打磨函数逼近折中阶跃函数,把0-1规划问题由离散问题转化为连续优化模型;(3)利用高阶光滑的解法求解优化模型.该方法打破了特定求解方法仅适用于特定类型0-1规划问题惯例,使求解0-1规划问题的方法更加一般化.在具体求解时,采用正弦型光滑打磨函数来逼近折中阶跃函数,计算效果很好.