Greedy Differencing Edge-Contraction heuristic for the Max-Cut problem

The Max-Cut problem is a classical NP-hard problem where the objective is to partition the nodes of an edge-weighted graph in a way that maximizes the sum of edges between the parts. We present a greedy heuristic for solving Max-Cut that combines an Edge-Contraction heuristic with the Differencing Method. We compare the heuristic’s performance to other greedy heuristics using a large and diverse set of problem instances.     

Calculating approximation guarantees for partial set cover of pairs

As a part of a heuristic for the fast detection of new word combinations in text streams, we consider the NP-hard Partial Set Cover of Pairs problem. There we wish to cover a maximum number of pairs of elements by a prescribed number of sets from a given set family. While the approximation ratio of the greedy algorithm for the classic Partial Set Cover problem is completely understood, the same question for covering of pairs is intrinsically more complicated, since the pairs insert some graph-theoretic structure. The best approximation guarantee for the first greedy step can be rephrased as a problem in extremal combinatorics: Assume that we may place a fixed number of subsets of fixed and equal size in a set, how many different pairs of elements can we cover? In this paper we introduce a method to calculate optimal approximation guarantees, and we demonstrate its use on the smallest set families.     

A packet filter placement problem with application to defense against spoofed denial of service attacks

We analyze a problem in computer network security, wherein packet filters are deployed to defend a network against spoofed denial of service attacks. Information on the Internet is transmitted by the exchange of IP packets, which must declare their origin and destination addresses. A route-based packet filter verifies whether the purported origin of a packet is correct with respect to the current route map. We examine the optimization problem of finding a minimum cardinality set of nodes to filter in the network such that no spoofed packet can reach its destination. We prove that this problem is NP-hard, and derive properties that explicitly relate the filter placement problem to the vertex cover problem. We identify topologies and routing policies for which a polynomial-time solution to the minimum filter placement problem exists, and prove that under certain routing conditions a greedy heuristic for the filter placement problem yields an optimal solution.     

On optimal stopping of multidimensional diffusions

This paper develops an approach for solving perpetual discounted optimal stopping problems for multidimensional diffusions, with special emphasis on the $d$-dimensional Wiener process. We first obtain some verification theorems for diffusions, based on the Green kernel representation of the value function. Specializing to the multidimensional Wiener process, we apply the Martin boundary theory to obtain a set of tractable integral equations involving only harmonic functions that characterize the stopping region of the problem in the bounded case. The approach is illustrated through the optimal stopping problem of a $d$-dimensional Wiener process with a positive definite quadratic form reward function.     

A fast meta-heuristic approach for the $$(\alpha ,\beta )-k$$-feature set problem

The feature selection problem aims to choose a subset of a given set of features that best represents the whole in a particular aspect, preserving the original semantics of the variables on the given samples and classes. In 2004, a new approach to perform feature selection was proposed. It was based on a NP-complete combinatorial optimisation problem called (\(\alpha ,\beta \))-k-feature set problem. Although effective for many practical cases, which made the approach an important feature selection tool, the only existing solution method, proposed on the original paper, was found not to work well for several instances. Our work aims to cover this gap found on the literature, quickly obtaining high quality solutions for the instances that existing approach can not solve. This work proposes a heuristic based on the greedy randomised adaptive search procedure and tabu search to address this problem; and benchmark instances to evaluate its performance. The computational results show that our method can obtain high quality solutions for both real and the proposed artificial instances and requires only a fraction of the computational resources required by the state of the art exact and heuristic approaches which use mixed integer programming models.     

有元素类型约束的k-划分问题研究

研究有元素类型约束且每个元素权重为正数的k-集合划分问题,元素类型约束指k-划分后每个集合所包含的元素的类型均不同. 该问题是对k-划分问题(k-partitioning problem)的一个拓展,在一人可拥有多技能执照的行业有广泛的应用背景. 提出基于LPT算法思想的贪婪算法,并得出以下结论: k≤2, 该算法给出最优解: k>2, 最坏情况下的性能比为2-m^-1, 这里m指待分配集合的数量.     

A decomposition approach for a very large scale optimal diversity management problem

This paper focuses on the solution of the optimal diversity management problem formulated as a p-Median problem. The problem is solved for very large scale real instances arising in the car industry and defined on a graph with several tens of thousands of nodes and with several millions of arcs. The particularity is that the graph can consist of several non connected components. This property is used to decompose the problem into a series of p-Median subproblems of a smaller dimension. We use a greedy heuristic and a Lagrangian heuristic for each subproblem. The solution of the whole problem is obtained by solving a suitable assignment problem using a Branch-and-Bound algorithm.Received: June 2004 / Revised version: December 2004MSC classification: 49M29, 90C06, 90C27, 90C60All correspondence to: Antonio SforzaIgor Vasilev: Support for this author was provided by NATO grant CBP.NR.RIG.911258.     

Perturbation resilience for the facility location problem

We analyze a simple local search heuristic for the facility location problem using the notion of perturbation resilience: an instance is $\gamma$-perturbation resilient if all costs can be perturbed by a factor of $\gamma$ without changing the optimal solution.We prove that local search for FLP succeeds in finding the optimal solution for $\gamma$-perturbation resilient instances for $\gamma \ge 3$, and we show that this is tight.     

A greedy randomised search heuristic for time-constrained vehicle scheduling and the incorporation of a learning strategy

In this paper, a greedy randomised heuristic is applied to a complex vehicle-scheduling problem with tight time windows and additional constraints. Two forms of adaptive search are identified, which are referred to as local and global adaptation. In both cases, the calculation of the greedy function is modified by an amount which measures heuristically the quality of the partial solution that is obtained when a decision is made. One use of global adaptation is an approach which is referred to as a learning strategy since it involves an attempt to learn from previous mistakes by an appropriate updating of the greedy function from one run of the heuristic to the next. Such a learning strategy forms the main focus of this paper. Experimental results show that it is potentially a powerful heuristic device, since it greatly enhanced the effectiveness of those methods that had previously been applied to this problem; that is, a greedy randomized heuristic which also incorporated a look-ahead strategy and a version of the well-known savings method. It is suggested that learning strategies of the general type introduced in this paper have potential for application to other combinatorial optimisation problems.     

Economic optimization in a fixed sequence of unreliable inspections

Given a fixed sequence of unreliable inspection operations with known costs and inspection error probabilities of two types (classifying good items as defective and vice versa), we develop a model for selecting the set of inspections that should be activated in order to minimize expected total costs (inspection and penalties). We present an efficient branch and bound algorithm for finding the optimal solution, and two variations of a greedy heuristic that can be applied jointly to provide very good solutions at a O(n²) computational complexity. The conclusions are backed by a factorial experiment that included 1440 problem instances.     

A modified greedy algorithm for dispersively weighted 3-set cover

The set cover problem is that of computing a minimum weight subfamily F^′, given a family F of weighted subsets of a base set U, such that every element of U is covered by some subset in F^′. The k-set cover problem is a variant in which every subset is of size at most k. It has been long known that the problem can be approximated within a factor of by the greedy heuristic, but no better bound has been shown except for the case of unweighted subsets. In this paper we consider approximation of a restricted version of the weighted 3-set cover problem, as a first step towards better approximation of general k-set cover problem, where any two distinct subset costs differ by a multiplicative factor of at least 2. It will be shown, via LP duality, that an improved approximation bound of H(3)-1/6 can be attained, when the greedy heuristic is suitably modified for this case. A key to our algorithm design and analysis is the Gallai-Edmonds structure theorem for maximum matchings.     

Monotonic optimization for sensor cover energy problem

We study the sensor cover energy problem (SCEP) in wireless communication—a difficult nonconvex problem with nonconvex constraints. A local approach based on DC programming called DCA was proposed by Astorino and Miglionico (Optim Lett 10(2):355–368, 2016) for solving this problem. In the present paper, we propose a global approach to (SCEP) based on the theory of monotonic optimization. By using an appropriate reformulation of (SCEP) we propose an algorithm for finding quickly a local optimal solution along with an efficient algorithm for computing a global optimal solution. Computational experiments are reported which demonstrate the practicability of the approach.     

Optimization over the polyhedron determined by a submodular function on a co-intersecting family

A greedy algorithm solves the problem of maximizing a linear objective function over the polyhedron (called the submodular polyhedron) determined by a submodular function on a distributive lattice or a ring family. We generalize the problem by considering a submodular function on a co-intersecting family and give an algorithm for solving it. Here, simple-minded greedy augmentations do not work any more and some complicated augmentations with multiple exchanges are required. We can find an optimal solution by at most 1/2n(n – 1) augmentations, wheren is the number of the variables and we assume a certain oracle for computing multiple exchange capacities.     

Asymptotic Analysis of a Greedy Heuristic for the Multi-Period Single-Sourcing Problem: The Acyclic Case

The multi-period single-sourcing problem that we address in this paper can be used as a tactical tool for evaluating logistics network designs in a dynamic environment. In particular, our objective is to find an assignment of customers to facilities, as well as the location, timing and size of production and inventory levels, that minimizes total assignment, production, and inventory costs. We propose a greedy heuristic, and prove that this greedy heuristic is asymptotically optimal in a probabilistic sense for the subclass of problems where the assignment of customers to facilities is allowed to vary over time. In addition, we prove a similar result for the subclass of problems where each customer needs to be assigned to the same facility over the planning horizon, and where the demand for each customer exhibits the same seasonality pattern. We illustrate the behavior of the greedy heuristic, as well as some improvements where the greedy heuristic is used as the starting point of a local interchange procedure, on a set of randomly generated test problems. These results suggest that the greedy heuristic may be asymptotically optimal even for the cases that we were unable to analyze theoretically.     

The linking set problem: a polynomial special case of the multiple-choice knapsack problem

We consider the linking set problem, which can be seen as a particular case of the multiple-choice knapsack problem. This problem occurs as a subproblem in a decomposition procedure for solving large-scale p-median problems such as the optimal diversity management problem. We show that if a non-increasing diference property of the costs in the linking set problem holds, then the problem can be solved by a greedy algorithm and the corresponding linear gap is null.     

Minimising total average cycle stock subject to practical constraints

Silver and Moon (J Opl Res Soc 50(8) (1999) 789–796) address the problem of minimising total average cycle stock subject to two practical constraints. They provide a dynamic programming formulation for obtaining an optimal solution and propose a simple and efficient heuristic algorithm. Hsieh (J Opl Res Soc 52(4) (2001) 463–470) proposes a 0–1 linear programming approach to the problem and a simple heuristic based on the relaxed 0–1 programming formulation. We show in this paper that the formulation of Hsieh can be improved for solving very large size instances of this inventory problem. So the mathematical approach is interesting for several reasons: the definition of the model is simple, its implementation is immediate by using a mathematical programming language together with a mixed integer programming software and the performance of the approach is excellent. Computational experiments carried out on the set of realistic examples considered in the above references are reported. We also show that the general framework for modelling given by mixed integer programming allows the initial model to be extended in several interesting directions.     

Bounds and Heuristics for the Shortest Capacitated Paths Problem

Given a graph G, the Shortest Capacitated Paths Problem (SCPP) consists of determining a set of paths of least total length, linking given pairs of vertices in G, and satisfying capacity constraints on the arcs of G.We formulate the SCPP as a 0-1 linear program and study two Lagrangian relaxations for getting lower bounds on the optimal value. We then propose two heuristic methods. The first one is based on a greedy approach, while the second one is an adaptation of the tabu search meta-heuristic.     

Pareto optimality and a class of set covering heuristics

The set covering problem has many diverse applications to problems arising in crew scheduling, facility location and other business areas. Since the problem is known to be hard to solve optimally, a number of approximate (heuristic) approaches have been designed for it. These approaches (with one exception) divide into two main groups, greedy heuristics and dual saturation heuristics. We use the concept of a Pareto optimal dual solution to show that an arbitrary dual saturation heuristic has the same worst-case performance guarantee as the two best known heuristics of that type. Moreover, this poor performance level is always attainable by those two heuristics.     

The timetable constrained distance minimization problem

We define the timetable constrained distance minimization problem (TCDMP) which is a sports scheduling problem applicable for tournaments where the total travel distance must be minimized. The problem consists of finding an optimal home-away assignment when the opponents of each team in each time slot are given. We present an integer programming, a constraint programming formulation and describe two alternative solution methods: a hybrid integer programming/constraint programming approach and a branch and price algorithm. We test all four solution methods on benchmark problems and compare the performance. Furthermore, we present a new heuristic solution method called the circular traveling salesman approach (CTSA) for solving the traveling tournament problem. The solution method is able to obtain high quality solutions almost instantaneously, and by applying the TCDMP, we show how the solutions can be further improved.     

Submodular set functions,matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem

For the problem maxlcub;Z(S): S is an independent set in the matroid Xrcub;, it is well-known that the greedy algorithm finds an optimal solution when Z is an additive set function (Rado-Edmonds theorem). Fisher, Nemhauser and Wolsey have shown that, when Z is a nondecreasing submodular set function satisfying Z(?)=0, the greedy algorithm finds a solution with value at least half the optimum value. In this paper we show that it finds a solution with value at least 1/(1 + α) times the optimum value, where α is a parameter which represents the ‘total curvature’ of Z. This parameter satisfies 0≤α≤1 and α=0 if and only if the set function Z is additive. Thus the theorems of Rado-Edmonds and Fisher-Nemhauser-Wolsey are both contained in the bound 1/(1 + α). We show that this bound is best possible in terms of α. Another bound which generalizes the Rado-Edmonds theorem is given in terms of a ‘greedy curvature’ of the set function. Unlike the first bound, this bound can prove the optimality of the greedy algorithm even in instances where Z is not additive. A third bound, in terms of the rank and the girth of X, unifies and generalizes the bounds (e?1)/e known for uniform matroids and $\text{1}\text{2}$ for general matroids. We also analyze the performance of the greedy algorithm when X is an independence system instead of a matroid. Then we derive two bounds, both tight: The first one is [1?(1?α/K)^k]/α where K and k are the sizes of the largest and smallest maximal independent sets in X respectively; the second one is 1/(p+α) where p is the minimum number of matroids that must be intersected to obtain X.