General Branch and Bound,and its relation to A1 and AO1

Branch and Bound (B&B) is a problem-solving technique which is widely used for various problems encountered in operations research and combinatorial mathematics. Various heuristic search procedures used in artificial intelligence (AI) are considered to be related to B&B procedures. However, in the absence of any generally accepted terminology for B&B procedures, there have been widely differing opinions regarding the relationships between these procedures and B&B. This paper presents a formulation of B&B general enough to include previous formulations as special cases, and shows how two well-known AI search procedures (A1 and AO1) are special cases of this general formulation.     

Weighted tardiness for the single machine scheduling problem:An examination of precedence theorem productivity

Earlier research by Kanet [11] has provided a number of new theorems for deciding precedence between pairs of jobs for 1∣∣Σw_jT_j. The theorems supplant those of Rinnooy Kan, Lageweg, and Lenstra [16]. Presented here are the results of an analysis of the marginal benefit these new theorems provide over the earlier versions of Rinnooy Kan et al. Results show that the new theorems can provide noteworthy improvements in the ability to discover precedence relations between job pairs. For a large set of problem instances the new theorems uncovered up to 8% more precedence relations than the original theorems of Rinnooy Kan et al. The improvement in the productivity in discovering precedence relations shows to be dependent on the coefficient of variation of the distribution of job weights. Logical application of the theorems is to include them in search procedures and/or heuristic approaches to 1||Σw_jT_j. One such heuristic based on the theorems is provided here in which the solutions to a large set of sample problems are within 8–12% of the optimum.     

Theoretical comparisons of search strategies in branch-and-bound algorithms

Four known search strategies used in branch-and-bound algorithms-heuristic search, depth-first search, best-bound search, and breadth-first search-are theoretically compared from the viewpoint of the performance of the resulting algorithms. Heuristic search includes the other three as special cases. Since heuristic search is determined by a heuristic functionh, we first investigate how the performance of the resulting algorithms depends onh. In particular, we show that heuristic search is stable in the sense that a slight change inh causes only a slight change in its performance. The best and the worst heurstic functions are clarified, and also discussed is how the heuristic functionh should be modified to obtain a branch-and-bound algorithm with an improved performance. Finally, properties and limitations of depth-first search, best-bound search, and breadth-first search viewed as special cases of heuristic search are considered. In particular, it is shown that the stability observed for heuristic search no longer holds for depth-first search.     

Improved LP-based algorithms for the closest string problem

In a recent paper by Liu et al. [Exact algorithm and heuristic for the closest string problem, Computers & Operations Research 2011;38:1513-20], a polynomial time heuristic procedure is proposed for the closest string problem (CSP). Such heuristic called LDDA_LSS is a combination of a previously published approximation algorithm and local search strategies. This paper points out that an instant algorithm deriving a feasible solution directly from the continuous relaxation solution of a standard ILP formulation of CSP already strongly outperforms LDDA_LSS both in terms of solution quality and computing time. Two core based procedures are then proposed that further improve the results of the instant algorithm. Based on these results, we conclude that such LP-based approaches for their efficiency and simplicity should be used as a benchmark for future heuristics on CSP.     

Duality in permutation state spaces and the dual search algorithm

Geometrical symmetries are commonly exploited to improve the efficiency of search algorithms. A new type of symmetry in permutation state spaces, duality, is introduced. Each state has a dual state. Both states share important attributes such as their distance to the goal. Given a state S, it is shown that an admissible heuristic of the dual state of S is an admissible heuristic for S. This provides opportunities for additional heuristic evaluations. An exact definition of the class of problems where duality exists is provided. A new search algorithm, dual search, is presented which switches between the original state and the dual state when it seems likely that the switch will improve the chance of reaching the goal faster. The decision of when to switch is very important and several policies for doing this are investigated. Experimental results show significant improvements for a number of applications, for using the dual state's heuristic evaluation and/or dual search.     

MaxMinMin p-dispersion problem: A variable neighborhood search approach

In this work we have developed a Variable Neighborhood Search (VNS) method in order to solve the MaxMinMin p-dispersion problem, which adds a new type of plateau search mechanism to the classical VNS metaheuristic framework. Besides, several other contributions have been made to the basic VNS heuristic in terms of the ascent and perturbation functions. To the best of our knowledge this is the first application of the VNS to the MaxMinMin problem and our approach, compared to previous methods, finds or improves the results for all of the large-sized benchmarks with low computational efforts. Finding most of the proven optimal solutions in a fraction of a second, the robustness and quality of the solutions and the low complexity of the methods demonstrate the strength of the proposed heuristic solution procedures.     

Extended beam search for non-exhaustive state space analysis

State space explosion is a major problem in both qualitative and quantitative model checking. This article focuses on using beam search, a heuristic search algorithm, for pruning weighted state spaces while generating. The original beam search is adapted to the state space generation setting and two new variants, motivated by practical case studies, are devised. These beam searches have been implemented in the μCRL toolset and applied on several case studies reported in the article.     

A complete proof on the solution procedure for non-instantaneous deteriorating items with permissible delay in payment

Ouyang et al. [Ouyang, L. Y., Wu, K. S., & Yang C. T. (2006). A study on an inventory model for non-instantaneous deteriorating items with permissible delay in payments. Computers & Industrial Engineering, 51, 637–651] present an inventory model for non-instantaneous deteriorating items with permissible delay in payments. They develop some theorems to characterize the optimal solutions and provide an easy-to-use method to find the optimal replenishment cycle time. Although, their inventory models are correct and interesting, processes of arguments to derive those theorems and the easy-to-use method to search for the optimal replenishment cycle time are not complete. So, the main purpose of this paper is to overcome those shortcomings and present complete proofs for Ouyang et al. (2006).     

Diverse subgroup set discovery

Large data is challenging for most existing discovery algorithms, for several reasons. First of all, such data leads to enormous hypothesis spaces, making exhaustive search infeasible. Second, many variants of essentially the same pattern exist, due to (numeric) attributes of high cardinality, correlated attributes, and so on. This causes top-k mining algorithms to return highly redundant result sets, while ignoring many potentially interesting results. These problems are particularly apparent with subgroup discovery (SD) and its generalisation, exceptional model mining. To address this, we introduce subgroup set discovery: one should not consider individual subgroups, but sets of subgroups. We consider three degrees of redundancy, and propose corresponding heuristic selection strategies in order to eliminate redundancy. By incorporating these (generic) subgroup selection methods in a beam search, the aim is to improve the balance between exploration and exploitation. The proposed algorithm, dubbed DSSD for diverse subgroup set discovery, is experimentally evaluated and compared to existing approaches. For this, a variety of target types with corresponding datasets and quality measures is used. The subgroup sets that are discovered by the competing methods are evaluated primarily on the following three criteria: (1) diversity in the subgroup covers (exploration), (2) the maximum quality found (exploitation), and (3) runtime. The results show that DSSD outperforms each traditional SD method on all or a (non-empty) subset of these criteria, depending on the specific setting. The more complex the task, the larger the benefit of using our diverse heuristic search turns out to be.     

Breadth-first heuristic search

Recent work shows that the memory requirements of A* and related graph-search algorithms can be reduced substantially by only storing nodes that are on or near the search frontier, using special techniques to prevent node regeneration, and recovering the solution path by a divide-and-conquer technique. When this approach is used to solve graph-search problems with unit edge costs, we show that a breadth-first search strategy can be more memory-efficient than a best-first strategy. We also show that a breadth-first strategy allows a technique for preventing node regeneration that is easier to implement and can be applied more widely. The breadth-first heuristic search algorithms introduced in this paper include a memory-efficient implementation of breadth-first branch-and-bound search and a breadth-first iterative-deepening A* algorithm that is based on it. Computational results show that they outperform other systematic search algorithms in solving a range of challenging graph-search problems.     

A tabu search heuristic for the hybrid flowshop scheduling with finite intermediate buffers

This paper investigates the hybrid flowshop scheduling with finite intermediate buffers, whose objective is to minimize the sum of weighted completion time of all jobs. Since this problem is very complex and has been proven strongly NP-hard, a tabu search heuristic is proposed. In this heuristic there are two main features. One is that a scatter search mechanism is incorporated to improve the diversity of the search procedure. And the other is that a permutation of N jobs representing their processing order in the first stage instead of a complex complete schedule is used to denote a solution. Computational experiments on randomly generated instances with different structures show that the proposed tabu search heuristic can provide good solutions compared to both the lower bounds and the algorithm proposed for this problem in a lately published literature.     

k-Nearest neighbor searching in hybrid spaces

Little work has been reported in the literature to support k-nearest neighbor (k-NN) searches/queries in hybrid data spaces (HDS). An HDS is composed of a combination of continuous and non-ordered discrete dimensions. This combination presents new challenges in data organization and search ordering. In this paper, we present an algorithm for k-NN searches using a multidimensional index structure in hybrid data spaces. We examine the concept of search stages and use the properties of an HDS to derive a new search heuristic that greatly reduces the number of disk accesses in the initial stage of searching. Further, we present a performance model for our algorithm that estimates the cost of performing such searches. Our experimental results demonstrate the effectiveness of our algorithm and the accuracy of our performance estimation model.     

Topological constraints in search-based robot path planning

There are many applications in motion planning where it is important to consider and distinguish between different topological classes of trajectories. The two important, but related, topological concepts for classifying manifolds that are of importance to us are those of homotopy and homology. In this paper we consider the problem of robot exploration and planning in Euclidean configuration spaces with obstaclees to (a)?identify and represent different homology classes of trajectories; (b)?plan trajectories constrained to certain homology classes or avoiding specified homology classes; and (c)?explore different homotopy classes of trajectories in an environment and determine the least cost trajectories in each class. We exploit theorems from complex analysis and the theory of electromagnetism to solve the problem 2-dimensional and 3-dimensional configuration spaces respectively. Finally, we describe the extension of these ideas to arbitrary D-dimensional configuration spaces. We incorporate these basic concepts to develop a practical graph-search based planning tool with theoretical guarantees by combining integration theory with search techniques, and illustrate it with several examples.     

Depth-first iterative-deepening: An optimal admissible tree search

The complexities of various search algorithms are considered in terms of time, space, and cost of solution path. It is known that breadth-first search requires too much space and depth-first search can use too much time and doesn't always find a cheapest path. A depth-first iterative-deepening algorithm is shown to be asymptotically optimal along all three dimensions for exponential tree searches. The algorithm has been used successfully in chess programs, has been effectively combined with bi-directional search, and has been applied to best-first heuristic search as well. This heuristic depth-first iterative-deepening algorithm is the only known algorithm that is capable of finding optimal solutions to randomly generated instances of the Fifteen Puzzle within practical resource limits.     

Coupled fixed point theorems for mixed monotone mappings and an application to integral equations

In this paper, we extend the coupled fixed point theorems for a mixed monotone mapping F:X×X→X in partially ordered metric spaces established by Bhaskar and Lakshmikantham [T. Gnana Bhaskar, V. Lakshmikantham, Fixed point theorems in partially ordered metric spaces and applications, Nonlinear Anal. TMA 65 (2006) 1379-1393]. An application to nonlinear integral equations is also given to illustrate our results.     

The heuristic concentration-integer and its application to a class of location problems

We propose a new metaheuristic called heuristic concentration-integer (HCI). This metaheuristic is a modified version of the heuristic concentration (HC), oriented to find good solutions for a class of integer programming problems, composed by problems in which p   elements must be selected from a larger set, and each element can be selected more than once. These problems are common in location analysis. The heuristic is explained and general instructions for rewriting integer programming formulations are provided, that make the application of HCI to these problems easier. As an example, the heuristic is applied to the maximal availability location problem (MALP), and the solutions are compared to those obtained using linear programming with branch and bound (LP+B&B)$(\mathrm{LP}+\mathrm{B}\&\mathrm{B})$. For one-third of the instances of MALP, LP+B&B$\mathrm{LP}+\mathrm{B}\&\mathrm{B}$ can be allowed to run until the computer is out of memory without termination, while HCI can find good solutions to the same instances in a reasonable time. In one such case, LP-IP was allowed to run for nearly 100 times longer than HCI and HCI still found a better solution. Furthermore, HCI found the optimal solution in 33.3% of cases and had an objective value gap of less than 1% in 76% of cases. In 18% of the cases, HCI found a solution that is better than LP+B&B. Therefore, in cases where LP+B&B$\mathrm{LP}+\mathrm{B}\&\mathrm{B}$ is unreasonable due to time or memory constraints, HCI is a valuable tool.     

Abstract convexity and generalizations of Himmelberg type fixed-point theorems

In this paper, we study a class KKM(X, Y) of set-valued mappings with KKM property in L-convex spaces introduced by Ben-El-Mechaiekh et al. Several new Himmelberg type fixed-point theorem for mappings with KKM property are established in noncompact locally L-convex spaces. These theorems improve, unify, and generalize many known results in the literatures.     

New Genetic Algorithms Based Approaches to Continuous <Emphasis Type="Italic">p</Emphasis>-Median Problem

We proposed new genetic algorithms (GAs) to address well-known p-median problem in continuous space. Two GA approaches with different replacement procedures are developed to solve this problem. To make the approaches more efficient in finding near-optimal solution two hybrid algorithms are developed combining the new GAs and a traditional local search heuristic. The performance of the newly developed models is compared to that of the traditional alternating location-allocation heuristics by numerical simulation and it is found that the models are effective in finding optimum facility locations.     

Simultaneous feature selection and feature weighting using Hybrid Tabu Search/K-nearest neighbor classifier

Feature selection and feature weighting are useful techniques for improving the classification accuracy of K-nearest-neighbor (K-NN) rule. The term feature selection refers to algorithms that select the best subset of the input feature set. In feature weighting, each feature is multiplied by a weight value proportional to the ability of the feature to distinguish pattern classes. In this paper, a novel hybrid approach is proposed for simultaneous feature selection and feature weighting of K-NN rule based on Tabu Search (TS) heuristic. The proposed TS heuristic in combination with K-NN classifier is compared with several classifiers on various available data sets. The results have indicated a significant improvement in the performance in classification accuracy. The proposed TS heuristic is also compared with various feature selection algorithms. Experiments performed revealed that the proposed hybrid TS heuristic is superior to both simple TS and sequential search algorithms. We also present results for the classification of prostate cancer using multispectral images, an important problem in biomedicine.     

The activity-based aggregate production planning with capacity expansion in manufacturing systems

This paper builds a mixed integer linear programming (MILP) model to mathematically characterize the problem of aggregate production planning (APP) with capacity expansion in a manufacturing system including multiple activity centers. We use the heuristic based on capacity shifting with linear relaxation to solve the model. Two linear relaxations, i.e., a complete linear relaxation (CLR) on all the integer variables and a partial linear relaxation (PLR) on part of the integer variables are investigated and compared in computational experiments. The computational results show that the heuristic based on the capacity shifting with CLR is very fast but yields low-quality solution whereas the capacity shifting with PLR provides high-quality solutions but at the cost of considerable computational time. As a result, we develop a hybrid heuristic combining beam search with capacity shifting, which is capable of producing a high-quality solution within reasonable computational time. The computational experiment on large-scale problems suggests that when solving a practical activity-based APP model with capacity expansion at the industrial level, the capacity shifting with CLR is preferable, and the beam search heuristic could be subsequently utilized as an alternative if the relaxation gap is larger than the acceptable deviation.