Revisiting the big valley search space structure in the TSP

The solution space of the travelling salesman problem under 2-opt moves has been characterized as having a big-valley structure, in which the evaluation of a tour is positively correlated to the distance of the tour from the global optimum. We examine the big-valley hypothesis more closely and show that while the big-valley structure does appear in much of the solution space, it breaks down around local optima that have solutions whose evaluation is very close to that of the global optimum; multiple funnels appear around local optima with evaluations close to the global optimum. The appearance of multiple funnels explains why certain iterated local search heuristics can quickly find high-quality solutions, but fail to consistently find the global optimum. We then investigate a novel search operator, which is demonstrated to have the ability to escape funnels at evaluations close to the global optimum.     

On Convergence of a P-Algorithm Based on a Statistical Model of Continuously Differentiable Functions

This paper is a study of the one-dimensional global optimization problem for continuously differentiable functions. We propose a variant of the so-called P-algorithm, originally proposed for a Wiener process model of an unknown objective function. The original algorithm has proven to be quite effective for global search, though it is not efficient for the local component of the optimization search if the objective function is smooth near the global minimizer. In this paper we construct a P-algorithm for a stochastic model of continuously differentiable functions, namely the once-integrated Wiener process. This process is continuously differentiable, but nowhere does it have a second derivative. We prove convergence properties of the algorithm.     

Strategic oscillation for the capacitated hub location problem with modular links

The capacitated single assignment hub location problem with modular link capacities is a variant of the classical hub location problem in which the cost of using edges is not linear but stepwise, and the hubs are restricted in terms of transit capacity rather than in the incoming traffic. We propose a metaheuristic algorithm based on strategic oscillation, a methodology originally introduced in the context of tabu search. Our method incorporates several designs for constructive and destructive algorithms, together with associated local search procedures, to balance diversification and intensification for an efficient search. Computational results on a large set of instances show that, in contrast to exact methods that can only solve small instances optimally, our metaheuristic is able to find high-quality solutions on larger instances in short computing times. In addition, the new method, which joins tabu search strategies with strategic oscillation, outperforms the previous tabu search implementation.     

A loose Benders decomposition algorithm for approximating two-stage mixed-integer recourse models

We propose a new class of convex approximations for two-stage mixed-integer recourse models, the so-called generalized alpha-approximations. The advantage of these convex approximations over existing ones is that they are more suitable for efficient computations. Indeed, we construct a loose Benders decomposition algorithm that solves large problem instances in reasonable time. To guarantee the performance of the resulting solution, we derive corresponding error bounds that depend on the total variations of the probability density functions of the random variables in the model. The error bounds converge to zero if these total variations converge to zero. We empirically assess our solution method on several test instances, including the SIZES and SSLP instances from SIPLIB. We show that our method finds near-optimal solutions if the variability of the random parameters in the model is large. Moreover, our method outperforms existing methods in terms of computation time, especially for large problem instances.

     

A facility neighborhood search heuristic for capacitated facility location with single-source constraints and flexible demand

We consider a generalization of the well-known capacitated facility location problem with single source constraints in which customer demand contains a flexible dimension. This work focuses on providing fast and practically implementable optimization-based heuristic solution methods for very large scale problem instances. We offer a unique approach that utilizes a high-quality efficient heuristic within a neighborhood search to address the combined assignment and fixed-charge structure of the underlying optimization problem. We also study the potential benefits of combining our approach with a so-called very large-scale neighborhood search (VLSN) method. As our computational test results indicate, our work offers an attractive solution approach that can be tailored to successfully solve a broad class of problem instances for facility location and similar fixed-charge problems.     

Comparison of independent,stratified and random covering sample schemes in optimization problems

We consider two schemes of global optimization algorithms based on the use of grids. Our main goal is to compare the so-called independent sampling (IS), stratified sampling (SS) and random covering (RC) grids implemented to the estimation problem of the global maximum of a function. The results give an insight on how a decrease of randomness in selection rules for the trial points improves efficiency of global random search algorithms.     

The effect of structural branching on the efficiency of clause learning SAT solving: An experimental study

The techniques for making decisions (branching) play a central role in complete methods for solving structured instances of propositional satisfiability (SAT). Experimental case studies in specific problem domains have shown that in some cases SAT solvers can determine satisfiability faster if branching in the solver is restricted to a subset of the variables at hand. The underlying idea in these approaches is to prune the search space substantially by restricting branching to strong backdoor sets of variables which guarantee completeness of the search. In this paper we present an extensive experimental evaluation of the effects of structure-based branching restrictions on the efficiency of solving structural SAT instances. Previous work is extended in a number of ways. We study state-of-the-art solver techniques, including clause learning and related heuristics. We provide a thorough analysis of the effect of branching restrictions on the inner workings of the solver, going deeper than merely measuring the solution time. Extending previous studies which have focused on input-restricted branching, we also consider relaxed branching restrictions that are based on underlying structural properties of the variables.     

An Ant Colony Optimization Algorithm for Shop Scheduling Problems

We deal with the application of ant colony optimization to group shop scheduling, which is a general shop scheduling problem that includes, among others, the open shop scheduling problem and the job shop scheduling problem as special cases. The contributions of this paper are twofold. First, we propose a neighborhood structure for this problem by extending the well-known neighborhood structure derived by Nowicki and Smutnicki for the job shop scheduling problem. Then, we develop an ant colony optimization approach, which uses a strong non-delay guidance for constructing solutions and which employs black-box local search procedures to improve the constructed solutions. We compare this algorithm to an adaptation of the tabu search by Nowicki and Smutnicki to group shop scheduling. Despite its general nature, our algorithm works particularly well when applied to open shop scheduling instances, where it improves the best known solutions for 15 of the 28 tested instances. Moreover, our algorithm is the first competitive ant colony optimization approach for job shop scheduling instances.     

An Experimental Evaluation of a Scatter Search for the Linear Ordering Problem

Scatter search is a population-based method that has recently been shown to yield promising outcomes for solving combinatorial and nonlinear global optimization problems. Based on formulations originally proposed in the 1960s for combining decision rules and problem constraints, such as in generating surrogate constraints, scatter search uses strategies for combining solution vectors that have proved effective in a variety of problem settings. In this paper, we present a scatter search implementation designed to find high quality solutions for the NP-hard linear ordering problem, which has a significant number of applications in practice. The LOP, for example, is equivalent to the so-called triangulation problem for input-output tables in economics. Our implementation incorporates innovative mechanisms to combine solutions and to create a balance between quality and diversification in the reference set. We also use a tracking process that generates solution statistics disclosing the nature of combinations and the ranks of antecedent solutions that produced the best final solutions. Extensive computational experiments with more than 300 instances establishes the effectiveness of our procedure in relation to approaches previously identified to be best.     

A multi-level search strategy for the 0-1 Multidimensional Knapsack Problem

We propose an exact method based on a multi-level search strategy for solving the 0-1 Multidimensional Knapsack Problem. Our search strategy is primarily based on the reduced costs of the non-basic variables of the LP-relaxation solution. Considering that the variables are sorted in decreasing order of their absolute reduced cost value, the top level branches of the search tree are enumerated following Resolution Search strategy, the middle level branches are enumerated following Branch & Bound strategy and the lower level branches are enumerated according to a simple Depth First Search enumeration strategy. Experimentally, this cooperative scheme is able to solve optimally large-scale strongly correlated 0-1 Multidimensional Knapsack Problem instances. The optimal values of all the 10 constraint, 500 variable instances and some of the 30 constraint, 250 variable instances of the OR-Library were found. These values were previously unknown.     

The variable neighborhood search for the two machine flow shop problem with a passive prefetch

We consider the two machine flow shop scheduling problem with passive loading of the buffer on the second machine. To compute lower bounds for the global optimum, we present four integer linear programming formulations of the problem. Three local search methods with variable neighborhoods are developed for obtaining upper bounds. Some new large neighborhood is designed. Our methods use this neighborhood along with some other well-known neighborhoods. For computational experiments, we present a new class of test instances with known global optima. Computational results indicate a high efficiency of the proposed approach for the new class of instances as well as for other classes of instances of the problem.     

The minimum shift design problem

The min-Shift Design problem (MSD) is an important scheduling problem that needs to be solved in many industrial contexts. The issue is to find a minimum number of shifts and the number of employees to be assigned to these shifts in order to minimize the deviation from workforce requirements. Our research considers both theoretical and practical aspects of the min-Shift Design problem. This problem is closely related to the minimum edge-cost flow problem (MECF), a network flow variant that has many applications beyond shift scheduling. We show that MSD reduces to a special case of MECF and, exploiting this reduction, we prove a logarithmic hardness of approximation lower bound for MSD. On the basis of these results, we propose a hybrid heuristic for the problem, which relies on a greedy heuristic followed by a local search algorithm. The greedy part is based on the network flow analogy, and the local search algorithm makes use of multiple neighborhood relations. An experimental analysis on structured random instances shows that the hybrid heuristic clearly outperforms our previous commercial implementation. Furthermore, it highlights the respective merits of the composing heuristics for different performance parameters.     

求解低秩矩阵恢复问题的非单调交替梯度方向法

低秩矩阵恢复问题作为一类在图像处理和信号数据分析等领域中都十分重要的问题已被广泛研究.本文在交替方向算法的框架下,应用非单调技术,提出一种求解低秩矩阵恢复问题的新算法.该算法在每一步迭代过程中,首先利用一步带有变步长梯度算法同时更新低秩部分的两块变量,然后采用非单调技术更新稀疏部分的变量.在一定的假设条件下,本文证明了...     

Trace-Based Methods for Solving Nonlinear Global Optimization and Satisfiability Problems

In this paper we present a method called NOVEL (Nonlinear Optimization via External Lead) forsolving continuous and discrete global optimization problems. NOVEL addresses the balance between global search and local search, using a trace to aid in identifying promising regions before committing to local searches. We discuss NOVEL for solving continuous constrained optimization problems and show how it can be extended to solve constrained satisfaction and discrete satisfiability problems. We first transform the problem using Lagrange multipliers into an unconstrained version. Since a stable solution in a Lagrangian formulation only guarantees a local optimum satisfying the constraints, we propose a global search phase in which an aperiodic and bounded trace function is added to the search to first identify promising regions for local search. The trace generates an information-bearing trajectory from which good starting points are identified for further local searches. Taking only a small portion of the total search time, this elegant approach significantly reduces unnecessary local searches in regions leading to the same local optimum. We demonstrate the effectiveness of NOVEL on a collection of continuous optimization benchmark problems, finding the same or better solutions while satisfying the constraints. We extend NOVEL to discrete constraint satisfaction problems (CPSs) by showing an efficient transformation method for CSPs and the associated representation in finite-difference equations in NOVEL. We apply NOVEL to solve Boolean satisfiability instances in circuit fault detection and circuit synthesis applications, and show comparable performance when compared to the best existing method.     

Hamilton-Jacobi inequalities in control problems for impulsive dynamical systems

We propose definitions of strong and weak monotonicity of Lyapunov-type functions for nonlinear impulsive dynamical systems that admit vector measures as controls and have trajectories of bounded variation. We formulate infinitesimal conditions for the strong and weak monotonicity in the form of systems of proximal Hamilton-Jacobi inequalities. As an application of strongly and weakly monotone Lyapunov-type functions, we consider estimates for integral funnels of impulsive systems as well as necessary and sufficient conditions of global optimality corresponding to the approach of the canonical Hamilton-Jacobi theory.     

Combining simulated annealing with local search heuristics

We introduce a meta-heuristic to combine simulated annealing with local search methods for CO problems. This new class of Markov chains leads to significantly more powerful optimization methods than either simulated annealing or local search. The main idea is to embed deterministic local search techniques into simulated annealing so that the chain explores only local optima. It makes large, global changes, even at low temperatures, thus overcoming large barriers in configuration space. We have tested this meta-heuristic for the traveling salesman and graph partitioning problems. Tests on instances from public libraries and random ensembles quantify the power of the method. Our algorithm is able to solve large instances to optimality, improving upon local search methods very significantly. For the traveling salesman problem with randomly distributed cities, in a square, the procedure improves on 3-opt by 1.6%, and on Lin-Kernighan local search by 1.3%. For the partitioning of sparse random graphs of average degree equal to 5, the improvement over Kernighan-Lin local search is 8.9%. For both CO problems, we obtain new best heuristics.     

General variable neighborhood search for the uncapacitated single allocation <Emphasis Type="Italic">p</Emphasis>-hub center problem

In this paper we propose a general variable neighborhood search heuristic for solving the uncapacitated single allocation p-hub center problem (USApHCP). For the local search step we develop a nested variable neighborhood descent strategy. The proposed approach is tested on benchmark instances from the literature and found to outperform the state-of-the-art heuristic based on ant colony optimization. We also test our heuristic on large scale instances that were not previously considered as test instances for the USApHCP. Moreover, exact solutions were reached by our GVNS for all instances where optimal solutions are known.     

Improving degree-based variable ordering heuristics for solving constraint satisfaction problems

In this paper, we improved two classical degree-based variable ordering heuristics, \(\frac{\textit{Dom}}{\textit{Ddeg}}\) and \(\frac{\textit{Dom}}{\textit{Wdeg}}\). We propose a method using the summation of constraint tightness in degree-based heuristics. We also propose two methods to calculate dynamic constraint tightness for binary extensional constraints and non-binary intensional constraints respectively. Our work shows how constraint tightness can be practically used to guide search. We performed a number of experiments on some benchmark instances. The results have shown that, the new heuristics improve the classical ones by both computational time and search tree nodes and they are more efficient than some other successful heuristics on the instances where the classical heuristics work well.     

A Cooperative Search Method for the <Emphasis Type="Italic">k</Emphasis>-Coloring Problem

In this paper, a cooperative search method, based on a multi-agent structure is developed to deal with the k-coloring problem. Three agents coordinate using an adaptive memory, a search agent, an intensification agent and a diversification agent. We use the results of a preliminary fitness landscape study to adjust the navigation strategy in the solution space and to fix the search parameters. Our method provides competitive results and it is fast when compared with best existing techniques on instances extracted from the second DIMACS challenge.      

Approximations and Randomization to Boost CSP Techniques

In recent years we have seen an increasing interest in combining constraint satisfaction problem (CSP) formulations and linear programming (LP) based techniques for solving hard computational problems. While considerable progress has been made in the integration of these techniques for solving problems that exhibit a mixture of linear and combinatorial constraints, it has been surprisingly difficult to successfully integrate LP-based and CSP-based methods in a purely combinatorial setting. Our approach draws on recent results on approximation algorithms based on LP relaxations and randomized rounding techniques, with theoretical guarantees, as well on results that provide evidence that the runtime distributions of combinatorial search methods are often heavy-tailed. We propose a complete randomized backtrack search method for combinatorial problems that tightly couples CSP propagation techniques with randomized LP-based approximations. We present experimental results that show that our hybrid CSP/LP backtrack search method outperforms the pure CSP and pure LP strategies on instances of a hard combinatorial problem.