New Reoptimization Techniques applied to Steiner Tree Problem

Given an instance of an optimization problem together with an optimal solution for it, a reoptimization problem asks for a solution for a locally modified input instance. In this paper we develop new reoptimization techniques and apply them to the Steiner Tree Problem. Our techniques significantly improve the previous results and apply to a variety of reoptimization problems.     

Reoptimization of minimum and maximum traveling salesman's tours

In this paper, reoptimization versions of the traveling salesman problem (TSP) are addressed. Assume that an optimum solution of an instance is given and the goal is to determine if one can maintain a good solution when the instance is subject to minor modifications. We study the case where nodes are inserted in, or deleted from, the graph. When inserting a node, we show that the reoptimization problem for MinTSP is approximable within ratio 4/3 if the distance matrix is metric. We show that, dealing with metric MaxTSP, a simple heuristic is asymptotically optimum when a constant number of nodes are inserted. In the general case, we propose a 4/5-approximation algorithm for the reoptimization version of MaxTSP.     

Reoptimization procedures for bounded variable primal simplex network algorithms

Many algorithms and applications call for the use of a network subprogram which must be optimized numerous times with slight changes to the problem data. Bound and right-hand-side changes to an existing basis tree may yield an infeasible basic solution. This report gives a sequence of steps that modify an existing basic solution to reflect such changes and streamline the reoptimization process.     

关于最短路问题的一个双目标优化问题

本文研究了一个双目标最短路问题的变形问题,在该变形问题中,一个目标函数还是路的长度,另一个目标函数则是路的容量,在Pareto-optimal最优解的意义下,本文给出了一个时间复杂性为O（n^3 )的算法,在字典序最优解的意义下,本文给出了一个时间复杂性为O(n^3)的算法。     

On the completeness of a metric related to the Bergman metric

We study the completeness of a metric which is related to the Bergman metric of a bounded domain (sometimes called the Burbea metric or Fuks metric). We provide a criterion for its completeness in the spirit of the Kobayashi criterion for the completeness of the Bergman metric. In particular we prove that in hyperconvex domains our metric is complete.     

Reoptimization Gaps versus Model Errors in Online-Dispatching of Service Units for ADAC

Under high load, the automated dispatching of service vehicles for the German Automobile As- sociation (ADAC) must reoptimize a dispatch for 100–150 vehicles and 400 requests in about ten seconds to near optimality. In the presence of service contractors, this can be achieved by the column generation algorithm ZIBDIP. In metropolitan areas, however, service contractors cannot be dispatched automatically because they may decline. The problem: a model without contractors yields larger optimality gaps within ten seconds. One way-out are simplified reoptimization mod- els. These compute a short-term dispatch containing only some of the requests: unknown future requests will influence future service anyway. The simpler the models the better the gaps, but also the larger the model error. What is more significant: reoptimization gap or reoptimization model error? We answer this question in simulations on real-world ADAC data: only the new model ZIBDIP_dummy can keep up with ZIBDIP.     

A new weighted metric: the relative metric I

The M-relative distance, denoted by ρ_M is a generalization of the p-relative distance introduced in [R.-C. Li, SIAM J. Matrix Anal. Appl. 19 (1998) 956-982]. We establish necessary and sufficient conditions under which ρ_M is a metric. In two special cases we derive complete characterizations of this metric. We also present a way of extending the results to metrics sensitive to the domain in which they are defined and find some connections to previously studied metrics. An auxiliary result of independent interest is an inequality related to Pittenger's inequality in Section 4.     

A new weighted metric: the relative metric II

In the first part of this investigation we generalized a weighted distance function of R.-C. Li's and found necessary and sufficient conditions for it being a metric. In this paper some properties of this so-called M-relative metric are established. Specifically, isometries and quasiconvexity results are derived. We also illustrate connections between our approach and generalizations of the hyperbolic metric.     

The rural postman problem with deadline classes

Vehicle routing problems with general time windows are extremely difficult to solve. However, the time windows in a particular problem may have a special structure which can be exploited. We consider a single-vehicle arc-routing problem in which the arcs are partitioned into deadline classes. It is shown that a cutting-plane approach works well for this problem.     

Online weighted flow time and deadline scheduling

In this paper we study some aspects of weighted flow time. We first show that the online algorithm Highest Density First is an O(1)-speed O(1)-approximation algorithm for P|r_i,pmtn|∑w_iF_i. We then consider a related Deadline Scheduling Problem that involves minimizing the weight of the jobs unfinished by some unknown deadline D on a uniprocessor. We show that any c-competitive online algorithm for weighted flow time must also be c-competitive for deadline scheduling. We then give an O(1)-competitive algorithm for deadline scheduling.     

Reoptimization gaps versus model errors in online-dispatching of service units for ADAC

Under high load, the automated dispatching of service vehicles for the German Automobile Association (ADAC) must reoptimize a dispatch for 100-150 vehicles and 400 requests in about 10 s to near optimality. In the presence of service contractors, this can be achieved by the column generation algorithm ZIBDIP. In metropolitan areas, however, service contractors cannot be dispatched automatically because they may decline. The problem: a model without contractors yields larger optimality gaps within 10 s. One way out are simplified reoptimization models. These compute a short-term dispatch containing only some of the requests: unknown future requests will influence future service anyway. The simpler the models the better the gaps, but also the larger the model error. What is more significant: reoptimization gap or reoptimization model error? We answer this question in simulations on real-world ADAC data: only the new models ShadowPrice and ZIBDIP_dummy can keep up with ZIBDIP.     

Construction heuristics for the asymmetric TSP

Non-Euclidean traveling salesman problem (TSP) construction heuristics, and especially asymmetric TSP construction heuristics, have been neglected in the literature by comparison with the extensive efforts devoted to studying Euclidean TSP construction heuristics. This state of affairs is at odds with the fact that asymmetric models are relevant to a wider range of applications, and indeed are uniformly more general that symmetric models. Moreover, common construction approaches for the Euclidean TSP have been shown to produce poor quality solutions for non-Euclidean instances. Motivation for remedying this gap in the study of construction approaches is increased by the fact that such methods are a great deal faster than other TSP heuristics, which can be important for real time problems requiring continuously updated response. The purpose of this paper is to describe two new construction heuristics for the asymmetric TSP and a third heuristic based on combining the other two. Extensive computational experiments are performed for several different families of TSP instances, disclosing that our combined heuristic clearly outperforms well-known TSP construction methods and proves significantly more robust in obtaining (relatively) high quality solutions over a wide range of problems.     

Further Extension of the TSP Assign Neighborhood

We introduce a new extension of Punnen's exponential neighborhood for the traveling salesman problem (TSP). In contrast to an interesting generalization of Punnen's neighborhood by De Franceschi, Fischetti, and Toth (2005), our neighborhood is searchable in polynomial time, a feature that invites exploitation by heuristic and metaheuristic procedures for the TSP and related problems, including those of De Franceschi, Fischetti, and Toth (2005) for the vehicle routing problem. Research of GG was partially supported by Leverhulme Trust and by the IST Programme of the European Community, under the PASCAL Network of Excellence, IST-2002–506778.     

Main metric invariants of finite metric spaces. II

In the present paper we obtain new main metric invariants of finite metric spaces. These invariants can be used for classification of the finite metric spaces and their recognition.     

p-Hausdorff度量

根据Firey组合的属性,引入p-Hausdorff度量,特别地,当p=1时,p-Hausdorff度量就是著名的Hausdorff度量.进一步运用凸几何分析理论证明关于p-Hausdorff度量的2个重要结论.     

Mapping the global structure of TSP fitness landscapes

The global structure of combinatorial landscapes is not fully understood, yet it is known to impact the performance of heuristic search methods. We use a so-called local optima network model to characterise and visualise the global structure of travelling salesperson fitness landscapes of different classes, including random and structured real-world instances of realistic size. Our study brings rigour to the characterisation of so-called funnels, and proposes an intensive and effective sampling procedure for extracting the networks. We propose enhanced visualisation techniques, including 3D plots and the incorporation of colour, sizes and widths, to reflect relevant aspects of the search process. This brings an almost tangible new perspective to the landscape and funnel metaphors. Our results reveal a much richer global structure than the suggestion of a ‘big-valley’ structure. Most landscapes of the tested instances have multiple valleys or funnels; and the number, disposition and interaction of these funnels seem to relate to search difficulty on the studied landscapes. We also find that the structured TSP instances feature high levels of neutrality, an observation not previously reported in the literature. We then propose ways of analysing and visualising these neutral landscapes.