The Multiple Trip Vehicle Routing Problem with Backhauls: Formulation and a Two-Level Variable Neighbourhood Search

In this paper a new VRP variant the Multiple Trip Vehicle Routing Problem with Backhauls (MT-VRPB) is investigated. The classical MT-VRP model is extended by including the backhauling aspect. An ILP formulation of the MT-VRPB is first presented and CPLEX results for small and medium size instances are reported. For large instances of the MT-VRPB a Two-Level VNS algorithm is developed. To gain a continuous balanced intensification and diversification during the search process VNS is embedded with the sequential VND and a multi-layer local search approach. The algorithm is tested on a set of new MT-VRPB data instances which we generated. Interesting computational results are presented. The Two-Level VNS produced excellent results when tested on the special variant of the VRPB.     

ILP heuristics and a new exact method for bi-objective 0/1 ILPs: Application to FTTx-network design

Heuristics and metaheuristics are inevitable ingredients of most of the general purpose ILP solvers today, because of their contribution to the significant boost of the performance of exact methods. In the field of bi/multi-objective optimization, to the best of our knowledge, it is still not very common to integrate ILP heuristics into exact solution frameworks. This paper aims to bring a stronger attention of both the exact and metaheuristic communities to still unexplored possibilities for performance improvements of exact and heuristic multi-objective optimization algorithms.We focus on bi-objective optimization problems whose feasible solutions can be described as 0/1 integer linear programs and propose two ILP heuristics, boundary induced neighborhood search (BINS) and directional local branching. Their main idea is to combine the features and explore the neighborhoods of solutions that are relatively close in the objective space. A two-phase ILP-based heuristic framework relying on BINS and directional local branching is introduced. Moreover, a new exact method called adaptive search in objective space (ASOS) is also proposed. ASOS combines features of the ϵ-constraint method with the binary search in the objective space and uses heuristic solutions produced by BINS for guidance. Our new methods are computationally evaluated on two problems of particular relevance for the design of FTTx-networks. Comparison with other known exact methods (relying on the exploration of the objective space) is conducted on a set of realistic benchmark instances representing telecommunication access networks from Germany.     

Kernel search: A general heuristic for the multi-dimensional knapsack problem

In this paper we apply the kernel search framework to the solution of the strongly NP-hard multi-dimensional knapsack problem (MKP). Kernel search is a heuristic framework based on the identification of a restricted set of promising items (kernel) and on the exact solution of ILP sub-problems. Initially, the continuous relaxation of the MKP, solved on the complete set of available items, is used to identify the initial kernel. Then, a sequence of ILP sub-problems are solved, where each sub-problem is restricted to the present kernel and to a subset of other items. Each ILP sub-problem may find better solutions with respect to the previous one and identify further items to insert into the kernel. The kernel search was initially proposed to solve a complex portfolio optimization problem. In this paper we show that the method has general key features that make it appropriate to solve other combinatorial problems using binary variables to model the decisions to select or not items. We adapt the kernel search to the solution of MKP and show that the method is very effective and efficient with respect to known problem-specific approaches. Moreover, the best known values of some MKP benchmark problems from the MIPLIB library have been improved.     

Fast relational learning using bottom clause propositionalization with artificial neural networks

Relational learning can be described as the task of learning first-order logic rules from examples. It has enabled a number of new machine learning applications, e.g. graph mining and link analysis. Inductive Logic Programming (ILP) performs relational learning either directly by manipulating first-order rules or through propositionalization, which translates the relational task into an attribute-value learning task by representing subsets of relations as features. In this paper, we introduce a fast method and system for relational learning based on a novel propositionalization called Bottom Clause Propositionalization (BCP). Bottom clauses are boundaries in the hypothesis search space used by ILP systems Progol and Aleph. Bottom clauses carry semantic meaning and can be mapped directly onto numerical vectors, simplifying the feature extraction process. We have integrated BCP with a well-known neural-symbolic system, C-IL²P, to perform learning from numerical vectors. C-IL²P uses background knowledge in the form of propositional logic programs to build a neural network. The integrated system, which we call CILP++, handles first-order logic knowledge and is available for download from Sourceforge. We have evaluated CILP++ on seven ILP datasets, comparing results with Aleph and a well-known propositionalization method, RSD. The results show that CILP++ can achieve accuracy comparable to Aleph, while being generally faster, BCP achieved statistically significant improvement in accuracy in comparison with RSD when running with a neural network, but BCP and RSD perform similarly when running with C4.5. We have also extended CILP++ to include a statistical feature selection method, mRMR, with preliminary results indicating that a reduction of more than 90 % of features can be achieved with a small loss of accuracy.     

Using the bottom clause and mode declarations in FOL theory revision from examples

Theory revision systems are designed to improve the accuracy of an initial theory, producing more accurate and comprehensible theories than purely inductive methods. Such systems search for points where examples are misclassified and modify them using revision operators. This includes trying to add antecedents to clauses usually following a top-down approach, considering all the literals of the knowledge base. Such an approach leads to a huge search space which dominates the cost of the revision process. ILP Mode Directed Inverse Entailment systems restrict the search for antecedents to the literals of the bottom clause. In this work the bottom clause and mode declarations are introduced in a first-order logic theory revision system aiming to improve the efficiency of the antecedent addition operation and, consequently, also of the whole revision process. Experimental results compared to revision system FORTE show that the revision process is on average 55 times faster, generating more comprehensible theories and still not significantly decreasing the accuracies obtained by the original revision process. Moreover, the results show that when the initial theory is approximately correct, it is more efficient to revise it than learn from scratch, obtaining significantly better accuracies. They also show that using the proposed theory revision system to induce theories from scratch is faster and generates more compact theories than when the theory is induced using a traditional ILP system, obtaining competitive accuracies. This is an extended and revised version of the ILP 2008 paper (Duboc et al. 2008).     

A GRASP with path-relinking heuristic for the survivable IP/MPLS-over-WSON multi-layer network optimization problem

In this paper we deal with the survivable internet protocol (IP)/multi-protocol label switching (MPLS)-over-wavelength switched optical network (WSON) multi-layer network optimization problem (SIMNO). This problem entails planning an IP/MPLS network layer over a photonic mesh infrastructure whilst, at the same time, ensuring the highest availability of services and minimizing the capital expenditures (CAPEX) investments. Such a problem is currently identified as an open issue among network operators, and hence, its solution is of great interest. To tackle SIMNO, we first provide an integer linear programming (ILP) formulation which provides an insight into the complexity of its managing. Then, a greedy randomized adaptive search procedure (GRASP) with path-relinking (PR) together with a biased random-key genetic algorithm (BRKGA) are specifically developed to help solve the problem. The performance of both heuristics is exhaustively tested and compared making use of various network and traffic instances. Numerical experiments show the benefits of using GRASP instead of BRKGA when dealing with highly complex network scenarios. Moreover, we verified that the use of GRASP with PR remarkably improves the basic GRASP algorithm, particularly in real-sized, complex scenarios such as those proposed in this paper.     

Approximate algorithms for static and continuous range queries in mobile navigation

For many years, spatial range search has been applied to computational geometry and multimedia problems to find interest objects within a given radius. Range search query has traditionally been used to return all objects within a given radius. However, having all objects is not necessary, especially when there are already enough objects closer to the query point. Furthermore, expanding the radius may give users better results, especially when there are a lot of objects just outside the search boundary. Therefore, in this paper, we focus on approximate range search, where the query results are approximate, rather than exact. We propose approximate static range search (ARS) which combines two approaches, namely (i) lowerbound approximate range search, and (ii) upperbound approximate range search. Using ARS, we are able to deliver a better performance, together with low false hit and reasonable false miss. We also extend ARS in the context of a continuous query setting, in which the query moves. This is particularly important in spatial databases as a mobile user who invokes the query is moving. In terms of continuous range search, the intention is to find split points—the locations where the query results will be updated. Accordingly, we propose two methods for approximate continuous range search, namely (i) range search minimization, and (ii) split points minimization. Our performance evaluation which compares our methods with the traditional continuous range search shows that our methods considerably reduce the number of split points, thereby improving overall performance.     

Accurate Computation of Orthogonal Fourier-Mellin Moments

Orthogonal Fourier-Mellin moments (OFMMs) suffer from geometric error and the numerical integration error. The geometric error arises when the square image is mapped into a unit disk and the mapping does not become perfect. The numerical integration error arises when the double integration is approximated by the zeroth order summation. In this paper, we propose methods which reduce these errors. The geometric error is reduced by considering the arc-grids lying on the boundary of the unit disk and the square grids lying completely inside the disk. The numerical integration error is reduced by Gaussian numerical integration, for which a simple computational framework is provided. The relative contributions of geometric error and numerical integration error to the total error are also analyzed. It is observed that the geometric error is significant only for the small images whereas the magnitude of numerical integration is significantly high for all image sizes, which increases with the order of moments. A simple computational framework which is similar to the conventional zeroth order approximation is also proposed which not only reduces numerical integration error but also reduces geometric error without considering arc-grids. The improved accuracy of OFMMs are shown to provide better image reconstruction, numerical stability and rotation and scale invariance. Exhaustive experimental results on a variety of real images have shown the efficacy of the proposed methods.     

Automatic integration of Web search interfaces with WISE-Integrator

An increasing number of databases are becoming Web accessible through form-based search interfaces, and many of these sources are database-driven e-commerce sites. It is a daunting task for users to access numerous Web sites individually to get the desired information. Hence, providing a unified access to multiple e-commerce search engines selling similar products is of great importance in allowing users to search and compare products from multiple sites with ease. One key task for providing such a capability is to integrate the Web search interfaces of these e-commerce search engines so that user queries can be submitted against the integrated interface. Currently, integrating such search interfaces is carried out either manually or semiautomatically, which is inefficient and difficult to maintain. In this paper, we present WISE-Integrator - a tool that performs automatic integration of Web Interfaces of Search Engines. WISE-Integrator explores a rich set of special metainformation that exists in Web search interfaces and uses the information to identify matching attributes from different search interfaces for integration. It also resolves domain differences of matching attributes. In this paper, we also discuss how to automatically extract information from search interfaces that is needed by WISE-Integrator to perform automatic interface integration. Our experimental results, based on 143 real-world search interfaces in four different domains, indicate that WISE-Integrator can achieve high attribute matching accuracy and can produce high-quality integrated search interfaces without human interactions.Received: 2 January 2004, Accepted: 25 March 2004, Published online: 12 August 2004Edited by: M. Carey     

Tackling group-to-tree matching in large scale group communications

As a mechanism to efficiently support group communications, multicasting, faces a serious state scalability problem when there are large numbers of groups in the network. Recently, a novel solution called Aggregated Multicast has been proposed, in which multiple groups can share one delivery tree. A key problem in Aggregated Multicast is group-to-tree matching (i.e., assigning groups to proper trees). In this paper, we formally define this problem, and formulate two versions of the problem: static and dynamic. We analyze the static version and prove that it is NP-complete. To tackle this hard problem, we propose three algorithms: one optimal (using Linear Integer Programming, or ILP), one near-optimal (using Greedy method), and one Pseudo-Dynamic algorithm. For the dynamic version, we present a generic dynamic on-line algorithm. Simulation study has been conducted to evaluate the performance of the algorithms. Our results show that: (1) for the static problem, the Greedy algorithm is a feasible solution and its performance is very close to the optimal ILP solution, while the Pseudo-Dynamic algorithm is a good heuristic for many cases where Greedy does not work well; (2) for the dynamic problem, the generic dynamic on-line algorithm is a very practical solution with promising performance and reasonable computation requirement.     

A genetic algorithm approach for multi-product multi-period continuous review inventory models

This paper formulates an approach for multi-product multi-period (Q, r) inventory models that calculates the optimal order quantity and optimal reorder point under the constraints of shelf life, budget, storage capacity, and “extra number of products” promotions according to the ordered quantity. Detailed literature reviews conducted in both fields have uncovered no other study proposing such a multi-product (Q, r) policy that also has a multi-period aspect and which takes all the aforementioned constraints into consideration. A real case study of a pharmaceutical distributor in Turkey dealing with large quantities of perishable products, for whom the demand structure varies from product to product and shows deterministic and variable characteristics, is presented and an easily-applicable (Q, r) model for distributors operating in this manner proposed. First, the problem is modeled as an integer linear programming (ILP) model. Next, a genetic algorithm (GA) solution approach with an embedded local search is proposed to solve larger scale problems. The results indicate that the proposed approach yields high-quality solutions within reasonable computation times.     

G-PaMeLA: A divide-and-conquer approach for joint channel assignment and routing in multi-radio multi-channel wireless mesh networks

The performance of Multi-Radio Multi-Channel Wireless Mesh Networks (MRMC-WMNs) based on the IEEE 802.11 technology depends significantly on how the channels are assigned to the radios and how traffic is routed between the access points and the gateways. In this paper we propose an algorithmic approach to this problem, for which, as far as we know, no optimal polynomial time solutions have been put forward in the literature. The core of our scheme consists of a sequential divide-and-conquer technique which divides the overall Joint Channel Assignment and Routing (JCAR) problem into a number of local optimization sub-problems that are executed sequentially. We propose a generalized scheme called Generalized Partitioned Mesh network traffic and interference aware channeL Assignment (G-PaMeLA), where the number of sub-problems is equal to the maximum number of hops to the gateway, and a customized version which takes advantage of the knowledge of the topology. In both cases each sub-problem is formulated as an Integer Linear Programming (ILP) optimization problem. An optimal solution for each sub-problem can be found by using a branch-and-cut method. The final solution is obtained after a post-processing phase, which improves network connectivity. The divide-and-conquer technique significantly reduces the execution time and makes our solution feasible for an operational WMN. With the help of a detailed packet level simulation, the G-PaMeLA technique is compared with several state-of-the-art JCAR algorithms. Our results highlight that G-PaMeLA performs much better than the others in terms of packet loss rate, collision probability and fairness among traffic flows.     

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.     

Cautious induction: An alternative to clause-at-a-time hypothesis construction in inductive logic programming

Hypotheses constructed by inductive logic programming (ILP) systems are finite sets of definite clauses. Top-down ILP systems usually adopt the following greedy clause-at-a-time strategy to construct such a hypothesis: start with the empty set of clauses and repeatedly add the clause that most improves the quality of the set. This paper formulates and analyses an alternative method for constructing hypotheses. The method, calledcautious induction, consists of a first stage, which finds a finite set of candidate clauses, and a second stage, which selects a finite subset of these clauses to form a hypothesis. By using a less greedy method in the second stage, cautious induction can find hypotheses of higher quality than can be found with a clause-at-a-time algorithm. We have implemented a top-down, cautious ILP system called CILS. This paper presents CILS and compares it to Progol, a top-down clause-at-a-time ILP system. The sizes of the search spaces confronted by the two systems are analysed and an experiment examines their performance on a series of mutagenesis learning problems. Simon Anthony, BEng.: Simon, perhaps better known as “Mr. Cautious” in Inductive Logic Programming (ILP) circles, completed a BEng in Information Engineering at the University of York in 1995. He remained at York as a research student in the Intelligent Systems Group. Concentrating on ILP, his research interests are Cautious Induction and developing number handling techniques using Constraint Logic Programming. Alan M. Frisch, Ph.D.: He is the Reader in Intelligent Systems at the University of York (UK), and he heads the Intelligent Systems Group in the Department of Computer Science. He was awarded a Ph. D. in Computer Science from the University of Rochester (USA) in 1986 and has held faculty positions at the University of Sussex (UK) and the University of Illinois at Urbana-Champaign (USA). For over 15 years Dr. Frisch has been conducting research on a wide range of topics in the area of automated reasoning, including knowledge retrieval, probabilistic inference, constraint solving, parsing as deduction, inductive logic programming and the integration of constraint solvers into automated deduction systems.     

Computational analysis of machine repair problem with unreliable multi-repairmen

This paper considers a multi-repairmen problem comprising of M operating machines with W warm standbys (spares). Both operating and warm standby machines are subject to failures. With a coverage probability c, a failed unit is immediately detected and attended by one of R repairmen if available. If the failed unit is not detected with probability 1−c, the system enters an unsafe state and must be cleared by a reboot action. The repairmen are also subject to failures which result in service (repair) interruptions. The failed repairman resumes service after a random period of time. In addition, the repair rate depends on number of failed machines. The entire system is modeled as a finite-state Markov chain and its steady state distribution is obtained by a recursive matrix approach. The major performance measures are evaluated based on this distribution. Under a cost structure, we propose to use the Quasi-Newton method and probabilistic global search Lausanne method to search for the global optimal system parameters. Numerical examples are presented to demonstrate the effectiveness of our approach in solving a highly complex manufacturing system subject to multiple uncertainties.     

SRLG fault localization using nested m-trails

This paper presents a novel technique called nested m-trail method in all-optical mesh networks for failure localization of any shared risk link group (SRLG) with up to d undirected links. The proposed method decomposes the network topology into virtual cycles and trails, in which sets of m-trails that traverse through a common monitoring node (MN) can be obtained. The nested m-trails are used in the monitoring burst (m-burst) framework, in which the MN can localize any SRLG failure by inspecting the optical bursts traversing through it. An integer linear program (ILP) and a heuristic are proposed for the network decomposition, which are further verified by numerical experiments. We show that the proposed method significantly reduces the required fault localization latency compared to the existing methods.     

Polynomial J-spectral factorization in minimal state space

By a specific choice of matrices in optimal LQ return difference equality, we develop a simple state-space algorithm for polynomial J-spectral factorization. For this purpose we solve a minimal-order algebraic Riccati equation, the order obtained by solving an Integer Linear Programming (ILP) problem. An example that cannot be solved by the existing algorithms illustrates our algorithm.     

Scaling Up Inductive Logic Programming: An Evolutionary Wrapper Approach

Inductive logic programming (ILP) algorithms are classification algorithms that construct classifiers represented as logic programs. ILP algorithms have a number of attractive features, notably the ability to make use of declarative background (user-supplied) knowledge. However, ILP algorithms deal poorly with large data sets (>10⁴ examples) and their widespread use of the greedy set-covering algorithm renders them susceptible to local maxima in the space of logic programs.This paper presents a novel approach to address these problems based on combining the local search properties of an inductive logic programming algorithm with the global search properties of an evolutionary algorithm. The proposed algorithm may be viewed as an evolutionary wrapper around a population of ILP algorithms.The evolutionary wrapper approach is evaluated on two domains. The chess-endgame (KRK) problem is an artificial domain that is a widely used benchmark in inductive logic programming, and Part-of-Speech Tagging is a real-world problem from the field of Natural Language Processing. In the latter domain, data originates from excerpts of the Wall Street Journal. Results indicate that significant improvements in predictive accuracy can be achieved over a conventional ILP approach when data is plentiful and noisy.     

Parallel ILP for distributed-memory architectures

The growth of machine-generated relational databases, both in the sciences and in industry, is rapidly outpacing our ability to extract useful information from them by manual means. This has brought into focus machine learning techniques like Inductive Logic Programming (ILP) that are able to extract human-comprehensible models for complex relational data. The price to pay is that ILP techniques are not efficient: they can be seen as performing a form of discrete optimisation, which is known to be computationally hard; and the complexity is usually some super-linear function of the number of examples. While little can be done to alter the theoretical bounds on the worst-case complexity of ILP systems, some practical gains may follow from the use of multiple processors. In this paper we survey the state-of-the-art on parallel ILP. We implement several parallel algorithms and study their performance using some standard benchmarks. The principal findings of interest are these: (1) of the techniques investigated, one that simply constructs models in parallel on each processor using a subset of data and then combines the models into a single one, yields the best results; and (2) sequential (approximate) ILP algorithms based on randomized searches have lower execution times than (exact) parallel algorithms, without sacrificing the quality of the solutions found. This is an extended version of the paper entitled Strategies to Parallelize ILP Systems, published in the Proceedings of the 15th International Conference on Inductive Logic Programming (ILP 2005), vol. 3625 of LNAI, pp. 136–153, Springer-Verlag.     

Two-link failure protection in WDM mesh networks with p-cycles

In WDM networks, it is important to protect connections against link failures due to the high bandwidth provided by a fiber link. Although many p-cycle based schemes have been proposed for single-link failure protection, protection against two-link failures have not received much attention. In this paper, we propose p-cycle based protection schemes for two-link failures. We formulate an ILP model for the p-cycle design problem for static traffic. We also propose two protection schemes for dynamic traffic, namely SPPP (Shortest Path Pair Protection) and SFPP (Short Full Path Protection). Simulation results show that SFPP is more capacity efficient than SPPP under incremental traffic. Under dynamic traffic, SPPP has lower blocking than SFPP when the traffic load is low and has higher blocking than SFPP when the traffic load is high.