On inverse traveling salesman problems

The inverse traveling salesman problem belongs to the class of ??inverse combinatorial optimization?? problems. In an inverse combinatorial optimization problem, we are given a feasible solution for an instance of a particular combinatorial optimization problem, and the task is to adjust the instance parameters as little as possible so that the given solution becomes optimal in the new instance. In this paper, we consider a variant of the inverse traveling salesman problem, denoted by ITSP _W,A , by taking into account a set W of admissible weight systems and a specific algorithm. We are given an edge-weighted complete graph (an instance of TSP), a Hamiltonian tour (a feasible solution of TSP) and a specific algorithm solving TSP. Then, ITSP _W,A , is the problem to find a new weight system in W which minimizes the difference from the original weight system so that the given tour can be selected by the algorithm as a solution. We consider the cases ${W \in \{\mathbb{R}^{+m}, \{1, 2\}^m , \Delta\}}$ where ?? denotes the set of edge weight systems satisfying the triangular inequality and m is the number of edges. As for algorithms, we consider a local search algorithm 2-opt, a greedy algorithm closest neighbor and any optimal algorithm. We devise both complexity and approximation results. We also deal with the inverse traveling salesman problem on a line for which we modify the positions of vertices instead of edge weights. We handle the cases ${W \in \{\mathbb{R}^{+n}, \mathbb{N}^n\}}$ where n is the number of vertices.     

Approximating the minimum clique cover and other hard problems in subtree filament graphs

Subtree filament graphs are the intersection graphs of subtree filaments in a tree. This class of graphs contains subtree overlap graphs, interval filament graphs, chordal graphs, circle graphs, circular-arc graphs, cocomparability graphs, and polygon-circle graphs. In this paper we show that, for circle graphs, the clique cover problem is NP-complete and the h-clique cover problem for fixed h is solvable in polynomial time. We then present a general scheme for developing approximation algorithms for subtree filament graphs, and give approximation algorithms developed from the scheme for the following problems which are NP-complete on circle graphs and therefore on subtree filament graphs: clique cover, vertex colouring, maximum k-colourable subgraph, and maximum h-coverable subgraph.     

Approximation algorithms for <Emphasis Type="Italic">k</Emphasis>-echelon extensions of the one warehouse multi-retailer problem

In this paper, we consider k-echelon extensions of the deterministic one warehouse multi-retailer problem. We give constant factor approximation algorithms for some of these extensions when k is fixed. We focus first on the case without backorders and we give a \((2k-1)\)-approximation algorithm under general assumptions on the evolution of the holding costs as products move toward the final customers. We then improve this result to a k-approximation when the holding costs are monotonically non-increasing or non-decreasing (which is a natural situation in practice). Finally we address problems with backorders: we give a 3-approximation for the one-warehouse multi-retailer problem with backlog and a k-approximation algorithm for the k-level Joint Replenishment Problem with backlog (a variant where inventory can only be kept at the final retailers). Ours results are the first constant approximation algorithms for those problems. In addition, we demonstrate the potential of our approach on a practical case. Our preliminary experiments show that the average optimality gap is around 15%.     

混合图上最小-最大圈覆盖问题的近似算法

考虑一个混合图上的最小-最大圈覆盖问题.给定一个正整数k和一个混合加权图G=(V E,A),这里V表示顶点集,E表示边集,A表示弧集.E中的每条边和A中的每条弧关联一个权重.问题的要求是确定k个环游,使得这k个环游能够经过A中的所有弧.目标是极小化最大环游的权重.该问题是运筹学和计算机科学中一个重要的组合优化问题,它和...     

Shorter tours by nicer ears: 7/5-Approximation for the graph-TSP, 3/2 for the path version,and 4/3 for two-edge-connected subgraphs

We prove new results for approximating the graph-TSP and some related problems. We obtain polynomial-time algorithms with improved approximation guarantees. For the graph-TSP itself, we improve the approximation ratio to 7=5. For a generalization, the minimum T-tour problem, we obtain the first nontrivial approximation algorithm, with ratio 3=2. This contains the s-t-path graph-TSP as a special case. Our approximation guarantee for finding a smallest 2-edge-connected spanning subgraph is 4=3. The key new ingredient of all our algorithms is a special kind of ear-decomposition optimized using forest representations of hypergraphs. The same methods also provide the lower bounds (arising from LP relaxations) that we use to deduce the approximation ratios.     

Multicriteria tour planning for mobile healthcare facilities in a developing country

A multiobjective combinatorial optimization (MOCO) formulation for the following location-routing problem in healthcare management is given: For a mobile healthcare facility, a closed tour with stops selected from a given set of population nodes has to be found. Tours are evaluated according to three criteria: (i) An economic efficiency criterion related to the tour length, (ii) the criterion of average distances to the nearest tour stops corresponding to p-median location problem formulations, and (iii) a coverage criterion measuring the percentage of the population unable to reach a tour stop within a predefined maximum distance. Three algorithms to compute approximations to the set of Pareto-efficient solutions of the described MOCO problem are developed. The first uses the P-ACO technique, and the second and the third use the VEGA and the MOGA variant of multiobjective genetic algorithms, respectively. Computational experiments for the Thiès region in Senegal were carried out to evaluate the three approaches on real-world problem instances.     

Approximability results for the resource-constrained project scheduling problem with a single type of resources

In this paper, we consider the well-known resource-constrained project scheduling problem. We give some arguments that already a special case of this problem with a single type of resources is not approximable in polynomial time with an approximation ratio bounded by a constant. We prove that there exist instances for which the optimal makespan values for the non-preemptive and the preemptive problems have a ratio of O(logn), where n is the number of jobs. This means that there exist instances for which the lower bound of Mingozzi et al. has a bad relative error of O(logn), and the calculation of this bound is an NP-hard problem. In addition, we give a proof that there exists a type of instances for which known approximation algorithms with polynomial time complexity have an approximation ratio of at least equal to $O(\sqrt{n})$ , and known lower bounds have a relative error of at least equal to O(logn). This type of instances corresponds to the single machine parallel-batch scheduling problem 1|p?batch,b=∞|C _max.     

Evaluation of nondominated solution sets for k-objective optimization problems: An exact method and approximations

Integrated Preference Functional (IPF) is a set functional that, given a discrete set of points for a multiple objective optimization problem, assigns a numerical value to that point set. This value provides a quantitative measure for comparing different sets of points generated by solution procedures for difficult multiple objective optimization problems. We introduced the IPF for bi-criteria optimization problems in [Carlyle, W.M., Fowler, J.W., Gel, E., Kim, B., 2003. Quantitative comparison of approximate solution sets for bi-criteria optimization problems. Decision Sciences 34 (1), 63–82]. As indicated in that paper, the computational effort to obtain IPF is negligible for bi-criteria problems. For three or more objective function cases, however, the exact calculation of IPF is computationally demanding, since this requires k (⩾3) dimensional integration.In this paper, we suggest a theoretical framework for obtaining IPF for k (⩾3) objectives. The exact method includes solving two main sub-problems: (1) finding the optimality region of weights for all potentially optimal points, and (2) computing volumes of k dimensional convex polytopes. Several different algorithms for both sub-problems can be found in the literature. We use existing methods from computational geometry (i.e., triangulation and convex hull algorithms) to develop a reasonable exact method for obtaining IPF. We have also experimented with a Monte Carlo approximation method and compared the results to those with the exact IPF method.     

On routing in VLSI design and communication networks

In this paper, we study the global routing problem in VLSI design and the multicast routing problem in communication networks. First we propose new and realistic models for both problems. In the global routing problem in VLSI design, we are given a lattice graph and subsets of the vertex set. The goal is to generate trees spanning these vertices in the subsets to minimize a linear combination of overall wirelength (edge length) and the number of bends of trees with respect to edge capacity constraints. In the multicast routing problem in communication networks, a graph is given to represent the network, together with subsets of the vertex set. We are required to find trees to span the given subsets and the overall edge length is minimized with respect to capacity constraints. Both problems are APX-hard. We present the integer linear programming (LP) formulation of both problems and solve the LP relaxations by the fast approximation algorithms for min-max resource-sharing problems in [K. Jansen, H. Zhang, Approximation algorithms for general packing problems and their application to the multicast congestion problem, Math. Programming, to appear, doi:10.1007/s10107-007-0106-8] (which is a generalization of the approximation algorithm proposed by Grigoriadis and Khachiyan [Coordination complexity of parallel price-directive decomposition, Math. Oper. Res. 2 (1996) 321-340]). For the global routing problem, we investigate the particular property of lattice graphs and propose a combinatorial technique to overcome the hardness due to the bend-dependent vertex cost. Finally, we develop asymptotic approximation algorithms for both problems with ratios depending on the best known approximation ratio for the minimum Steiner tree problem. They are the first known theoretical approximation bound results for the problems of minimizing the total costs (including both the edge and the bend costs) while spanning all given subsets of vertices.     

The knapsack problem with neighbour constraints

We study a constrained version of the knapsack problem in which dependencies between items are given by the adjacencies of a graph. In the 1-neighbour knapsack problem, an item can be selected only if at least one of its neighbours is also selected. In the all-neighbours knapsack problem, an item can be selected only if all its neighbours are also selected.We give approximation algorithms and hardness results when the vertices have both uniform and arbitrary weight and profit functions, and when the dependency graph is directed and undirected.     

Approximation algorithms for art gallery problems in polygons

In this paper, we present approximation algorithms for minimum vertex and edge guard problems for polygons with or without holes with a total of n vertices. For simple polygons, approximation algorithms for both problems run in O(n⁴) time and yield solutions that can be at most O(logn) times the optimal solution. For polygons with holes, approximation algorithms for both problems give the same approximation ratio of O(logn), but the running time of the algorithms increases by a factor of n to O(n⁵).     

Mind the gap: a heuristic study of subway tours

What is the minimum tour visiting all lines in a subway network? In this paper we study the problem of constructing the shortest tour visiting all lines of a city railway system. This combinatorial optimization problem has links with the classic graph circuit problems and operations research. A broad set of fast algorithms is proposed and evaluated on simulated networks and example cities of the world. We analyze the trade-off between algorithm runtime and solution quality. Time evolution of the trade-off is also captured. Then, the algorithms are tested on a range of instances with diverse features. On the basis of the algorithm performance, measured with various quality indicators, we draw conclusions on the nature of the above combinatorial problem and the tacit assumptions made while designing the algorithms.     

Optimizing bandwidth allocation in elastic optical networks with application to scheduling

We study a problem of optimal bandwidth allocation in the elastic optical networks technology, where usable frequency intervals are of variable width. In this setting, each lightpath has a lower and upper bound on the width of its frequency interval, as well as an associated profit, and we seek a bandwidth assignment that maximizes the total profit. This problem is known to be NP-complete. We strengthen this result by showing that, in fact, the problem is inapproximable within any constant ratio even on a path network. We further derive NP-hardness results and present approximation algorithms for several special cases of the path and ring networks, which are of practical interest. Finally, while in general our problem is hard to approximate, we show that an optimal solution can be obtained by allowing resource augmentation. Some of our results resolve open problems posed by Shalom et al. (2013) [28]. Our study has applications also in real-time scheduling.     

Greedy expansions in convex optimization

This paper is a follow-up to the author’s previous paper on convex optimization. In that paper we began the process of adjusting greedy-type algorithms from nonlinear approximation for finding sparse solutions of convex optimization problems. We modified there the three most popular greedy algorithms in nonlinear approximation in Banach spaces-Weak Chebyshev Greedy Algorithm, Weak Greedy Algorithm with Free Relaxation, and Weak Relaxed Greedy Algorithm-for solving convex optimization problems. We continue to study sparse approximate solutions to convex optimization problems. It is known that in many engineering applications researchers are interested in an approximate solution of an optimization problem as a linear combination of elements from a given system of elements. There is an increasing interest in building such sparse approximate solutions using different greedy-type algorithms. In this paper we concentrate on greedy algorithms that provide expansions, which means that the approximant at the mth iteration is equal to the sum of the approximant from the previous, (m ? 1)th, iteration and one element from the dictionary with an appropriate coefficient. The problem of greedy expansions of elements of a Banach space is well studied in nonlinear approximation theory. At first glance the setting of a problem of expansion of a given element and the setting of the problem of expansion in an optimization problem are very different. However, it turns out that the same technique can be used for solving both problems. We show how the technique developed in nonlinear approximation theory, in particular, the greedy expansions technique, can be adjusted for finding a sparse solution of an optimization problem given by an expansion with respect to a given dictionary.     

Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing

This paper describes new models and exact solution algorithms for the fixed destination multidepot salesmen problem defined on a graph with n nodes where the number of nodes each salesman is to visit is restricted to be in a predefined range. Such problems arise when the time to visit a node takes considerably longer as compared to the time of travel between nodes, in which case the number of nodes visited in a salesman’s tour is the determinant of their ‘load’. The new models are novel multicommodity flow formulations with O(n²) binary variables, which is contrary to the existing formulations for the same (and similar) problems that typically include O(n³) binary variables. The paper also describes Benders decomposition algorithms based on the new formulations for solving the problem exactly. Results of the computational experiments on instances derived from TSPLIB show that some of the proposed algorithms perform remarkably well in cases where formulations solved by a state-of-the-art optimization code fail to yield optimal solutions within reasonable computation time.     

On minimum power connectivity problems

Given a (directed or undirected) graph with edge costs, the power of a node is the maximum cost of an edge leaving it, and the power of the graph is the sum of the powers of its nodes. Motivated by applications for wireless networks, we present polynomial and improved approximation algorithms, as well as inapproximability results, for some classic network design problems under the power minimization criteria. Our main result is for the problem of finding a min-power subgraph that contains k internally-disjoint vs-paths from every node v to a given node s: we give a polynomial algorithm for directed graphs and a logarithmic approximation algorithm for undirected graphs. In contrast, we will show that the corresponding edge-connectivity problems are unlikely to admit even a polylogarithmic approximation.     

A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem

We present a variable neighborhood search approach for solving the one-commodity pickup-and-delivery travelling salesman problem. It is characterized by a set of customers such that each of the customers either supplies (pickup customers) or demands (delivery customers) a given amount of a single product, and by a vehicle, whose given capacity must not be exceeded, that starts at the depot and must visit each customer only once. The objective is to minimize the total length of the tour. Thus, the considered problem includes checking the existence of a feasible travelling salesman’s tour and designing the optimal travelling salesman’s tour, which are both NP-hard problems. We adapt a collection of neighborhood structures, k-opt, double-bridge and insertion operators mainly used for solving the classical travelling salesman problem. A binary indexed tree data structure is used, which enables efficient feasibility checking and updating of solutions in these neighborhoods. Our extensive computational analysis shows that the proposed variable neighborhood search based heuristics outperforms the best-known algorithms in terms of both the solution quality and computational efforts. Moreover, we improve the best-known solutions of all benchmark instances from the literature (with 200 to 500 customers). We are also able to solve instances with up to 1000 customers.     

A note on the approximability of cutting stock problems

Cutting stock problems and bin packing problems are basically the same problems. They differ essentially on the variability of the input items. In the first, we have a set of items, each item with a given multiplicity; in the second, we have simply a list of items (each of which we may assume to have multiplicity 1). Many approximation algorithms have been designed for packing problems; a natural question is whether some of these algorithms can be extended to cutting stock problems. We define the notion of “well-behaved” algorithms and show that well-behaved approximation algorithms for one, two and higher dimensional bin packing problems can be translated to approximation algorithms for cutting stock problems with the same approximation ratios.     

On generalizations of network design problems with degree bounds

Iterative rounding and relaxation have arguably become the method of choice in dealing with unconstrained and constrained network design problems. In this paper we extend the scope of the iterative relaxation method in two directions: (1) by handling more complex degree constraints in the minimum spanning tree problem (namely laminar crossing spanning tree), and (2) by incorporating ‘degree bounds’ in other combinatorial optimization problems such as matroid intersection and lattice polyhedra. We give new or improved approximation algorithms, hardness results, and integrality gaps for these problems. Our main result is a (1, b + O(log n))-approximation algorithm for the minimum crossing spanning tree (MCST) problem with laminar degree constraints. The laminar MCST problem is a natural generalization of the well-studied bounded-degree MST, and is a special case of general crossing spanning tree. We give an additive Ω(log ^c m) hardness of approximation for general MCST, even in the absence of costs (c > 0 is a fixed constant, and m is the number of degree constraints). This also leads to a multiplicative Ω(log ^c m) hardness of approximation for the robust k-median problem (Anthony et al. in Math Oper Res 35:79–101, 2010), improving over the previously known factor 2 hardness. We then consider the crossing contra-polymatroid intersection problem and obtain a (2, 2b + Δ ? 1)-approximation algorithm, where Δ is the maximum element frequency. This models for example the degree-bounded spanning-set intersection in two matroids. Finally, we introduce the crossing latticep olyhedron problem, and obtain a (1, b + 2Δ ? 1) approximation algorithm under certain condition. This result provides a unified framework and common generalization of various problems studied previously, such as degree bounded matroids.