An Integer Linear Programming Formulation and Branch-and-Cut Algorithm for the Capacitated m-Ring-Star Problem

We study the capacitated m-ring-star problem (CmRSP) that faces the design of minimum cost network structure that connects customers with m rings using a set of ring connections that share a distinguished node (depot), and optionally star connections that connect customers to ring nodes. Ring and star connections have some associated costs. Also, rings can include transit nodes, named Steiner nodes, to reduce the total network cost if possible. The number of customers in each ring-star (ringʼs customers and customer connected to it through star connections) have an upper bound (capacity).These kind of networks are appropriate in optical fiber urban environments. CmRSP is know to be NP-Hard. In this paper we propose an integer linear programming formulation and a branch-and-cut algorithm.     

Algorithms for a stochastic selective travelling salesperson problem

In this paper, the selective travelling salesperson problem with stochastic service times, travel times, and travel costs (SSTSP) is addressed. In the SSTSP, service times, travel times and travel costs are known a priori only probabilistically. A non-negative value of reward for providing service is associated with each customer and there is a pre-specified limit on the duration of the solution tour. It is assumed that not all potential customers can be visited within this tour duration limit, even under the best circumstances. And, thus, a subset of customers must be selected. The objective of the SSTSP is to design an a priori tour that visits each chosen customer once such that the total profit (total reward collected by servicing customers minus travel costs) is maximized and the probability that the total actual tour duration exceeds a given threshold is no larger than a chosen probability value. We formulate the SSTSP as a chance-constrained stochastic program and propose both exact and heuristic approaches for solving it. Computational experiments indicate that the exact algorithm is able to solve small- and moderate-size problems to optimality and the heuristic can provide near-optimal solutions in significantly reduced computing time.     

An iterated local search heuristic for the capacitated prize-collecting travelling salesman problem

This paper considers a variant of the travelling salesman problem named the capacitated prize-collecting travelling salesman problem (CPCTSP), which is derived from the colour-coating production scheduling in a cold rolling mill. The objective of the CPCTSP is to minimize the travel cost and the penalties paid for unvisited customers in such a way that a sufficiently large prize is collected and the demand of the visited customers does not exceed the salesman's capacity. For this problem, we propose an iterated local search (ILS) heuristic adopting guided kick and enhanced dynasearch. The experimental results on randomly generated instances show that the proposed heuristic outperforms the improved tabu search algorithm using frequency-based memory, and the further experimental results on instances collected from real colour-coating production also show that the proposed ILS algorithm is more effective and efficient than the currently adopted manual scheduling method.     

Solving the Passive Optical Network with Fiber Duct Sharing Planning Problem Using Discrete Techniques

Similar to the constrained facility location problem, the passive optical network (PON) planning problem necessitates the search for a subset of deployed facilities (splitters) and their allocated demand points (optical network units) to minimize the overall deployment cost. In this paper we use a mixed integer linear programming formulation stemming from network flow optimization to construct a heuristic based on limiting the total number of interconnecting paths when implementing fiber duct sharing. Then, a disintegration heuristic involving the construction of valid clusters from the output of a k means algorithm, reduce the time complexity while ensuring close to optimal results. The proposed heuristics are then evaluated using a real-world dataset, showing favourable performance.     

Heuristic algorithms for the multi-depot ring-star problem

In this paper, we consider the problem of designing urban optical networks. In particular, given a set of telephone exchanges, we must design a collection of ring-stars, where each ring-star is a cycle composed of a telephone exchange, some customers, some transition points used to save routing costs and customers not on the cycle connected to the cycle by a single edge. The ring topology is chosen in many fiber optic communication networks since it allows to prevent the loss of connection due to a single edge or even a single node failure. The objective is to minimize the total cost of the optical network which is mainly due to the excavation costs. We call this problem Multi-Depot Ring-Star Problem (MDRSP) and we formulate it as an optimization problem in Graph Theory. We present lower bounds and heuristic algorithms for the MDRSP. Computational results on randomly generated instances and real-life datasets are also presented.     

General solutions to the single vehicle routing problem with pickups and deliveries

The single vehicle routing problem with pickups and deliveries (SVRPPD) is defined on a graph in which pickup and delivery demands are associated with the customer vertices. The problem consists of designing a least cost route for a vehicle of capacity Q. Each customer is allowed to be visited once for a combined pickup and delivery, or twice if these two operations are performed separately. This article proposes a mixed integer linear programming model for the SVRPPD. It introduces the concept of general solution which encompasses known solution shapes such as Hamiltonian, double-path and lasso. Classical construction and improvement heuristics, as well as a tabu search heuristic, are developed and tested over several instances. Computational results show that the best solutions generated by the heuristics are frequently non-Hamiltonian and may contain up to two customers visited twice.     

A scatter search heuristic for the capacitated clustering problem

This paper proposes a scatter search-based heuristic approach to the capacitated clustering problem. In this problem, a given set of customers with known demands must be partitioned into p distinct clusters. Each cluster is specified by a customer acting as a cluster center for this cluster. The objective is to minimize the sum of distances from all cluster centers to all other customers in their cluster, such that a given capacity limit of the cluster is not exceeded and that every customer is assigned to exactly one cluster. Computational results on a set of instances from the literature indicate that the heuristic is among the best heuristics developed for this problem.     

The time constrained maximal covering salesman problem

We introduce the time constrained maximal covering salesman problem (TCMCSP) which is the generalization of the covering salesman and orienting problems. In this problem, we are given a set of vertices including a central depot, customer and facility vertices where each facility can supply the demand of some customers within its pre-determined coverage distance. Starting from the depot, the goal is to maximize the total number of covered customers by constructing a length constrained Hamiltonian cycle over a subset of facilities. We propose several mathematical programming models for the studied problem followed by a heuristic algorithm. The developed algorithm takes advantage of different procedures including swap, deletion, extraction-insertion and perturbation. Finally, an integer linear programming based improvement technique is designed to try to improve the quality of the solutions. Extensive computational experiments on a set of randomly generated instances indicate the effectiveness of the algorithm.     

A location–allocation heuristic for the capacitated multi-facility Weber problem with probabilistic customer locations

The capacitated multi-facility Weber problem is concerned with locating m facilities in the Euclidean plane, and allocating their capacities to n customers at minimum total cost. The deterministic version of the problem, which assumes that customer locations and demands are known with certainty, is a non-convex optimization problem and difficult to solve. In this work, we focus on a probabilistic extension and consider the situation where the customer locations are randomly distributed according to a bivariate distribution. We first present a mathematical programming formulation, which is even more difficult than its deterministic version. We then propose an alternate location–allocation local search heuristic generalizing the ideas used originally for the deterministic problem. In its original form, the applicability of the heuristic depends on the calculation of the expected distances between the facilities and customers, which can be done for only very few distance and probability density function combinations. We therefore propose approximation methods which make the method applicable for any distance function and bivariate location distribution.     

k-Interchange procedures for local search in a precedence-constrained routing problem

We develop k-interchange procedures to perform local search in a precedence-constrained routing problem. The problem in question is known in the Transportation literature as the single vehicle many-to-many Dial-A-Ride Problem, or DARP. The DARP is the problem of minimizing the length of the tour traveled by a vehicle to service N customers, each of whom wishes to go from a distinct origin to a distinct destination. The vehicle departs from a specified point and returns to that point upon service of all customers. Precedence constraints in the DARP exist because the origin of each customer must precede his/her destination on the route. As in the interchange procedure of Lin for the Traveling Salesman Problem (TSP), a k-interchange is a substitution of k of the links of an initial feasible DARP tour with k other links, and a DARP tour is k-optimal if it is impossible to obtain a shorter tour by replacing any k of its links by k other links. However, in contrast to the TSP where each individual interchange takes O(1) time, checking whether each individual DARP interchange satisfies the origin-destination precedence constraints normally requires O(N²) time. In this paper we develop a method which still finds the best k-interchange that can be produced from an initial feasible DARP tour in O(N^k) time, the same order of magnitude as in the Lin heuristic for the TSP. This method is then embedded in a breadth-first or a depth-first search procedure to produce a k-optimal DARP tour. The paper focuses on the k = 2 and k = 3 cases. Experience with the procedures is presented. in which k-optimal tours are produced by applying a 2-opt or 3-opt search to initial DARP tours produced either randomly or by a fast O(N²) heuristic. The breadth-first and depth-first search modes are compared. The heuristics are seen to produce very good or near-optimal DARP tours.     

Two criteria to check whether ideals are direct sums of cyclically presented modules

A famous theorem of commutative algebra due to I. M. Isaacs states that “if every prime ideal of R is principal, then every ideal of R is principal”. Therefore, a natural question of this sort is “whether the same is true if one weakens this condition and studies rings in which ideals are direct sums of cyclically presented modules?” The goal of this paper is to answer this question in the case R is a commutative local ring. We obtain an analogue of Isaacs's theorem. In fact, we give two criteria to check whether every ideal of a commutative local ring R is a direct sum of cyclically presented modules, it suffices to test only the prime ideals or structure of the maximal ideal of R. As a consequence, we obtain: if R is a commutative local ring such that every prime ideal of R is a direct sum of cyclically presented R-modules, then R is a Noetherian ring. Finally, we describe the ideal structure of commutative local rings in which every ideal of R is a direct sum of cyclically presented R-modules.     

On Supersets of Wavelet Sets

Considering a single dyadic orthonormal wavelet ψ in L ²(?), it is still an open problem whether the support of $\widehat{\psi}$ always contains a wavelet set. As far as we know, the only result in this direction is that if the Fourier support of a wavelet function is “small” then it is either a wavelet set or a union of two wavelet sets. Without assuming that a set S is the Fourier support of a wavelet, we obtain some necessary conditions and some sufficient conditions for a “small” set S to contain a wavelet set. The main results, which are in terms of the relationship between two explicitly constructed subsets A and B of S and two subsets T ₂ and D ₂ of S intersecting itself exactly twice translationally and dilationally respectively, are (1) if $A\cup B\not\subseteq T_{2}\cap D_{2}$ then S does not contain a wavelet set; and (2) if A∪B?T ₂∩D ₂ then every wavelet subset of S must be in S?(A∪B) and if S?(A∪B) satisfies a “weak” condition then there exists a wavelet subset of S?(A∪B). In particular, if the set S?(A∪B) is of the right size then it must be a wavelet set.     

On optimal right-of-way policies at a single-server station when insertion of idle times is permitted

A general stream of n types of customers arrives at a Single Server station where service is non-preemptive, the server may undergo Poisson breakdowns and insertion of idle times is allowed. If ξ(k) and c(k) are, respectively, the expected service time and sojourn cost per unit time of a type k customer (1?k?n), call k “V.I.P.” type if ξ(k)/c(k) = min_1?i?n[ξ(i)/sbc(i)].We show that any right-of-way service policy can be improved by a policy that grants V.I.P. customers priority over all others, and never inserts idle time when a V.I.P. customer is present.We further show that if the arrival stream is Poisson, the so-called “cμ” priority rule (applied with no delays) is optimal in the class of all service policies, and not just among those of a priority nature.     

Project selection with discounted returns and multiple constraints

This paper considers the problem of selecting a subset of N projects subject to multiple resource constraints. The objective is to maximize the net present value of the total return, where the return from each project depends on its completion time and the previously implemented projects. It is observed that the optimal order (sequence) of projects does not depend on the particular subset of selected projects and hence the overall problem reduces to a multiconstraint nonlinear integer (0–1) problem. This problem can be solved optimally in pseudo-polynomial time using a dynamic programming method but the method is impractical except when the number of constraints, K, is very small. We therefore propose two heuristic methods which require O(N³K) and O(N⁴K) computations, respectively, and evaluate them computationally on 640 problems with up to 100 projects and up to 8 constraints. The results show that the best heuristic is on the average within 0.08% of the optimum for the single-constraint case and within 2.61% of the optimum for the multiconstraint case.     

A Genetic Algorithm for Solving a Capacitated p-Median Problem

Facility-location problems have several applications, such as telecommunications, industrial transportation and distribution. One of the most well-known facility-location problems is the p-median problem. This work addresses an application of the capacitated p-median problem to a real-world problem. We propose a genetic algorithm (GA) to solve the capacitated p-median problem. The proposed GA uses not only conventional genetic operators, but also a new heuristic “hypermutation” operator suggested in this work. The proposed GA is compared with a tabu search algorithm.     

On the support of complete intersection zero-cycles

On an algebraic varietyY ? ? _N we will call complete intersection a 0-cycle when it is the intersection of Y with a codimension n complete intersection of ? _N . We consider the following problem: Let E?Y be given. Does E contain the support of a complete intersection 0-cycle? The two main theorems shown in this article give the answers in some cases: first, a negative answer for E some “big” subset of a singular irreducible algebraic variety; secondly, a positive answer for some “small” subset, on any algebraic variety.     

Gray codes in graphs of subsets

Let G(n,k) be a graph whose vertices are the k-element subsets of an n-set represented as n-tuples of “O's” and “1's” with k “1's”. Two such subsets are adjacent if one can be obtained from the other by switching a “O” and a “1” which are in adjacent positions, where the first and nth positions are also considered adjacent. The problem of finding hamiltonian cycles in G(n,k) is discussed. This may be considered a problem of finding “Gray codes” of the k-element subsets of an n-set. It is shown that no such cycle exists if n and k are both even or if k=2 and n?7 and that such a cycle does exist in all other cases where k?5.     

Rectilinear line segment intersection,layered segment trees,and dynamization

The aim of the present paper is to provide an efficient solution to the following problem: “Given a family of n rectilinear line segments in two-space report all intersections in the family with a query consisting of an arbitrary rectilinear line segment.” We provide an algorithm which takes O(nlog₂n) preprocessing time, o(nlog₂n) space and O(log₂n + k) query time, where k is the number of reported intersections. This solution serves to introduce a powerful new data structure, the layered segment tree, which is of independent interest. Second it yields, by way of recent dynamization techniques, a solution to the on-line version of the above problem, that is the operations INSERT and DELETE and QUERY with a line segment are allowed. Third it also yields a new nonscanning solution to the batched version of the above problem. Finally we apply these techniques to the problem obtained by replacing “line segment” by “rectangle” in the above problem, giving an efficient solution in this case also.     

The construction of all locally compact extensions

The paper presents one of the ways to construct all the locally compact extensions of a given Tychonoff space T. First, there proved the “local” variant of the Stone-C?ech theorem on “completely regular” Riesz spaces X(T) of continuous bounded functions on T with no unit function, in general, but with a collection of local units. In Theorem 1 it is proved that all the functions from X(T) can be “completely regularly” extended on the largest locally compact extension β_xT. Theorem 3 states, that β_xT are presenting, in fact, all the locally compact extensions of T.     

Solutions to open problems of Yang concerning inverse nodal problems

Yang [X. F. Yang, A new inverse nodal problem, Journal of Differential Equations 169 (2001), 633–653] considered a new inverse nodal problem for the Sturm-Liouville operator L(q, α, β) in L ²[0, 1]: an s-dense subset of the nodal set in (0, b) (for any fixed b ∈ ( \(\frac{1}{2}\) , 1]) determines the potential q and boundary data α, β. (1) Since the s-dense condition is stronger than the dense condition, X. F. Yang proposed an open problem “It is open if the boundary parameter α can be determined by a dense subset of the nodal set in (0, b) but not necessarily by an s-dense subset of the nodal set in (0, b).” Cheng et al. have solved this problem and shown that a dense subset of the nodal set in (0, b) completely determines the potential q and boundary data α, β. (2) Another interesting open question: “It remains open if the result holds true for b ∈ (0, \(\frac{1}{2}\) ]” is also proposed by X. F. Yang. In this paper we provide a counterexample to claim that the result does not hold true for b ∈ (0, \(\frac{1}{2}\) ), and a uniqueness theorem for b = \(\frac{1}{2}\) .