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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

Prize‐collecting set multicovering with submodular pricing

We consider a ground set E and a submodular function acting on it. We first propose a “set multicovering” problem in which the value (price) of any is . We show that the linear program (LP) of this problem can be directly solved by applying a submodular function minimization (SFM) algorithm on the dual LP. However, the main results of this study concern prize‐collecting multicovering with submodular pricing, that is, a more general and more difficult “multicovering” problem in which elements can be left uncovered by paying a penalty. We formulate it as a large‐scale LP (with variables representing all subsets of E) that could be tackled by column generation (CG; for a CG algorithm for “set‐covering” problems with submodular pricing). However, we do not solve this large‐scale LP by CG, but we solve it in polynomial time by exploiting its integrality properties. More exactly, after appropriate restructuring, the dual LP can be transformed into an LP that has been thoroughly studied (as a primal) in the SFM theory. Solving this LP reduces to optimizing a strong map of submodular functions. For this, we use the Fleischer–Iwata framework that optimizes all these functions within the same asymptotic running time as solving a single SFM, that is, in , where and γ is the complexity of one submodular evaluation. Besides solving the problem, the proposed approach can be useful to (a) simultaneously find the best solution of up to functions under strong map relations in time, (b) perform sensitivity analysis in very short time (even at no extra cost), and (c) reveal combinatorial insight into the primal–dual optimal solutions. We present several potential applications throughout the paper, from production planning to combinatorial auctions.     

Polynomial time approximation algorithms for proportionate open‐shop scheduling

This paper deals with the presentation of polynomial time (approximation) algorithms for a variant of open‐shop scheduling, where the processing times are only machine‐dependent. This variant of scheduling is called proportionate scheduling and its applications are used in many real‐world environments. This paper develops three polynomial time algorithms for the problem. First, we present a polynomial time algorithm that solves the problem optimally if , where n and m denote the numbers of jobs and machines, respectively. If, on the other hand, , we develop a polynomial time approximation algorithm with a worst‐case performance ratio of that improves the bound existing for general open‐shops. Next, in the case of , we take into account the problem under consideration as a master problem and convert it into a simpler secondary approximation problem. Furthermore, we formulate both the master and secondary problems, and compare their complexity sizes. We finally present another polynomial time algorithm that provides optimal solution for a special case of the problem where .     

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.     

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.     

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.     

An analysis of parameter adaptation in reactive tabu search

On‐line parameter adaptation schemes are widely used in metaheuristics. They are sometimes preferred to off‐line tuning techniques for two main reasons. First, they promise to achieve good performance even on new instance families that have not been considered during the design or the tuning phase of the algorithm. Second, it is assumed that an on‐line scheme could adapt the algorithm's behaviour to local characteristics of the search space. This paper challenges the second hypothesis by analysing the contribution of the parameter adaptation to the performance of a state‐of‐the‐art reactive tabu search () algorithm for the maximum clique problem. Our experimental analysis shows that this on‐line parameter adaptation scheme converges to good instance‐specific settings for the parameters, and that there is no evidence that it adapts to the local characteristics of the search space. The insights gained from the analysis are confirmed by further experiments with an algorithm for the quadratic assignment problem. Together, the results of the two algorithms shed some new light on the reasons behind the effectiveness of .     

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.     

Computational comparisons of different formulations for the Stackelberg minimum spanning tree game

Let be a given graph whose edge set is partitioned into a set R of red edges and a set B of blue edges, and assume that red edges are weighted and contain a spanning tree of G. Then, the Stackelberg minimum spanning tree game (StackMST) is that of pricing (i.e., weighting) the blue edges in such a way that the total weight of the blue edges selected in a minimum spanning tree of the resulting graph is maximized. In this paper, we present different new mathematical programming formulations for the StackMST based on the properties of the minimum spanning tree problem and the bilevel optimization. We establish a theoretical and empirical comparison between these new formulations that are able to solve random instances of 20–70 nodes. We also test our models on instances in the literature, outperforming previous results.     

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.     

A nonmonotone accelerated Levenberg–Marquardt method for the -eigenvalues of symmetric tensors

The eigenvalues of tensors become more and more important in the numerical multilinear algebra. In this paper, based on the nonmonotone technique, an accelerated Levenberg–Marquardt (LM) algorithm is presented for computing the -eigenvalues of symmetric tensors, in which an LM step and an accelerated LM step are computed at each iteration. We establish the global convergence of the proposed algorithm using properties of symmetric tensors and norms. Under the local error-bound condition, the cubic convergence of the nonmonotone accelerated LM algorithm is derived. Numerical results show that this method is efficient.     

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.     

A biased random‐key genetic algorithm for scheduling heterogeneous multi‐round systems

A divisible load is an amount W of computational work that can be arbitrarily divided into independent chunks of load. In many divisible load applications, the load can be parallelized in a master–worker fashion, where the master distributes the load among a set P of worker processors to be processed in parallel. The master can only send load to one worker at a time, and the transmission can be done in a single round or in multiple rounds. The multi‐round divisible load scheduling problem consists in (a) selecting the subset of workers that will process the load, (b) defining the order in which load will be transmitted to each of them, (c) defining the number m of transmission rounds that will be used, and (d) deciding the amount of load that will be transmitted to each worker at each round , so as to minimize the makespan. We propose a heuristic approach that determines the transmission order, the set of the active processors and the number of rounds by a biased random‐key genetic algorithm. The amount of load transmitted to each worker is computed in polynomial time by closed‐form formulas. Computational results showed that the proposed genetic algorithm outperformed a closed‐form state‐of‐the‐art heuristic, obtaining makespans that are 11.68% smaller on average for a set of benchmark problems.