Adaptive nonmonotone line search method for unconstrained optimization

In this paper, an adaptive nonmonotone line search method for unconstrained minimization problems is proposed. At every iteration, the new algorithm selects only one of the two directions: a Newton-type direction and a negative curvature direction, to perform the line search. The nonmonotone technique is included in the backtracking line search when the Newton-type direction is the search direction. Furthermore, if the negative curvature direction is the search direction, we increase the steplength under certain conditions. The global convergence to a stationary point with second-order optimality conditions is established. Some numerical results which show the efficiency of the new algorithm are reported.      

Two local search approaches for solving real-life car sequencing problems

The NP-hard problem of car sequencing appears as the heart of the logistic process of many car manufacturers. The subject of the ROADEF’2005 challenge addressed a car sequencing problem proposed by the car manufacturer RENAULT, more complex than the academic problem generally addressed in the literature. This paper describes two local search approaches for this problem. In the first part, a new approach by very large-scale neighborhood search is presented. This approach, designed during the qualification stage preceding the final, is based on an original integer linear programming formulation. The second part is dedicated to the approach which enabled us to win the ROADEF’2005 challenge. Inspired by the latest works on the subject, this one is based on very fast explorations of small neighborhoods. Our contribution here is mainly algorithmic, in particular by showing how much exploiting invariants speeds up the neighborhood evaluation and contributes to the diversification of the search. Finally, the two approaches are compared and discussed through an extensive computational study on RENAULT’s benchmarks. The main conclusion drawn at this point is that sophisticated metaheuristics are useless to solve car sequencing problems. More generally, our victory on ROADEF’2005 challenge demonstrates that algorithmic aspects, sometimes neglected, remain the key ingredients for designing and engineering high-performance local search heuristics.     

A variable neighborhood search for the capacitated arc routing problem with intermediate facilities

The capacitated arc routing problem (CARP) focuses on servicing edges of an undirected network graph. A wide spectrum of applications like mail delivery, waste collection or street maintenance outlines the relevance of this problem. A realistic variant of the CARP arises from the need of intermediate facilities (IFs) to load up or unload the service vehicle and from tour length restrictions. The proposed Variable Neighborhood Search (VNS) is a simple and robust solution technique which tackles the basic problem as well as its extensions. The VNS shows excellent results on four different benchmark sets. Particularly, for all 120 instances the best known solution could be found and in 71 cases a new best solution was achieved.     

Simple ingredients leading to very efficient heuristics for the maximum clique problem

Starting from an algorithm recently proposed by Pullan and Hoos, we formulate and analyze iterated local search algorithms for the maximum clique problem. The basic components of such algorithms are a fast neighbourhood search (not based on node evaluation but on completely random selection) and simple, yet very effective, diversification techniques and restart rules. A detailed computational study is performed in order to identify strengths and weaknesses of the proposed algorithms and the role of the different components on several classes of instances. The tested algorithms are very fast and reliable: most of the DIMACS benchmark instances are solved within very short CPU times. For one of the hardest tests, a new putative optimum was discovered by one of our algorithms. Very good performances were also shown on recently proposed and more difficult instances. It is important to remark that the heuristics tested in this paper are basically parameter free (the appropriate value for the unique parameter is easily identified and was, in fact, the same value for all problem instances used in this paper).     

Density functional studies of molecular structures of N-methyl formamide, N,N-dimethyl formamide, and N,N-dimethyl acetamide

Density functional theory was applied to the calculation of molecular structures of N-methyl formamide (NMF), N,N-dimethyl formamide (DMF), and N,N-dimethyl acetamide (DMA). DFT calculations on NMF, DMF, and DMA were performed using a combination of the local functional of Vosko, Wilk, and Nusair (VWN) with the nonlocal exchange functional of Becke and the nonlocal correlational functional of Lee, Yang, and Parr (BLYP). The adiabatic connection method (ACM) of Becke has also been used, for the first time, for the calculation of molecular structures of NMF, DMF, and DMA. The calculated molecular structures are in excellent agreement with the experimental geometries of NMF and DMA derived from gas-phase electron-diffraction studies. Sparse experimental data on the gas-phase geometry of DMF reported in the literature compares well with the DFT results on DMF. DFT emerges as a powerful method to calculate molecular structures.     

On the numerical solution of the linear complementarity problem

The well-known linear complementarity problem with definite matrices is considered. It is proposed to solve it using a global optimization algorithm in which one of the basic stages is a special local search. The proposed global search algorithm is tested using a variety of randomly generated problems; a detailed analysis of the computational experiment is given.     

Lower bounds on the pathwidth of some grid-like graphs

We present proofs of lower bounds on the node search number of some grid-like graphs including two-dimensional grids, cylinders, tori and a variation we call “orb-webs”. Node search number is equivalent to pathwidth and vertex separation, which are all important graph parameters. Since matching upper bounds are not difficult to obtain, this implies that the pathwidth of these graphs is easily computed, because the bounds are simple functions of the graph dimensions. We also show matching upper and lower bounds on the node search number of equidimensional tori which are one less than the obvious upper bound.     

Effects of initial states on the quantum correlations in the generalized Grover search algorithm

We investigate the correlations between two qubits in the Grover search algorithm with arbitrary initial states by numerical simulation. Using a set of suitable bases, we construct the reduced density matrix and give the numerical expression of correlations relating to the iterations. For different initial states, we obtain the concurrence and quantum discord compared with the success probability in the algorithm. The results show that the initial states affect the correlations and the limit point of the correlations in the searching process. However, the initial states do not influence the whole cyclical trend.     

Wavelength selection framework for classifying food and pharmaceutical samples into multiple classes

Near infrared (NIR) spectroscopy is an efficient, low‐cost analytical technique widely applied to identify the origin of food and pharmaceutical products. NIR spectra‐based classification strategies typically use thousands of equally spaced wavelengths as input information, some of which may not carry relevant information for product classification. When that is the case, the performance of predictive and exploratory multivariate techniques may be undermined by such noisy information. In this paper, we propose an iterative framework for selecting subsets of NIR wavelengths aimed at classifying samples into categories. For that matter, we integrate Principal Components Analysis (PCA) and three classification techniques: k‐Nearest Neighbor (KNN), Probabilistic Neural Network (PNN) and Linear Discriminant Analysis (LDA). PCA is first applied to NIR data, and a wavelength importance index is derived based on the PCA loadings. Samples are then categorized using the wavelength with the highest index and the classification accuracy is calculated; next, the wavelength with the second highest index is inserted into the dataset and a new classification is performed. This forward‐based iterative procedure is carried out until all original wavelengths are inserted into the dataset used for classification. The subset of wavelengths leading to the maximum accuracy is chosen as the recommended subset. Our propositions performed remarkably well when applied to four datasets related to food and pharmaceutical products. Copyright © 2016 John Wiley & Sons, Ltd.     

A UNIVERSAL APPROACH FOR CONTINUOUS OR DISCRETE NONLINEAR PROGRAMMINGS WITH MULTIPLE VARIABLES AND CONSTRAINTS

IntroductionExtensive research works have been published for solving nonlinear mathematicprogramming problems.Nonetheless,it is still difficult to find an effective and universalapproach for general programming problems with multiple design variables and …