Search

We develop a series of theorems about the graph structure of the classical Minimum Linear Arrangement (MinLA) problem which disclose properties that can be exploited by Multi-Neighborhood Search (MNS) algorithms. As a foundation, we differentiate between swaps of labels attached to adjacent and non-adjacent nodes to create two new neighborhood classes, and show how our theorems yield efficient algorithms for updating key arrays used by local search procedures. In addition, we introduce a class of neighborhoods called set-based neighborhoods supported by a theorem that identifies solutions (labelings) for the MinLA problem in polynomial time that dominate exponential numbers of alternative solutions. The component neighborhoods within this new neighborhood class can be applied in various sequences in conjunction with the first two new neighborhoods introduced. Our results also apply to problems with objectives different than those of MinLA. Finally, our results make it possible to exploit the new neighborhoods according to the user's choice of MNS protocols and alternative local search algorithms. [ABSTRACT FROM AUTHOR]

Ejection chain methods, which include the classical Lin-Kernighan (LK) procedure and the Stem-and-Cycle (S&C) reference structure, have been the source of the currently leading algorithms for large scale symmetric traveling salesman problems (STSP). Although these methods proved highly effective in generating large neighborhoods for symmetric instances, their potential application to the asymmetric setting of the problem (ATSP) introduces new challenges that require special consideration. This article extends our studies on the single-rooted S&C to examine the more advanced doubly-rooted (DR) reference structure. The DR structure, which is allied both to metaheuristics and network optimization, allows more complex network-related (alternating) paths to transition from one tour to another, and offers special advantages for the ATSP. Computational experiments on an extensive testbed exhibits superior performance for the DR neighborhood over its LK counterpart for the ATSP. We additionally show that a straightforward implementation of a DR ejection chain algorithm outperforms the best local search algorithms and obtains solutions comparable to those obtained by the currently most advanced special-purpose algorithms for the ATSP, while requiring dramatically reduced computation time. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(1), 23-33 2016 [ABSTRACT FROM AUTHOR]

This paper develops a new way to help solve difficult linear and nonlinear discrete-optimization decision models more efficiently by introducing a problem-difficulty metric that uses the concept of entropy from information theory. Our entropy metric is employed to devise rules for problem partitioning within an implicit enumeration method, where branching is accomplished based on the subproblem complexity. The only requirement for applying our metric is the availability of (upper) bounds on branching subproblems, which are often computed within most implicit enumeration methods such as branch-and-bound (or cutting-plane-based) methods. Focusing on problems with a relatively small number of constraints, but with a large number of variables, we develop a hybrid partitioning and enumeration solution scheme by combining the entropic approach with the recently developed improved surrogate constraint (ISC) method to produce the new method we call ISCENT. Our computational results indicate that ISCENT can be an order of magnitude more efficient than commercial solvers, such as CPLEX, for convex instances with no more than eight constraints. Furthermore, for nonconvex instances, ISCENT is shown to be significantly more efficient than other standard global solvers. [ABSTRACT FROM AUTHOR]

The quadratic assignment problem (QAP) is a well-known combinatorial optimization problem with a wide variety of applications, prominently including the facility location problem. The acknowledged difficulty of the QAP has made it the focus of many metaheuristic solution approaches. In this paper, we show the benefit of utilizing strategic diversification within the tabu search (TS) framework for the QAP, by incorporating several diversification and multistart TS variants. Computational results for an extensive and challenging set of QAP benchmark test problems demonstrate the ability of our TS variants to improve on a classic TS approach that is one of the principal and most extensively used methods for the QAP. We also show that our new procedures are highly competitive with the best recently introduced methods from the literature, including more complex hybrid approaches that incorporate the classic TS method as a subroutine. [ABSTRACT FROM AUTHOR]