Two dependency constrained spanning tree problems

We introduce two spanning tree problems with dependency constraints, where an edge can be chosen only if at least one or all edges in its dependency set are also chosen, respectively. The dependencies on the input graph G are described by a digraph D whose vertices are the edges of G, and the in‐neighbors of a vertex are its dependency set. We show that both problems are NP‐hard even if G is an outerplanar chordal graph with diameter 2 or maximum degree 3, and D is a disjoint union of arborescences of height 2. We also prove that the problems are inapproximable to a factor, unless , and that they are W[2]‐hard. As an attempt to narrow the hardness gap, we present two polynomial cases. We test integer linear programming formulations based on directed cut (DCUT) and Miller–Tucker–Zemlin (MTZ) constraints. Computational experiments are reported.     

Constrained shortest path tour problem: models,valid inequalities,and Lagrangian heuristics

The constrained shortest path tour problem (CSPTP) is an NP‐hard combinatorial optimization problem defined on a connected directed graph , where V is the set of nodes and A is the set of nonnegative weighted arcs. Given two distinct nodes , an integer value , and node disjoint subsets , , the CSPTP aims at finding the shortest trail from s to t while visiting at least one node in every subset , in this order. In this paper, we perform a comparative analysis between two integer programming (IP) models for the problem. We also propose valid inequalities and a Lagrangian‐based heuristic framework. Branch‐and‐bound algorithms from the literature, as well as a metaheuristic approach, are used for comparison. Extensive computational experiments carried out on benchmark data sets show the effective use of valid inequalities and the quality of bounds obtained by the Lagrangian framework. Because benchmark instances do not require a great computational effort of IP models in the sense that their optimality is reached at the root node of the CPLEX branch‐and‐cut search tree, we introduce new challenging CSPTP instances for which our solution approaches outperform existing ones for the problem.     

Comparison of metaheuristics for the k‐labeled spanning forest problem

In this paper, we study the k‐labeled spanning forest (kLSF) problem in which an undirected graph whose edges are labeled and an integer‐positive value are given; the aim is to find a spanning forest of the input graph with the minimum number of connected components and the upper bound on the number of labels. The problem is related to the minimum labeling spanning tree problem and has several applications in the real world. In this paper, we compare several metaheuristics to solve this NP‐hard problem. In particular, the proposed intelligent variable neighborhood search (VNS) shows excellent performance, obtaining high‐quality solutions in short computational running time. This approach integrates VNS with other complementary approaches from machine learning, statistics, and experimental algorithmics, in order to produce high‐quality performance and completely automate the resulting optimization strategy.     

Min‐degree constrained minimum spanning tree problem: complexity,properties, and formulations

This paper addresses a new combinatorial problem, the Min‐Degree Constrained Minimum Spanning Tree (md‐MST), that can be stated as: given a weighted undirected graph with positive costs on the edges and a node‐degrees function , the md‐MST is to find a minimum cost spanning tree T of G, where each node i of T either has at least a degree of or is a leaf node. This problem is closely related to the well‐known Degree Constrained Minimum Spanning Tree (d‐MST) problem, where the degree constraint is an upper bound instead. The general NP‐hardness for the md‐MST is established and some properties related to the feasibility of the solutions for this problem are presented, in particular we prove some bounds on the number of internal and leaf nodes. Flow‐based formulations are proposed and computational experiments involving the associated Linear Programming (LP) relaxations are presented.     

Linear-time algorithms for eliminating claws in graphs

Since many -complete graph problems are polynomial-time solvable when restricted to claw-free graphs, we study the problem of determining the distance of a given graph to a claw-free graph, considering vertex elimination a measure. Claw-free Vertex Deletion (CFVD) consists of determining the minimum number of vertices to be removed from a graph such that the resulting graph is claw-free. Although CFVD is -hard in general and recognizing claw-free graphs is still a challenge, where the current best deterministic algorithm for a graph G consists of performing executions of the best algorithm for matrix multiplication, we present linear-time algorithms for CFVD on weighted block graphs and weighted graphs with bounded treewidth. Furthermore, we show that this problem on forests can be solved in linear time by a simpler algorithm, and we determine the exact values for full k-ary trees. On the other hand, we show that CFVD is -hard even when the input graph is a split graph. We also show that the problem is hard to be approximated within any constant factor better than 2, assuming the unique games conjecture.     

A branch‐and‐price approach to k‐clustering minimum biclique completion problem

We consider the problem of finding k‐bipartite subgraphs, called “clusters,” in a bipartite graph , such that each vertex i of S appears in exactly one of the subgraphs, every vertex j of T appears in each cluster in which at least one of its neighbors appears, and the total number of edges needed to complete each cluster (i.e. to become a biclique) is minimized. This problem has been shown to be strongly NP‐hard and is known as the k‐clustering minimum biclique completion problem. It has been applied to bundling channels for multicast transmissions. The application consists of finding k‐multicast sessions that partition the set of demands, given a set of demands of services from clients. Each service should belong to a single multicast session, while each client can appear in more than one session. We extend previous work by developing a branch‐and‐price algorithm that embeds a new metaheuristic based on variable neighborhood infeasible search and a branching rule that exploits the problem structure. The metaheuristic can also efficiently solve the pricing subproblem. In addition to the random instances used in the literature, we present structured instances generated using the MovieLens dataset collected by the GroupLens Research Project. Extensive computational results show that our branch‐and‐price algorithm outperforms the approaches proposed in the literature.     

Graph fragmentation problem: analysis and synthesis

Vulnerability metrics play a key role in the understanding of cascading failures and target/random attacks to a network. The graph fragmentation problem (GFP) is the result of a worst‐case analysis of a random attack. We can choose a fixed number of individuals for protection, and a nonprotected target node immediately destroys all reachable nodes. The goal is to minimize the expected number of destroyed nodes in the network. In this paper, we address the GFP by several approaches: metaheuristics, approximation algorithms, polytime methods for specific instances, and exact methods for small instances. The computational complexity of the GFP is included in our analysis, where we formally prove that the corresponding decision version of the problem is ‐complete. Furthermore, a strong inapproximability result holds: there is no polynomial approximation algorithm with factor lower than 5/3, unless . This promotes the study of specific instances of the problem for tractability and/or exact methods in exponential time. As a synthesis, we propose new vulnerability/connectivity metrics and an interplay with game theory using a closely related combinatorial problem called component order connectivity.     

On computing the 2‐diameter ‐constrained K ‐reliability of networks

This article considers a communication network modeled by a graph and a distinguished set of terminal nodes . We assume that the nodes never fail, but the edges fail randomly and independently with known probabilities. The classical K ‐reliability problem computes the probability that the subnetwork is composed only by the surviving edges in such a way that all terminals communicate with each other. The d ‐diameter ‐constrained K ‐reliability generalization also imposes the constraint that each pair of terminals must be the extremes of a surviving path of approximately d length. It allows modeling communication network situations in which limits exist on the acceptable delay times or on the amount of hops that packets can undergo. Both problems have been shown to be NP ‐hard, yet the complexity of certain subproblems remains undetermined. In particular, when , it was an open question whether the instances with were solvable in polynomial time. In this paper, we prove that when and is a fixed parameter (i.e. not an input) the problem turns out to be polynomial in the number of nodes of the network (in fact linear). We also introduce an algorithm to compute these cases in such time and also provide two numerical examples.     

Computational and structural analysis of the contour of graphs

Let be a finite, simple, and connected graph. The closed interval of a set is the set of all vertices lying on a shortest path between any pair of vertices of S. The set S is geodetic if . The eccentricity of a vertex v is the number of edges in the greatest shortest path between v and any vertex w of G. A vertex v is a contour vertex if no neighbor of v has eccentricity greater than v. The contour of G is the set formed by the contour vertices of G. We consider two problems: the problem of determining whether the contour of a graph class is geodetic; the problem of determining if there exists a graph such that is not geodetic. We obtain a sufficient condition that is useful for both problems; we prove a realization theorem related to problem and show two infinite families such that is not geodetic. Using computational tools, we establish the minimum graphs for which is not geodetic; and show that all graphs with , and all bipartite graphs with , are such that is geodetic.     

Mixed coordination mechanisms for scheduling games on hierarchical machines

In this paper, we study scheduling games under mixed coordination mechanisms on hierarchical machines. The two scheduling policies involved are ‐ and ‐, where ‐ (resp., ‐) policy sequences jobs in nondecreasing order of their hierarchies, and jobs of the same hierarchy in nonincreasing (resp., nondecreasing) order of their processing times. We first show the existence of a Nash equilibrium. Then we present the price of anarchy and the price of stability for the games with social costs of minimizing the makespan and maximizing the minimum machine load. All the bounds given in this paper are tight.     

Crowdfunding mechanism comparison when product quality is uncertain

Many entrepreneurs have recently employed crowdfunding to raise money. Although there are several crowdfunding mechanisms, there is no clear dominant strategy for the type of mechanisms that should be adopted by the entrepreneur. This paper compares two commonly used mechanisms of crowdfunding by building a two‐person and two‐period model where the entrepreneur first makes the decision then two consumers follow. The all‐or‐nothing () mechanism allows entrepreneurs to set a funding target and keep nothing unless the goal is achieved. In contrast, entrepreneurs under the keep‐it‐all () mechanism must also set a target and keep any funds regardless of whether the goal has been achieved. To compare these two mechanisms, we assume that customers are not sure about the quality of the product, which is very common in reward‐based crowdfunding. Using a unified model, our results show that large or poorly scalable projects are more likely to choose the mechanism.     

A parallel variable neighborhood search approach for the obnoxious p‐median problem

The obnoxious p‐median problem consists of selecting p locations, considered facilities, in a way that the sum of the distances from each nonfacility location, called customers, to its nearest facility is maximized. This is an ‐hard problem that can be formulated as an integer linear program. In this paper, we propose the application of a variable neighborhood search (VNS) method to effectively tackle this problem. First, we develop new and fast local search procedures to be integrated into the basic VNS methodology. Then, some parameters of the algorithm are tuned in order to improve its performance. The best VNS variant is parallelized and compared with the best previous methods, namely branch and cut, tabu search, and GRASP over a wide set of instances. Experimental results show that the proposed VNS outperforms previous methods in the state of the art. This fact is finally confirmed by conducting nonparametric statistical tests.     

The provably good parallel seeding algorithms for the k-means problem with penalties

As a classic NP-hard problem in machine learning and computational geometry, the k-means problem aims to partition the given points into k sets to minimize the within-cluster sum of squares. The k-means problem with penalties (k-MPWP), as a generalizing problem of the k-means problem, allows a point that can be either clustered or penalized with some positive cost. In this paper, we mainly apply the parallel seeding algorithm to the k-MPWP, and show sufficient analysis to bound the expected solution quality in the case where both the number of iterations and the number of points sampled in each iteration can be given arbitrarily. The approximate guarantee can be obtained as , where is a polynomial function involving the maximal ratio M between the penalties. On one hand, this result can be viewed as a further improvement on the parallel algorithm for k-MPWP given by Li et al., where the number of iterations depends on other factors. On the other hand, our result also generalizes the one solving the k-means problem presented by Bachem et al., because k-MPWP is a variant of the k-means problem. Moreover, we present a numerical experiment to show the effectiveness of the parallel algorithm for k-means with penalties.     

The daily routing and scheduling problem of home health care: based on costs and participants’ preference satisfaction

Improving the level of service and reducing total costs are the most important objectives for the decision support system of home health care companies. But these objectives are often in conflict. In this study, we aim to minimize the total costs and maximize the participants’ preference satisfaction simultaneously. The problem is formulated as a bi-objective mixed-integer linear programming model that considers the skill requirements of patients, hard time windows for the service start time, and the working duration of a nurse. Patient preference satisfaction captures the nurse skill level and nurse–patient familiarity, and nurses’ preference satisfaction captures the overtime duration. To solve this problem, a novel hybrid elitist nondominated sorting genetic algorithm (hybrid NSGA-II) is developed by embedding a local search algorithm into the basic NSGA-II framework. Computation results on a set of benchmarking instances show that the developed hybrid NSGA-II can obtain approximate Pareto-optimal solutions within a shorter computation time when compared with the -constraint method for small instances; it can also perform better than the basic NSGA-II and SPEA-II with the size increasing for middle and large instances. Using a small instance, this study also analyzes the problem properties and the trade-off between total costs and participants’ preference satisfaction.     

The generalized discrete ‐centroid problem

The ‐centroid problem or leader–follower problem is generalized considering different customer choice rules where a customer may use facilities belonging to different firms, if the difference in travel distance (or time) is small enough. Assuming essential goods, some particular customer choice rules are analyzed. Linear programming formulations for the generalized ‐medianoid and ‐centroid problems are presented and an exact solution approach is applied. Some computational examples are included.     

Solving the edge‐disjoint paths problem using a two‐stage method

There exists a wide variety of network problems where several connection requests occur simultaneously. In general, each request is attended by finding a route in the network, where the origin and destination of such a route are those hosts that wish to establish a connection for information exchange. As is well documented in the related literature, the exchange of information through disjoint routes increases the effective bandwidth, velocity, and the probability of receiving the corresponding information. The definition of disjoint paths may refer to nodes, edges, or both. One of the most studied variants is the one where disjointness implies not to share edges. This optimization problem is usually known as the maximum edge‐disjoint paths problem. This ‐hard optimization problem has applications in real‐time communications, very large scale integration design, scheduling, bin packing, or load balancing. The proposed approach hybridizes an integer linear programming formulation of the problem with an evolutionary algorithm. Empirical results using 174 previously reported instances show that the proposed procedure compares favorably to previous metaheuristics for this problem. We confirm the significance of the results by conducting nonparametric statistical tests.     

Full complexity analysis of the diameter‐constrained reliability

Let be a simple graph with nodes and links, a subset of “terminals,” a vector , and a positive integer d, called “diameter.” We assume that nodes are perfect but links fail stochastically and independently, with probabilities . The “diameter‐constrained reliability” (DCR) is the probability that the terminals of the resulting subgraph remain connected by paths composed of d links, or less. This number is denoted by . The general DCR computation belongs to the class of ‐hard problems, since it subsumes the problem of computing the probability that a random graph is connected. The contributions of this paper are twofold. First, a full analysis of the computational complexity of DCR subproblems is presented in terms of the number of terminal nodes and the diameter d. Second, we extend the class of graphs that accept efficient DCR computation. In this class, we include graphs with bounded co‐rank, graphs with bounded genus, planar graphs, and, in particular, Monma graphs, which are relevant to robust network design.     

Solving diameter‐constrained minimum spanning tree problems by constraint programming

The diameter‐constrained minimum spanning tree problem consists in finding a minimum spanning tree of a given graph, subject to the constraint that the maximum number of edges between any two vertices in the tree is bounded from above by a given constant. This problem typically models network design applications where all vertices communicate with each other at a minimum cost, subject to a given quality requirement. We propose alternative formulations using constraint programming that circumvent weak lower bounds yielded by most mixed‐integer programming formulations. Computational results show that the proposed formulation, combined with an appropriate search procedure, solves larger instances and is faster than other approaches in the literature.     

VNS and second order heuristics for the min-degree constrained minimum spanning tree problem

Given an undirected graph with weights associated with its edges, the min-degree constrained minimum spanning tree (md$\mathit{md}$-MST) problem consists in finding a minimum spanning tree of the given graph, imposing minimum degree constraints in all nodes except the leaves. This problem was recently proposed in Almeida et al. [Min-degree constrained minimum spanning tree problem: Complexity, proprieties and formulations. Operations Research Center, University of Lisbon, Working-paper no. 6; 2006], where its theoretical complexity was characterized and showed to be NP$\mathit{NP}$-hard.     

A biased random‐key genetic algorithm for single‐round divisible load scheduling

A divisible load is an amount W of computational work that can be arbitrarily divided into chunks and distributed among a set P of worker processors to be processed in parallel. Divisible load applications occur in many fields of science and engineering. They can be parallelized in a master‐worker fashion, but they pose several scheduling challenges. The divisible load scheduling problem consists in (a) selecting a subset of active workers, (b) defining the order in which the chunks will be transmitted to each of them, and (c) deciding the amount of load that will be transmitted to each worker , with , so as to minimize the makespan, i.e., the total elapsed time since the master began to send data to the first worker, until the last worker stops its computations. In this work, we propose a biased random‐key genetic algorithm for solving the divisible load scheduling problem. Computational results show that the proposed heuristic outperforms the best heuristic in the literature.