A hybrid algorithm for the Heterogeneous Fleet Vehicle Routing Problem

This paper deals with the Heterogeneous Fleet Vehicle Routing Problem (HFVRP). The HFVRP generalizes the classical Capacitated Vehicle Routing Problem by considering the existence of different vehicle types, with distinct capacities and costs. The objective is to determine the best fleet composition as well as the set of routes that minimize the total costs. The proposed hybrid algorithm is composed by an Iterated Local Search (ILS) based heuristic and a Set Partitioning (SP) formulation. The SP model is solved by means of a Mixed Integer Programming solver that interactively calls the ILS heuristic during its execution. The developed algorithm was tested in benchmark instances with up to 360 customers. The results obtained are quite competitive with those found in the literature and new improved solutions are reported.     

A parallel matheuristic for the technician routing and scheduling problem

The Technician Routing and Scheduling Problem (TRSP) consists in routing staff to serve requests for service, taking into account time windows, skills, tools, and spare parts. Typical applications include maintenance operations and staff routing in telecoms, public utilities, and in the health care industry. In this paper, we present a formal definition of the TRSP, discuss its relation with the Vehicle Routing Problem with Time Windows (VRPTW), and review related research. From a methodological perspective, we describe a matheuristic composed of a constructive heuristic, a parallel Adaptive Large Neighborhood Search, and a mathematical programming based post-optimization procedure that successfully tackles the TRSP. We validate the matheuristic on the Solomon VRPTW instances, where we achieve an average gap of $0.23\,\%$ , and matched 44 out of 55 optimal solutions. Finally, we illustrate how the matheuristic successfully solves a set of TRSP instances extended from the Solomon benchmark.     

A heuristic framework on a common generalization of the Vehicle Routing Problem and the Linear Ordering Problem

A framework for bounding and approximating the solution of a newly formulated problem, the Vehicle Routing Problem with Internal Transports (VRPIT) Blázsik et al. (Pure Math Appl 17: 229–239, 2006), is presented. VRPIT is a common generalization of two well-known NP-hard problems, the Vehicle Routing Problem (VRP) Laporte (Eur J Op Res 59(3):345–358, 1992) and the Linear Ordering Problem (LOP) Schiavinotto and Stützle (J Math Model Algorithms 3(4):367–402, 2004). This generalization was motivated by the following situation: Consider VRP with the additional opportunity that each vehicle may make internal transports via short tours during its overall tour. In order to obtain the optimal income, we want to reduce the cost of small tours in relation to the profit that can be achieved by the corresponding internal transports with unit capacities. The structure of feasible solutions can be viewed as cycles of a permutation. The objective function is the difference between the profit from internal transports and the cost of the short tours. Although VRPIT is coming from the generalization of VRT and LOP, other equally hard problems can be reduced to it, as well.     

Multiobjective vehicle routing problem with fixed delivery and optional collections

We present an adaption on the formulation for the vehicle routing problem with fixed delivery and optional collections, in which the simultaneous minimization of route costs and of collection demands not fulfilled is considered. We also propose a multiobjective version of the iterated local search (MOILS). The performance of the MOILS is compared with the $\epsilon $ -constrained ( $P_{\epsilon }$ ) ILS, the NSGA-II and the indicator-based multi-objective local search methods in the solution of 14 problem instances containing between 50 and 199 customers plus the depot. The results indicate that the MOILS outperformed the other approaches, obtaining significantly better average values for coverage, hypervolume and cardinality.     

On a periodic vehicle routing problem

This paper deals with a study on a variant of the Periodic Vehicle Routing Problem (PVRP). As in the traditional Vehicle Routing Problem, customer locations each with a certain daily demand are given, as well as a set of capacitated vehicles. In addition, the PVRP has a horizon, say T days, and there is a frequency for each customer stating how often within this T-day period this customer must be visited. A solution to the PVRP consists of T sets of routes that jointly satisfy the demand constraints and the frequency constraints. The objective is to minimize the sum of the costs of all routes over the planning horizon. We develop different algorithms solving the instances of the case studied. Using these algorithms we are able to realize considerable cost reductions compared to the current situation.     

An Approximation Algorithm for Computing Shortest Paths in Weighted 3-d Domains

We present an approximation algorithm for computing shortest paths in weighted three-dimensional domains. Given a polyhedral domain $\mathcal D $ D , consisting of $n$ n tetrahedra with positive weights, and a real number $\varepsilon \in (0,1)$ ε ∈ ( 0 , 1 ) , our algorithm constructs paths in $\mathcal D $ D from a fixed source vertex to all vertices of $\mathcal D $ D , the costs of which are at most $1+\varepsilon $ 1 + ε times the costs of (weighted) shortest paths, in $O(\mathcal{C }(\mathcal D )\frac{n}{\varepsilon ^{2.5}}\log \frac{n}{\varepsilon }\log ^3\frac{1}{\varepsilon })$ O ( C ( D ) n ε 2.5 log n ε log 3 1 ε ) time, where $\mathcal{C }(\mathcal D )$ C ( D ) is a geometric parameter related to the aspect ratios of tetrahedra. The efficiency of the proposed algorithm is based on an in-depth study of the local behavior of geodesic paths and additive Voronoi diagrams in weighted three-dimensional domains, which are of independent interest. The paper extends the results of Aleksandrov et al. (J ACM 52(1):25–53, 2005), to three dimensions.     

On the computation of all eigenvalues for the eigenvalue complementarity problem

In this paper, a parametric algorithm is introduced for computing all eigenvalues for two Eigenvalue Complementarity Problems discussed in the literature. The algorithm searches a finite number of nested intervals \([\bar{l}, \bar{u}]\) in such a way that, in each iteration, either an eigenvalue is computed in \([\bar{l}, \bar{u}]\) or a certificate of nonexistence of an eigenvalue in \([\bar{l}, \bar{u}]\) is provided. A hybrid method that combines an enumerative method [1] and a semi-smooth algorithm [2] is discussed for dealing with the Eigenvalue Complementarity Problem over an interval \([\bar{l}, \bar{u}]\) . Computational experience is presented to illustrate the efficacy and efficiency of the proposed techniques.     

Maximal fitting subclasses of the class of all finite π-groups

Call a Fitting class $\mathfrak{F}$ π-maximal if $\mathfrak{F}$ is (inclusion-)maximal in the class $\mathfrak{C}_\pi$ of all finite π-groups, where π stands for a nonempty set of primes. We establish a π-maximality criterion for a Fitting class $\mathfrak{F}$ of finite π-groups: we prove that a nontrivial Fitting class $\mathfrak{F}$ is π-maximal if and only if there is a prime p ∈ π such that, for every π-group G, the index of the $\mathfrak{F}$ -radical $G_\mathfrak{F}$ in G is equal to 1 or p. This implies Laue’s familiar result on a necessary and sufficient condition of the maximality of an arbitrary Fitting class of finite groups in the class $\mathfrak{C}$ of all finite groups. The π-maximality criterion obtained also gives a confirmation of the negative solution of Skiba’s Problem asking whether a local Fitting class has no inclusion-maximal Fitting subclasses (see Problem 13.50, The Kourovka Notebook: Unsolved Problems in Group Theory, 14th ed., Sobolev Institute of Mathematics, Novosibirsk, 1999).     

An efficient compact quadratic convex reformulation for general integer quadratic programs

We address the exact solution of general integer quadratic programs with linear constraints. These programs constitute a particular case of mixed-integer quadratic programs for which we introduce in Billionnet et al. (Math. Program., 2010) a general solution method based on quadratic convex reformulation, that we called MIQCR. This reformulation consists in designing an equivalent quadratic program with a convex objective function. The problem reformulated by MIQCR has a relatively important size that penalizes its solution time. In this paper, we propose a convex reformulation less general than MIQCR because it is limited to the general integer case, but that has a significantly smaller size. We call this approach Compact Quadratic Convex Reformulation (CQCR). We evaluate CQCR from the computational point of view. We perform our experiments on instances of general integer quadratic programs with one equality constraint. We show that CQCR is much faster than MIQCR and than the general non-linear solver BARON (Sahinidis and Tawarmalani, User??s manual, 2010) to solve these instances. Then, we consider the particular class of binary quadratic programs. We compare MIQCR and CQCR on instances of the Constrained Task Assignment Problem. These experiments show that CQCR can solve instances that MIQCR and other existing methods fail to solve.     

Preemptive and non-preemptive generalized min sum set cover

In the (non-preemptive) Generalized Min Sum Set Cover Problem, we are given $n$ ground elements and a collection of sets $\mathcal{S }= \{S_1, S_2, \ldots , S_m\}$ where each set $S_i \in 2^{[n]}$ has a positive requirement $\kappa (S_i)$ that has to be fulfilled. We would like to order all elements to minimize the total (weighted) cover time of all sets. The cover time of a set $S_i$ is defined as the first index $j$ in the ordering such that the first $j$ elements in the ordering contain $\kappa (S_i)$ elements in $S_i$ . This problem was introduced by Azar et al. (2009) with interesting motivations in web page ranking and broadcast scheduling. For this problem, constant approximations are known by Bansal et al. (2010) and Skutella and Williamson (Oper Res Lett 39(6):433–436, 2011). We study the version where preemption is allowed. The difference is that elements can be fractionally scheduled and a set $S$ is covered in the moment when $\kappa (S)$ amount of elements in $S$ are scheduled. We give a 2-approximation for this preemptive problem. Our linear programming relaxation and analysis are completely different from the aforementioned previous works. We also show that any preemptive solution can be transformed into a non-preemptive one by losing a factor of 6.2 in the objective function. As a byproduct, we obtain an improved $12.4$ -approximation for the non-preemptive problem.     

Anti-Substitution Intuitions and the Content of Belief Reports

Philosophers of language traditionally take it that anti-substitution intuitions teach us about the content of belief reports. Jennifer Saul [1997, 2002 (with David Braun), 2007] challenges this lesson. Here I offer a response to Saul’s challenge. In the first two sections of the article, I present a common sense justification for drawing conclusions about content from anti-substitution intuitions. Then, in Sect. 3, I outline Saul’s challenge—what she calls ‘the Enlightenment Problem’. Finally, in Sect. 4, I argue that Saul’s challenge does not undermine the common sense justification presented in Sects. 1 and 2. I avoid the challenge by arguing that anti-substitution intuitions are not directly sensitive to the content of the sentences that produce them, but rather to the possibility that one could have distinct ways of thinking about an object.     

Decidability of absorption in relational structures of bounded width

The absorption theory of Barto and Kozik has proven to be a very useful tool in the algebraic approach to the Constraint Satisfaction Problem and the structure of finite algebras in general. We address the following problem: Given a finite relational structure \({\mathbb{A}}\) and a subset \({B \subseteq A}\) , is it decidable whether B is an absorbing subuniverse? We provide an affirmative answer in the case when \({\mathbb{A}}\) has bounded width (i.e., the algebra of polymorphisms of \({\mathbb{A}}\) generates a congruence meet semidistributive variety). As a by-product, we confirm that in this case the notion of Jónsson absorption coincides with the usual absorption. We also show that several open questions about absorption in relational structures can be reduced to digraphs.     

Disjoint Edges in Complete Topological Graphs

It is shown that every complete $n$ -vertex simple topological graph has at $\varOmega (n^{1/3})$ pairwise disjoint edges, and these edges can be found in polynomial time. This proves a conjecture of Pach and Tóth, which appears as Problem 5 from Chapter 9.5 in Research Problems in Discrete Geometry by Brass, Moser, and Pach.     

The Funk and Hilbert geometries for spaces of constant curvature

The goal of this paper is to introduce and to study analogues of the Euclidean Funk and Hilbert metrics on open convex subsets of the hyperbolic space $\mathbb H ^n$ H n and of the sphere $S^n$ S n . We highlight some striking similarities among the three cases (Euclidean, spherical and hyperbolic) which hold at least at a formal level. The proofs of the basic properties of the classical Funk metric on subsets of $\mathbb R ^n$ R n use similarity properties of Euclidean triangles which of course do not hold in the non-Euclidean cases. Transforming the side lengths of triangles using hyperbolic and circular functions and using some non-Euclidean trigonometric formulae, the Euclidean similarity techniques are transported into the non-Euclidean worlds. We start by giving three representations of the Funk metric in each of the non-Euclidean cases, which parallel known representations for the Euclidean case. The non-Euclidean Funk metrics are shown to be Finslerian, and the associated Finsler norms are described. We then study their geodesics. The Hilbert geometry of convex sets in the non-Euclidean constant curvature spaces $S^n$ S n and $\mathbb H ^n$ H n is then developed by using the properties of the Funk metric and by introducing a non-Euclidean cross ratio. In the case of Euclidean (respectively spherical, hyperbolic) geometry, the Euclidean (respectively spherical, hyperbolic) geodesics are Funk and Hilbert geodesics. This leads to a formulation and a discussion of Hilbert’s Problem IV in the non-Euclidean settings. Projection maps between the spaces $\mathbb R ^n, \mathbb H ^n$ R n , H n and the upper hemisphere establish equivalences between the Hilbert geometries of convex sets in the three spaces of constant curvature, but such an equivalence does not hold for Funk geometries.     

Amalgamation bases for the class of lattice-ordered groups

We prove Theorem A. The cardinal product of two copies of the integers is an amalgamation base for the class of all lattice-ordered groups but their lexicographic product is not. This answers Problem 27 of [Black Swamp Problem Book (W. Charles Holland, ed.), Bowling Green State University, 1982]. We also prove Theorem B. he cardinal product of n copies of the integers is not an amalgamation base for the class of all lattice-ordered groups if n ≥ 3.     

Scheme of lines on a family of 2-dimensional quadrics: geometry and derived category

Given a generic family $Q$ of 2-dimensional quadrics over a smooth 3-dimensional base $Y$ we consider the relative Fano scheme $M$ of lines of it. The scheme $M$ has a structure of a generically conic bundle $M \rightarrow X$ over a double covering $X \rightarrow Y$ ramified in the degeneration locus of $Q \rightarrow Y$ . The double covering $X \rightarrow Y$ is singular in a finite number of points (corresponding to the points $y \in Y$ such that the quadric $Q_y$ degenerates to a union of two planes), the fibers of $M$ over such points are unions of two planes intersecting in a point. The main result of the paper is a construction of a semiorthogonal decomposition for the derived category of coherent sheaves on $M$ . This decomposition has three components, the first is the derived category of a small resolution $X^+$ of singularities of the double covering $X \rightarrow Y$ , the second is a twisted resolution of singularities of $X$ (given by the sheaf of even parts of Clifford algebras on $Y$ ), and the third is generated by a completely orthogonal exceptional collection.     

Speeding up branch and bound algorithms for solving the maximum clique problem

In this paper we consider two branch and bound algorithms for the maximum clique problem which demonstrate the best performance on DIMACS instances among the existing methods. These algorithms are MCS algorithm by Tomita et al. (2010) and MAXSAT algorithm by Li and Quan (2010a, b). We suggest a general approach which allows us to speed up considerably these branch and bound algorithms on hard instances. The idea is to apply a powerful heuristic for obtaining an initial solution of high quality. This solution is then used to prune branches in the main branch and bound algorithm. For this purpose we apply ILS heuristic by Andrade et al. (J Heuristics 18(4):525–547, 2012). The best results are obtained for p_hat1000-3 instance and gen instances with up to 11,000 times speedup.     

Global symplectic coordinates on gradient Kähler–Ricci solitons

A classical result of McDuff [14] asserts that a simply connected complete Kähler manifold $(M,g,\omega )$ with non positive sectional curvature admits global symplectic coordinates through a symplectomorphism $\Psi \ : M \rightarrow \mathbb{R }^{2n}$ (where $n$ is the complex dimension of $M$ ), satisfying the following property (proved by E. Ciriza in [4]): the image $\Psi (T)$ of any complex totally geodesic submanifold $T\subset M$ through the point $p$ such that $\Psi (p)=0$ , is a complex linear subspace of $\mathbb C ^n\simeq \mathbb{R }^{2n}$ . The aim of this paper is to exhibit, for all positive integers $n$ , examples of $n$ -dimensional complete Kähler manifolds with non-negative sectional curvature globally symplectomorphic to $\mathbb{R }^{2n}$ through a symplectomorphism satisfying Ciriza’s property.     

Group homomorphic encryption: characterizations, impossibility results, and applications

We give a complete characterization both in terms of security and design of all currently existing group homomorphic encryption schemes, i.e., existing encryption schemes with a group homomorphic decryption function such as ElGamal and Paillier. To this end, we formalize and identify the basic underlying structure of all existing schemes and say that such schemes are of shift-type. Then, we construct an abstract scheme that represents all shift-type schemes (i.e., every scheme occurs as an instantiation of the abstract scheme) and prove its IND-CCA1 (resp. IND-CPA) security equivalent to the hardness of an abstract problem called Splitting Oracle-Assisted Subgroup Membership Problem (SOAP) (resp. Subgroup Membership Problem, SMP). Roughly, SOAP asks for solving an SMP instance, i.e., for deciding whether a given ciphertext is an encryption of the neutral element of the ciphertext group, while allowing access to a certain oracle beforehand. Our results allow for contributing to a variety of open problems such as the IND-CCA1 security of Paillier’s scheme, or the use of linear codes in group homomorphic encryption. Furthermore, we design a new cryptosystem which provides features that are unique up to now: Its IND-CPA security is based on the k-linear problem introduced by Shacham, and Hofheinz and Kiltz, while its IND-CCA1 security is based on a new k-problem that we prove to have the same progressive property, namely that if the k-instance is easy in the generic group model, the (k+1)-instance is still hard.     

Geometry of the Funk metric on Weil–Petersson spaces

We discuss the Funk function $F(x,y)$ on a Teichmüller space with its Weil–Petersson metric $(\mathcal{T },d)$ introduced in Yamada (Convex bodies in Euclidean and Weil–Petersson geometries, 2011), which was originally studied for an open convex subset in a Euclidean space by Funk [cf. Papadopoulos and Troyanov (Math Proc Cambridge Philos Soc 147:419–437, 2009)]. $F(x,y)$ is an asymmetric distance and invariant by the action of the mapping class group. Unlike the original one, $F(x,y)$ is not always convex in $y$ with $x$ fixed (Corollary 2.11, Theorem 5.1). For each pseudo-Anosov mapping class $g$ and a point $x \in \mathcal{T }$ , there exists $E$ such that for all $n\not = 0$ , $ \log |n| -E \le F(x,g^n.x) \le \log |n|+E$ (Corollary 2.10), while $F(x,g^n.x)$ is bounded if $g$ is a Dehn twist (Proposition 2.13). The translation length is defined by $|g|_F=\inf _{x \in \mathcal{T }}F(x,g.x)$ for a map $g: \mathcal{T }\rightarrow \mathcal{T }$ . If $g$ is a pseudo-Anosov mapping class, there exists $Q$ such that for all $n \not = 0$ , $\log |n| -Q \le |g^n|_F \le \log |n| + Q.$ For sufficiently large $n$ , $|g^n|_F >0$ and the infimum is achieved. If $g$ is a Dehn twist, then $|g^n|_F=0$ for each $n$ (Theorem 2.16). Some geodesics in $(\mathcal{T },d)$ are geodesics in terms of $F$ as well. We find a decomposition of $\mathcal{T }$ by sets, each of which is foliated by those geodesics (Theorem 4.10).