The ring-star problem: A new integer programming formulation and a branch-and-cut algorithm

A ring star in a graph is a subgraph that can be decomposed into a cycle (or ring) and a set of edges with exactly one vertex in the cycle. In the minimum ring-star problem (mrsp) the cost of a ring star is given by the sum of the costs of its edges, which vary, depending on whether the edge is part of the ring or not. The goal is to find a ring-star spanning subgraph minimizing the sum of all ring and assignment costs. In this paper we show that the mrsp can be reduced to a minimum (constrained) Steiner arborescence problem on a layered graph. This reduction is used to introduce a new integer programming formulation for the mrsp. We prove that the dual bound generated by the linear relaxation of this formulation always dominates the one provided by an early model from the literature. Based on our new formulation, we developed a branch-and-cut algorithm for the mrsp. On the primal side, we devised a grasp heuristic to generate good upper bounds for the problem. Computational tests with these algorithms were conducted on a benchmark of public domain. In these experiments both our exact and heuristics algorithms had excellent performances, noticeably in dealing with instances whose optimal solution has few vertices in the ring. In addition, we also investigate the minimum spanning caterpillar problem (mscp) which has the same input as the mrsp and admits feasible solutions that can be viewed as ring stars with paths in the place of rings. We present an easy reduction of the mscp to the mrsp, which makes it possible to solve to optimality instances of the former problem too. Experiments carried out with the mscp revealed that our branch-and-cut algorithm is capable to solve to optimality instances with up to 200 vertices in reasonable time.     

A computational comparison of flow formulations for the capacitated location-routing problem

In this paper we present a computational comparison of four different flow formulations for the capacitated location-routing problem. We introduce three new flow formulations for the problem, namely a two-index two-commodity flow formulation, a three-index vehicle-flow formulation and a three-index two-commodity flow formulation. We also consider an existing two-index vehicle-flow formulation and extend it by considering new families of valid inequalities and separation algorithms. We introduce new branch-and-cut algorithms for each of the formulations and compare them on a wide number of instances. Our results show that compact formulations can produce tight gaps and solve many instances quickly, whereas three-index formulations scale better in terms of computing time.     

Algorithms for solutions of extended general mixed variational inequalities and fixed points

In this paper, we introduce and study a new class of extended general nonlinear mixed variational inequalities and a new class of extended general resolvent equations and establish the equivalence between the extended general nonlinear mixed variational inequalities and implicit fixed point problems as well as the extended general resolvent equations. Then by using this equivalent formulation, we discuss the existence and uniqueness of solution of the problem of extended general nonlinear mixed variational inequalities. Applying the aforesaid equivalent alternative formulation and a nearly uniformly Lipschitzian mapping S, we construct some new resolvent iterative algorithms for finding an element of set of the fixed points of nearly uniformly Lipschitzian mapping S which is the unique solution of the problem of extended general nonlinear mixed variational inequalities. We study convergence analysis of the suggested iterative schemes under some suitable conditions. We also suggest and analyze a class of extended general resolvent dynamical systems associated with the extended general nonlinear mixed variational inequalities and show that the trajectory of the solution of the extended general resolvent dynamical system converges globally exponentially to the unique solution of the extended general nonlinear mixed variational inequalities. The results presented in this paper extend and improve some known results in the literature.     

移动传感器网络中的最大价值路径扫描覆盖算法

扫描覆盖是当前移动传感器网络的一个重要覆盖技术,其主要通过规划移动传感器的巡逻路径对事件兴趣点（Points of Interest,POI）进行定期监测,从而以相对于普通覆盖方案更低廉的成本实现对POI监控．研究最大价值路径扫描覆盖,即使用移动传感器扫描覆盖分布在一条路径上的POI集合,使得被覆盖POI的价值总和达到最大．首先设计了一个基于线性规划随机取整的近似算法,通过将问题松弛并刻画为一个线性规划,然后对线性规划最优解取整得到一个扫描覆盖方案．该算法可在O（mn^3.5L）时间内求解,并具有可证明的近似比1-1/e．其次,通过扩展基于贪心策略的集合覆盖算法,设计了一个时间复杂度为O（m²n²）的贪心算法,其主要思想为循环选取一个单位巡逻范围覆盖POI价值最大的传感器．为优化运行时间,基于MVSCP问题的特殊结构将算法时间进一步改进至O（m log m+mn²）．最后,通过仿真实验分析所设计算法的实际性能.实验结果表明,线性规划随机取整算法运行时间低至整数规划算法的百分之一,但其所求解的质量只略低于整数规划算法;改进的贪心算法虽然不具有可证明的近似比,但其实际所求解的质量并不弱于线性规划随机取整算法,并且具有三者中最佳的运行时间．     

A mathematical formulation and complexity considerations for the blocks relocation problem

The blocks relocation problem (BRP) may be defined as follows: given a set of homogeneous blocks stored in a two-dimensional stock, which relocations are necessary to retrieve the blocks from the stock in a predefined order while minimizing the number of those relocations? In this paper, we first prove NP-hardness of the BRP as well as a special case, closing open research questions. Moreover, we propose different solution approaches. First, a mathematical model is presented that provides optimal solutions to the general BRP in cases where instances are small. To overcome such limitation, some realistic assumption taken from the literature is introduced, leading to the definition of a binary linear programming model. In terms of computational time, this approach is reasonably fast to be used to solve medium-sized instances. In addition, we propose a simple heuristic based upon a set of relocation rules. This heuristic is used to generate “good” quality solutions for larger instances in very short computational time, and, consequently, is proposed for tackling problem instances where solutions are required (almost) immediately. Solution quality of the heuristic is measured against optimal solutions obtained using a state-of-the-art commercial solver and both of them are compared with reference results from literature.     

A fast approximation algorithm for solving the complete set packing problem

We study the complete set packing problem (CSPP) where the family of feasible subsets may include all possible combinations of objects. This setting arises in applications such as combinatorial auctions (for selecting optimal bids) and cooperative game theory (for finding optimal coalition structures). Although the set packing problem has been well-studied in the literature, where exact and approximation algorithms can solve very large instances with up to hundreds of objects and thousands of feasible subsets, these methods are not extendable to the CSPP since the number of feasible subsets is exponentially large. Formulating the CSPP as an MILP and solving it directly, using CPLEX for example, is impossible for problems with more than 20 objects. We propose a new mathematical formulation for the CSPP that directly leads to an efficient algorithm for finding feasible set packings (upper bounds). We also propose a new formulation for finding tighter lower bounds compared to LP relaxation and develop an efficient method for solving the corresponding large-scale MILP. We test the algorithm with the winner determination problem in spectrum auctions, the coalition structure generation problem in coalitional skill games, and a number of other simulated problems that appear in the literature.     

Exact join detection for convex polyhedra and other numerical abstractions

Deciding whether the union of two convex polyhedra is itself a convex polyhedron is a basic problem in polyhedral computations; having important applications in the field of constrained control and in the synthesis, analysis, verification and optimization of hardware and software systems. In such application fields though, general convex polyhedra are just one among many, so-called, numerical abstractions, which range from restricted families of (not necessarily closed) convex polyhedra to non-convex geometrical objects. We thus tackle the problem from an abstract point of view: for a wide range of numerical abstractions that can be modeled as bounded join-semilattices—that is, partial orders where any finite set of elements has a least upper bound—we show necessary and sufficient conditions for the equivalence between the lattice-theoretic join and the set-theoretic union. For the case of closed convex polyhedra—which, as far as we know, is the only one already studied in the literature—we improve upon the state-of-the-art by providing a new algorithm with a better worst-case complexity. The results and algorithms presented for the other numerical abstractions are new to this paper. All the algorithms have been implemented, experimentally validated, and made available in the Parma Polyhedra Library.     

Amortized Random Backtracking

Some nonsystematic search algorithms can deal with partial assignments of variables, and then can use constraint propagation techniques. Let us call them NSPA algorithms (Nonsystematic Search with Partial Assignments). For satisfiability or optimization problems, such NSPA algorithms scale a lot better than systematic algorithms. We show in this paper that naive NSPA algorithms have to pay a severe overhead due to the way they visit partial assignments. Amortizing the visits of partial assignments is an important feature which we introduce and analyze in this paper. We also propose a new NSPA algorithm that is amortized: it is called Amortized Random Backtracking, and performs a probabilistic exploration of the search space. It can be seen as an amortized version of iterative sampling and has given very good experimental results on a real life time tabling problem.     

Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem

In this paper new MILP formulations for the multiple allocation p-hub median problem are presented. These require fewer variables and constraints than those traditionally used in the literature. An efficient heuristic algorithm, based on shortest paths, is described. LP based solution methods as well as an explicit enumeration algorithm are developed to obtain exact solutions. Computational results are presented for well known problems from the literature which show that exact solutions can be found in a reasonable amount of computational time. Our algorithms are also benchmarked on a different data set. This data set, which includes problems that are larger than those used in the literature, is based on a postal delivery network and has been treated by the authors in an earlier paper.     

An ensemble of discrete differential evolution algorithms for solving the generalized traveling salesman problem

In this paper, an ensemble of discrete differential evolution algorithms with parallel populations is presented. In a single populated discrete differential evolution (DDE) algorithm, the destruction and construction (DC) procedure is employed to generate the mutant population whereas the trial population is obtained through a crossover operator. The performance of the DDE algorithm is substantially affected by the parameters of DC procedure as well as the choice of crossover operator. In order to enable the DDE algorithm to make use of different parameter values and crossover operators simultaneously, we propose an ensemble of DDE (eDDE) algorithms where each parameter set and crossover operator is assigned to one of the parallel populations. Each parallel parent population does not only compete with offspring population generated by its own population but also the offspring populations generated by all other parallel populations which use different parameter settings and crossover operators. As an application area, the well-known generalized traveling salesman problem (GTSP) is chosen, where the set of nodes is divided into clusters so that the objective is to find a tour with minimum cost passing through exactly one node from each cluster. The experimental results show that none of the single populated variants was effective in solving all the GTSP instances whereas the eDDE performed substantially better than the single populated variants on a set of problem instances. Furthermore, through the experimental analysis of results, the performance of the eDDE algorithm is also compared against the best performing algorithms from the literature. Ultimately, all of the best known averaged solutions for larger instances are further improved by the eDDE algorithm.     

An iterative penalty method for the least squares solution of boundary value problems

This article is concerned with iterative techniques for linear systems of equations arising from a least squares formulation of boundary value problems. In its classical form, the solution of the least squares method is obtained by solving the traditional normal equation. However, for nonsmooth boundary conditions or in the case of refinement at a selected set of interior points, the matrix associated with the normal equation tends to be ill-conditioned. In this case, the least squares method may be formulated as a Powell multiplier method and the equations solved iteratively. Therein we use and compare two different iterative algorithms. The first algorithm is the preconditioned conjugate gradient method applied to the normal equation, while the second is a new algorithm based on the Powell method and formulated on the stabilized dual problem. The two algorithms are first compared on a one-dimensional problem with poorly conditioned matrices. Results show that, for such problems, the new algorithm gives more accurate results. The new algorithm is then applied to a two-dimensional steady state diffusion problem and a boundary layer problem. A comparison between the least squares method of Bramble and Schatz and the new algorithm demonstrates the ability of the new method to give highly accurate results on the boundary, or at a set of given interior collocation points without the deterioration of the condition number of the matrix. Conditions for convergence of the proposed algorithm are discussed. © 1997 John Wiley & Sons, Inc.     

Performance evaluation of evolutionary class of algorithms—An application to 0–1 knapsack problem

The 0–1 knapsack [1] problem is a well-known NP-complete problem. There are different algorithms in the literature to attack this problem, two of them being of specific interest. One is a pseudo polynomial algorithm of order O(nK), K being the target of the problem. This algorithm works unsatisfactorily, as the given target becomes high. In fact, the complexity might become exponential in that case. The other scheme is a fully polynomial time approximation scheme (FPTAS) whose complexity is also polynomial time. The present paper suggests a probabilistic heuristic which is an evolutionary scheme accompanied by the necessary statistical formulation and its theoretical justification. We have identified parameters responsible for the performance of our evolutionary scheme which in turn would keep the option open for improving the scheme.     

Cutting plane versus compact formulations for uncertain (integer) linear programs

Robustness is about reducing the feasible set of a given nominal optimization problem by cutting ??risky?? solutions away. To this end, the most popular approach in the literature is to extend the nominal model with a polynomial number of additional variables and constraints, so as to obtain its robust counterpart. Robustness can also be enforced by adding a possibly exponential family of cutting planes, which typically leads to an exponential formulation where cuts have to be generated at run time. Both approaches have pros and cons, and it is not clear which is the best one when approaching a specific problem. In this paper we computationally compare the two options on some prototype problems with different characteristics. We first address robust optimization à la Bertsimas and Sim for linear programs, and show through computational experiments that a considerable speedup (up to 2 orders of magnitude) can be achieved by exploiting a dynamic cut generation scheme. For integer linear problems, instead, the compact formulation exhibits a typically better performance. We then move to a probabilistic setting and introduce the uncertain set covering problem where each column has a certain probability of disappearing, and each row has to be covered with high probability. A related uncertain graph connectivity problem is also investigated, where edges have a certain probability of failure. For both problems, compact ILP models and cutting plane solution schemes are presented and compared through extensive computational tests. The outcome is that a compact ILP formulation (if available) can be preferable because it allows for a better use of the rich arsenal of preprocessing/cut generation tools available in modern ILP solvers. For the cases where such a compact ILP formulation is not available, as in the uncertain connectivity problem, we propose a restart solution strategy and computationally show its practical effectiveness.     

New integer programming formulations and an exact algorithm for the ordered cutting stock problem

Apart from trim loss minimization, there are many other issues concerning cutting processes that arise in real production systems. One of these is related to the number of stacks that need to be opened near the cutting machines. Many researchers have worked in the last years on cutting stock problems with additional constraints on the number of open stacks. In this paper, we address a related problem: the Ordered Cutting Stock Problem (OCSP). In this case, a stack is opened for every new client's order, and it is closed only when all the items of that order are cut. The OSCP has been introduced recently in the literature. Our aim is to provide further insight into this problem. This paper describes three new integer programming formulations for solving it, and an exact algorithm based on column generation, branch-and-bound and cutting planes. We report on computational experiments on a set of random instances. The results show that good lower bounds can be computed quickly, and that optimal solutions can be found in a reasonable amount of time.     

A new bilevel formulation for the vehicle routing problem and a solution method using a genetic algorithm

The Vehicle Routing Problem (VRP) is one of the most well studied problems in operations research, both in real life problems and for scientific research purposes. During the last 50 years a number of different formulations have been proposed, together with an even greater number of algorithms for the solution of the problem. In this paper, the VRP is formulated as a problem of two decision levels. In the first level, the decision maker assigns customers to the vehicles checking the feasibility of the constructed routes (vehicle capacity constraints) and without taking into account the sequence by which the vehicles will visit the customers. In the second level, the decision maker finds the optimal routes of these assignments. The decision maker of the first level, once the cost of each routing has been calculated in the second level, estimates which assignment is the better one to choose. Based on this formulation, a bilevel genetic algorithm is proposed. In the first level of the proposed algorithm, a genetic algorithm is used for calculating the population of the most promising assignments of customers to vehicles. In the second level of the proposed algorithm, a Traveling Salesman Problem (TSP) is solved, independently for each member of the population and for each assignment to vehicles. The algorithm was tested on two sets of benchmark instances and gave very satisfactory results. In both sets of instances the average quality is less than 1%. More specifically in the set with the 14 classic instances proposed by Christofides, the quality is 0.479% and in the second set with the 20 large scale vehicle routing problems, the quality is 0.826%. The algorithm is ranked in the tenth place among the 36 most known and effective algorithms in the literature for the first set of instances and in the sixth place among the 16 algorithms for the second set of instances. The computational time of the algorithm is decreased significantly compared to other heuristic and metaheuristic algorithms due to the fact that the Expanding Neighborhood Search Strategy is used.     

Transitive sets in Euclidean Ramsey theory

A finite set X in some Euclidean space Rn is called Ramsey if for any k there is a d such that whenever Rd is k-coloured it contains a monochromatic set congruent to X. This notion was introduced by Erd?s, Graham, Montgomery, Rothschild, Spencer and Straus, who asked if a set is Ramsey if and only if it is spherical, meaning that it lies on the surface of a sphere. This question (made into a conjecture by Graham) has dominated subsequent work in Euclidean Ramsey theory.In this paper we introduce a new conjecture regarding which sets are Ramsey; this is the first ever ‘rival’ conjecture to the conjecture above. Calling a finite set transitive if its symmetry group acts transitively—in other words, if all points of the set look the same—our conjecture is that the Ramsey sets are precisely the transitive sets, together with their subsets. One appealing feature of this conjecture is that it reduces (in one direction) to a purely combinatorial statement. We give this statement as well as several other related conjectures. We also prove the first non-trivial cases of the statement.Curiously, it is far from obvious that our new conjecture is genuinely different from the old. We show that they are indeed different by proving that not every spherical set embeds in a transitive set. This result may be of independent interest.     

A heuristic algorithm based on multi-assignment procedures for nurse scheduling

This paper tackles a Nurse Scheduling Problem which consists of generating work schedules for a set of nurses while considering their shift preferences and other requirements. The objective is to maximize the satisfaction of nurses’ preferences and minimize the violation of soft constraints. This paper presents a new deterministic heuristic algorithm, called MAPA (multi-assignment problem-based algorithm), which is based on successive resolutions of the assignment problem. The algorithm has two phases: a constructive phase and an improvement phase. The constructive phase builds a full schedule by solving successive assignment problems, one for each day in the planning period. The improvement phase uses a couple of procedures that re-solve assignment problems to produce a better schedule. Given the deterministic nature of this algorithm, the same schedule is obtained each time that the algorithm is applied to the same problem instance. The performance of MAPA is benchmarked against published results for almost 250,000 instances from the NSPLib dataset. In most cases, particularly on large instances of the problem, the results produced by MAPA are better when compared to best-known solutions from the literature. The experiments reported here also show that the MAPA algorithm finds more feasible solutions compared with other algorithms in the literature, which suggest that this proposed approach is effective and robust.     

Scatter Search for the 0–1 Multidimensional Knapsack Problem

The evolutionary metaheuristic called scatter search has been applied successfully to optimization problems for several years. In this paper, we apply the scatter search technique to the well-known 0–1 multidimensional knapsack problem. We propose a new relaxation-based diversification generator, which produces an initial population with elite solutions. The computational results obtained for a set of classic and correlated instances clearly show that (1) this generator can also be used as a heuristic for solving the multidimensional knapsack problem; (2) using the population produced by our generator as a starting point for the scatter search algorithm leads to better performance. We also enhance the scatter search algorithm by integrating memory and by using adapted intensification phases. Overall, the results are interesting and competitive compared to other population-based algorithms, such as genetic algorithms.      

Algorithms for a multi-level network optimization problem

In this paper we work on a multi-level network optimization problem that integrates into the same model important aspects of: (i) discrete facility location, (ii) topological network design, and (iii) network dimensioning. Potential applications for the model are discussed, stressing its growing importance. The multi-level network optimization problem treated is defined and a mathematical programming formulation is presented. We make use of a branch-and-bound algorithm based on Lagrangean relaxation lower bounds to introduce some new powerful auxiliary algorithms to exactly solve the problem. We conduct a set of computational experiments that indicate the quality of the proposed approach.     

An analytical comparison of the LP relaxations of integer models for the k-club problem

Given an undirected graph G = (V, E), a k-club is a subset of nodes that induces a subgraph with diameter at most k. The k-club problem is to find a maximum cardinality k-club. In this study, we use a linear programming relaxation standpoint to compare integer formulations for the k-club problem. The comparisons involve formulations known from the literature and new formulations, built in different variable spaces. For the case k = 3, we propose two enhanced compact formulations. From the LP relaxation standpoint these formulations dominate all other compact formulations in the literature and are equivalent to a formulation with a non-polynomial number of constraints. Also for k = 3, we compare the relative strength of LP relaxations for all formulations examined in the study (new and known from the literature). Based on insights obtained from the comparative study, we devise a strengthened version of a recursive compact formulation in the literature for the k-club problem (k > 1) and show how to modify one of the new formulations for the case k = 3 in order to accommodate additional constraints recently proposed in the literature.