A central path interior point method for nonlinear programming and its local convergence

In this paper, we present an interior point method for nonlinear programming that avoids the use of penalty function or filter. We use an adaptively perturbed primal dual interior point framework to computer trial steps and a central path technique is used to keep the iterate bounded away from 0 and not to deviate too much from the central path. A trust-funnel-like strategy is adopted to drive convergence. We also use second-order correction (SOC) steps to achieve fast local convergence by avoiding Maratos effect. Furthermore, the presented algorithm can avoid the blocking effect. It also does not suffer the blocking of productive steps that other trust-funnel-like algorithm may suffer. We show that, under second-order sufficient conditions and strict complementarity, the full Newton step (combined with an SOC step) will be accepted by the algorithm near the solution, and hence the algorithm is superlinearly local convergent. Numerical experiments results, which are encouraging, are reported.     

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.     

An affine scaling interior trust-region method combining with nonmonotone line search filter technique for linear inequality constrained minimization

This paper proposes an affine scaling interior trust-region method in association with nonmonotone line search filter technique for solving nonlinear optimization problems subject to linear inequality constraints. Based on a Newton step which is derived from the complementarity conditions of linear inequality constrained optimization, a trust-region subproblem subject only to an ellipsoidal constraint is defined by minimizing a quadratic model with an appropriate quadratic function and scaling matrix. The nonmonotone schemes combining with trust-region strategy and line search filter technique can bring about speeding up the convergence progress in the case of high nonlinear. A new backtracking relevance condition is given which assures global convergence without using the switching condition used in the traditional line search filter technique. The fast local convergence rate of the proposed algorithm is achieved which is not depending on any external restoration procedure. The preliminary numerical experiments are reported to show effectiveness of the proposed algorithm.     

Exploiting hardware capabilities in interior point methods

The increase of computer performance continues to support the practice of large-scale optimization. Computers with multiple computing cores and vector processing capabilities are now widely available. We investigate how the recently introduced Advanced Vector Instruction (AVX) set on Intel-compatible architectures can be exploited in interior point methods for linear and nonlinear optimization. We focus on data structures and implementation techniques that utilize the new vector instructions. Our numerical experiments demonstrate that the AVX instruction set provides a significant performance boost in our implementation on large-scale problem that have significant fill-in in the sparse Cholesky factorization, achieving up to 100 gigaflops performance on a standard desktop computer on linear optimization problems for which the required Cholesky factorization is relatively dense.     

An integer programming column generation principle for heuristic search methods

There is an increasing interest in integrating column generation and heuristic approaches to efficiently solve large‐scale discrete optimisation problems. We contribute in this direction. Based on the insights from Lagrangian duality theory, we present an auxiliary problem that can be used for finding near‐optimal solutions to a discrete column‐oriented model. The structure of this auxiliary problem makes it suitable for being addressed with a heuristic search method involving column generation. To this end, we suggest a large neighbourhood search strategy where the repair step is to solve a column generation type subproblem. The suggested search strategy and mathematical models involved need to be tailored to the problem structure. To illustrate important design options and computational behaviour, four applications are studied: bin packing, generalised assignment, a resource allocation problem and the fixed‐charge transportation problem.     

和声蚁群耦合算法求解整数规划的应用研究

针对于求解一般的整数规划问题,提出了和声蚁群耦合算法。采用和声搜索更新种群策略和个体扰动策略改善了蚁群算法过早收敛的问题,同时采用蚁群算法对寻优路径信息素的正反馈来加快和声搜索收敛于最优路径。实验结果表明,相比于蚁群算法和和声搜索算法,新算法大大提高了一般整数规划问题的搜索效率。     

An interior point cutting plane heuristic for mixed integer programming

We explore the use of interior point methods in finding feasible solutions to mixed integer programming. As integer solutions are typically in the interior, we use the analytic center cutting plane method to search for integer feasible points within the interior of the feasible set. The algorithm searches along two line segments that connect the weighted analytic center and two extreme points of the linear programming relaxation. Candidate points are rounded and tested for feasibility. Cuts aimed to improve the objective function and restore feasibility are then added to displace the weighted analytic center until a feasible integer solution is found. The algorithm is composed of three phases. In the first, points along the two line segments are rounded gradually to find integer feasible solutions. Then in an attempt to improve the quality of the solutions, the cut related to the bound constraint is updated and a new weighted analytic center is found. Upon failing to find a feasible integer solution, a second phase is started where cuts related to the violated feasibility constraints are added. As a last resort, the algorithm solves a minimum distance problem in a third phase. The heuristic is tested on a set of problems from MIPLIB and CORAL. The algorithm finds good quality feasible solutions in the first two phases and never requires the third phase.     

A recombination‐based matheuristic for mixed integer programming problems with binary variables

This work introduces a heuristic for mixed integer programming (MIP) problems with binary variables, based on information obtained from differences between feasible solutions as well as solutions from the linear relaxation. This information is used to build a neighborhood that is explored as a sub‐MIP problem. The proposed heuristic is evaluated using 45 problems from the MIPLIB repository. Its performance, in terms of solution improvement over the results obtained after exploring 50,000 nodes of the branch‐and‐bound tree, is compared against that of Solution Polishing, which is another recombination‐based heuristic for MIP problems used within the CPLEX solver; as well as against the solution obtained by running the default CPLEX branch‐and‐cut (B&C) method under a same time limit. The computational results indicate that the proposed method is able to yield results that are significantly better than those obtained by the default CPLEX B&C approach and comparable to those of Solution Polishing in terms of the mean solution quality. This equivalence of expected solution quality, coupled with a simpler implementation, suggests the use of the proposed approach as a possible alternative for improving the quality of solutions in MIP problems.     

Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem

The bipartite unconstrained 0-1 quadratic programming problem (BQP) is a difficult combinatorial problem defined on a complete graph that consists of selecting a subgraph that maximizes the sum of the weights associated with the chosen vertices and the edges that connect them. The problem has appeared under several different names in the literature, including maximum weight induced subgraph, maximum weight biclique, matrix factorization and maximum cut on bipartite graphs. There are only two unpublished works (technical reports) where heuristic approaches are tested on BQP instances. Our goal is to combine straightforward search elements to balance diversification and intensification in both exact (branch and bound) and heuristic (iterated local search) frameworks. We perform a number of experiments to test individual search components and also to create new benchmarks when comparing against the state of the art, which the proposed procedure outperforms.     

A trust-region algorithm combining line search filter technique for nonlinear constrained optimization

In this paper, we propose a trust-region algorithm in association with line search filter technique for solving nonlinear equality constrained programming. At current iteration, a trial step is formed as the sum of a normal step and a tangential step which is generated by trust-region subproblem and the step size is decided by interior backtracking line search together with filter methods. Then, the next iteration is determined. This is different from general trust-region methods in which the next iteration is determined by the ratio of the actual reduction to the predicted reduction. The global convergence analysis for this algorithm is presented under some reasonable assumptions and the preliminary numerical results are reported.     

A Hybrid approach for integer programming combining genetic algorithms, linear programming and ordinal optimization

Hybrid methods are promising tools in integer programming, as they combine the best features of different methods in a complementary fashion. This paper presents such a framework, integrating the notions of genetic algorithm, linear programming, and ordinal optimization in an effort to shorten computation times for large and/or difficult integer programming problems. Capitalizing on the central idea of ordinal optimization and on the learning capability of genetic algorithms to quickly generate good feasible solutions, and then using linear programming to solve the problem that results from fixing the integer part of the solution, one may be able to obtain solutions that are close to optimal. Indeed ordinal optimization guarantees the quality of the solutions found. Numerical testing on a real-life complex scheduling problem demonstrates the effectiveness and efficiency of this approach.     

Multiobjective 0‐1 integer programming for the use of sugarcane residual biomass in energy cogeneration

It is well known that Brazil is the largest producer of sugarcane in the world. Nevertheless, a great concern exists about the crop system used, because the most common practice is manual harvesting with prior straw burning. The Brazilian authorities have approved a law prohibiting the burning of sugarcane crop residue before harvesting. However, mechanized harvesting creates the new problem of having to deal with the residue. Many studies have indeed proposed the use of this residue as an energy source. A major difficulty in using this residue is how to economically transport sugarcane harvest biomass from a farm to a processing centre. Besides transport costs, another concern is knowing whether the energy generated by the straw offsets the energy used, in terms of fuel, in the process. This study proposes a multiobjective integer linear programming optimization model to choose sugarcane varieties so as to minimize costs in the use of crop residue and simultaneously maximize the energy balance in such a process. Computational results are presented and discussed.     

Discrete dynamic convexized method for nonlinearly constrained nonlinear integer programming

This paper considers the nonlinearly constrained nonlinear integer programming problem over a bounded box. An auxiliary function is constructed based on a penalty function. By increasing the value of a parameter, minimization of the function by a discrete local search method can escape successfully from a previously converged discrete local minimizer. An algorithm is designed based on minimizing the auxiliary function with increasing values of the parameter. Numerical experiments show that the algorithm is robust and efficient.     

A multi-start iterated local search with tabu list and path relinking for the two-echelon location-routing problem

The two-echelon location-routing problem (LRP-2E) is raised by the design of transportation networks with two types of trips: first-level trips serving from one main depot a set of satellite depots, to be located, and second-level trips supplying customers from these satellites. In the proposed multi-start iterated local search (MS-ILS), three greedy randomized heuristics are used cyclically to get initial solutions. Each ILS run alternates between two search spaces: LRP-2E solutions, and travelling salesman (TSP) tours covering the main depot and the customers. The number of iterations allotted to a run is reduced whenever a known solution (stored in a tabu list) is revisited. MS-ILS can be reinforced by a path-relinking procedure (PR), used internally for intensification, as post-optimization, or both. On two sets with 24 and 30 LRP-2E instances, MS-ILS outperforms on average two GRASP algorithms and adding PR brings a further improvement. Our metaheuristic also surpasses a tabu search on 30 instances for a more general problem with several main depots. It is still effective on a particular case, the capacitated location-routing problem (CLRP): In a comparison with four published metaheuristics, only one (LRGTS, Prins et al., 2007) does better.     

A two state reduction based dynamic programming algorithm for the bi-objective 0–1 knapsack problem

In this paper, we present a dynamic programming (DP) algorithm for the multi-objective 0–1 knapsack problem (MKP) by combining two state reduction techniques. One generates a backward reduced-state DP space (BRDS) by discarding some states systematically and the other reduces further the number of states to be calculated in the BRDS using a property governing the objective relations between states. We derive the condition under which the BRDS is effective to the MKP based on the analysis of solution time and memory requirements. To the authors’ knowledge, the BRDS is applied for the first time for developing a DP algorithm. The numerical results obtained with different types of bi-objective instances show that the algorithm can find the Pareto frontier faster than the benchmark algorithm for the large size instances, for three of the four types of instances conducted in the computational experiments. The larger the size of the problem, the larger improvement over the benchmark algorithm. Also, the algorithm is more efficient for the harder types of bi-objective instances as compared with the benchmark algorithm.     

An alternating direction method for second-order conic programming

An alternating direction dual augmented Lagrangian method for second-order cone programming (SOCP) problems is proposed. In the algorithm, at each iteration it first minimizes the dual augmented Lagrangian function with respect to the dual variables, and then with respect to the dual slack variables while keeping the other two variables fixed, and then finally it updates the Lagrange multipliers. Convergence result is given. Numerical results demonstrate that our method is fast and efficient, especially for the large-scale second-order cone programming.     

模糊时间窗VRP的动态规划和禁忌搜索混合算法

为优化具有模糊时间窗的车辆路径问题,以物流配送成本和顾客平均满意度为目标,建立了多目标数学规划模型。基于Pareto占优的理论给出了求解多目标优化问题的并行多目标禁忌搜索算法,算法中嵌入同时优化顾客满意度的动态规划方法,运用阶段划分,把原问题分解为关于紧路径的优化子问题。对模糊时间窗为线性分段函数形式和非线性凹函数形式的隶属度函数,分别提出了次梯度有限迭代算法和次梯度中值迭代算法来优化顾客的最优开始服务时间。通过Solomon的标准算例,与次梯度投影算法的比较验证了动态规划方法优化服务水平的有效性,与主流的NSGA-II算法的对比实验表明了该研究提出的多目标禁忌搜索算法的优越性。     

JAMES: An object‐oriented Java framework for discrete optimization using local search metaheuristics

This paper describes the Java Metaheuristics Search framework (JAMES, v1.1): an object‐oriented Java framework for discrete optimization using local search algorithms that exploits the generality of such metaheuristics by clearly separating search implementation and application from problem specification. A wide range of generic local searches are provided, including (stochastic) hill climbing, tabu search, variable neighbourhood search and parallel tempering. These can be applied to any user‐defined problem by plugging in a custom neighbourhood for the corresponding solution type. Using an automated analysis workflow, the performance of different search algorithms can be compared in order to select an appropriate optimization strategy. Implementations of specific components are included for subset selection, such as a predefined solution type, generic problem definition and several subset neighbourhoods used to modify the set of selected items. Additional components for other types of problems (e.g. permutation problems) are provided through an extensions module which also includes the analysis workflow. In comparison with existing Java metaheuristics frameworks that mainly focus on population‐based algorithms, JAMES has a much lower memory footprint and promotes efficient application of local searches by taking full advantage of move‐based evaluation. Releases of JAMES are deployed to the Maven Central Repository so that the framework can easily be included as a dependency in other Java applications. The project is fully open source and hosted on GitHub. More information can be found at http://www.jamesframework.org . Copyright © 2016 John Wiley & Sons, Ltd.