Refined Integer Programs and Polyhedral Results for the Target Visitation Problem

In the Target Visitation Problem (TVP), the task is to determine an ordering (permutation) of a set of target locations (sites) that maximizes the difference between the total sum of pairwise rewards $p_{ij}\in ℝ$, $i\ne j$, obtained when ranking a site $i$ (anywhere) before another site $j$, and the total sum of pairwise costs $c_{ij}\in ℝ$ paid when ranking sites $i$ and $j$ consecutively. Considering a permutation as a site-traversal order, the rewards $p_{ij}$ may be interpreted as the strength of the preference of visiting site $i$ before site $j$ while the costs $c_{ij}$ may reflect e.g. the traveling distance from $i$ to $j$. Figure 1 displays which rewards and costs effectively contribute to the objective value of an example ordering of five sites, and a more formal problem definition is given at the beginning of Section 2. As this illustrates, the TVP is a combination (and generalization) of the Linear Ordering Problem (LOP) and the (Weighted) Asymmetric Hamiltonian Path Problem (AHPP) in a complete graph. With only slight modifications, one may also consider it as a combination of the LOP and the (Weighted) Asymmetric Traveling Salesman Problem (ATSP) [4, 5]. By choosing sufficiently high rewards, it may further serve as a proxy for the ATSP with precedence constraints. Moreover, each of these related combinatorial optimization problems is well-known to be strongly $𝒩𝒫$-hard whence so is the TVP [5, 6].

The TVP is a natural model for route planning problems where both the total travel costs and the order of the visited sites are of (potentially competing) interest. A common scenario is that the demands of supply (urgencies) and the supply times between locations need to be juxtaposed in opposition, like in the seminal application with unmanned aerial vehicles (drones) in [4]. This includes particularly the scheduling of rescue or relief missions in disaster areas, the planning of town-cleaning or snow-plowing services [5], as well as further applications in transportation where the route sequence is supposed to reflect visiting preferences beyond the shortest distance or travel time, for instance to integrate an additional route-internal pickup and delivery as considered e.g. in [2].

Since its introduction in 2004 by Grundel and Jeffcoat [4] who addressed the problem with a local search approach, the TVP has mainly been studied in the context of integer programming and polyhedral combinatorics by Hildenbrandt, especially in his PhD thesis [5] and a related article [6]. In the dissertation, he also evaluated several heuristics. Furthermore, there is a semidefinite programming relaxation for the TVP by Hungerländer [7] as well as further heuristics by Blázsik et al. [2] and Arulselvan et al. [1].

In this work, we first present three integer programming (re)formulations for the TVP which improve on their relatives from [5, 6] in terms of continuous relaxation strength, preciseness in characterizing TVP solutions by means of compact constraint sets, and solution times. An accompanying analysis of the impact of certain equation and inequality classes provides a tidied-up dominance relation between candidate constraints that enforce a consistent permutation or link different variable subsets. Then, we present revised and extended results regarding the description of the polytopes associated with the proposed formulations, i.e. the convex hull of the vectors describing their feasible solutions, by means of a minimal set of linear equations and facet-defining inequalities. In an experimental study, we demonstrate the practical effects of our refinements in terms of solving the formulations with a branch-and-cut algorithm, and we report the optimal values for some previously unsolved instances. Besides that, we draw relations to the Asymmetric Betweenness Problem and the Quadratic Linear Ordering Problem which allow to translate certain structural results between canonical integer programming formulations for these problems and for the TVP.

This paper is organized as follows. In Section 2, we first provide a more formal definition of the TVP, we recall the two primary integer programs proposed in [5, 6], and we briefly address further aspects of closely related work. We then present our refined formulations in Section 3, along with accompanying results on their relaxation strength and the necessity of certain constraint sets. Our polyhedral results are the subject of Section 4, and we report on our computational experiments in Section 5. Finally, a brief conclusion is given in Section 6.

Let $n\in \mathbb{N}$ be the number of target sites to be visited in the TVP and let ${\mathrm{\Pi }}_n$ be the set of all permutations of $[n]≔\{1,\mathrm{\dots },n\}$. A permutation $\pi \in {\mathrm{\Pi }}_n$ is here treated as a bijective function that maps each site $i\in [n]$ to its position $\pi (i)\in [n]$, and where we conversely denote by ${\pi }^{-1}(i)$ the site that is placed at the position $i\in [n]$. The objective function of the TVP may then be formally written as

or likewise as

As will become apparent in the following, the latter variant is particularly suited to be implemented by means of common binary decision variables in an integer linear programming (ILP) formulation. Since such formulations and accompanying polyhedral considerations are the central subject of this work, we mainly concentrate the exposition of the prevalent literature on the seminal (and so far, in all conscience, not otherwise resumed) research by Hildenbrandt [5, 6]. Specifically, he presents several integer programs for the TVP, two of which are in the focus of his investigations as well as of this paper.

The first, major, model by Hildenbrandt is called TVP-HP, and it combines the central ingredients of known formulations for the AHPP and the LOP in a canonical way.

In this light, TVP-HP involves (AHPP) variables $x_{ij}$, for $i,j\in [n]$, $i\ne j$, where $x_{ij}=1$ if $\pi (j)-\pi (i)=1$ (i.e., site $j$ is visited immediately after site $i$) and $x_{ij}=0$ otherwise, as well as (LOP) variables $y_{ij}$, for $i,j\in [n]$, , where $y_{ij}=1$ if (i.e., site $j$ is visited anytime after site $i$) and $y_{ij}=0$ if . Assuming that the AHPP variables take on binary values, the constraints (1)–(3) reflect that $n-1$ immediate successor relations (“edges”, when considering the permutation as a path) are established while each site has at most one successor and at most one predecessor. Likewise, assuming that the LOP variables take on binary values, the three-di-cycle inequalities (4) and (5) are known to be sufficient in order to uniquely determine a permutation $\pi \in {\mathrm{\Pi }}_n$ [3]. In [5, 6], Hildenbrandt points out that the linking of the two variable sets by means of inequalities (6) and (7) excludes disconnected subpaths (respectively subtours) from the feasible set, i.e., they ensure that the binary values of the AHPP variables are in one-to-one correspondence with a directed Hamiltonian path. In the original presentation of TVP-HP in these references, the constraints (7) are nevertheless missing despite they are hence necessary. At the same time, they are included in the list of facet-defining inequalities for the related polytope that Hildenbrandt describes explicitly for $n=4$ and they also have been recognizably included when carrying out his computational experiments with TVP-HP.

The second model in Hildenbrandt’s focus is an extended formulation, called TVP-E.

Specifically, he obtains TVP-E from TVP-HP by extending the latter in two steps. First, he introduces the additional variables $b_{ikj}$, for all $i,j,k\in [n]$, $|\{i,j,k\}|=3$, with the interpretation that $b_{ikj}=1$ if (i.e., $k$ is ranked between $i$ and $j$ while $i$ is ranked before $j$) and $b_{ikj}=0$ otherwise. Second, he appends the constraint sets (11) and (12) to link these new variables to the AHPP respectively LOP variables. Thereby, the intuition behind the inequalities (12) is that if site $j$ is visited immediately after site $i$, then any other site $k$ must be visited either before or after both $i$ and $j$. Notably, the constraints (11) (only) ensure that, if , then any other site $k$ must be placed either before, in between, or after this accordingly ordered pair. The reverse direction, i.e., $b_{ijk}+b_{kij}+b_{ikj}=1$ if , is however missing.

Indeed, solutions where all the six $b$-variables associated with a fixed triple of sites $i,j,k\in [n]$, , are zero, are thus verifiably feasible for TVP-E (in addition to those where these variables receive values that are consistent with the ordering expressed in the LOP variables). Consequently, a feasible solution to the TVP unintendedly corresponds to more than one feasible solution of TVP-E (which we will cure in Section 3). Since a feasible TVP solution is correctly (and unambiguously) encoded in the integral AHPP- and LOP-variables though, and since the $b$-variables do not affect the objective function, one may still derive optimum solutions from TVP-E. Apart from that, the inequalities (7) are again not included in the original presentation of TVP-E in [5, 6], and in this case they are indeed negligible as they are implied by (11) and (12).

Even despite the unintended additional solutions, the upper bound on the optimal value obtained when solving the continuous relaxation (i.e., the linear programming, or short LP, relaxation that results from neglecting all integrality restrictions) of TVP-E is provably at least as strong as the one obtained when solving the relaxation of TVP-HP, and is experimentally observed in [5, 6] to be usually significantly stronger. Nevertheless, TVP-E has not been further considered as an option for a branch-and-cut approach in these references, due to the reported high solution times of its relaxation. As will be demonstrated in the following sections, these solution times can however be improved by a careful reformulation.

Another observation that rather appears as a detail in [5], and that will play an important role for the refinement of TVP-HP, is that the three-di-cycle inequalities (4), (5) can be extended in the here given common context with the AHPP-variables. These extended three-di-cycle inequalities can be written as follows:

For completeness, we remark that Hildenbrandt describes a further model that combines the notion of a subsequently visited pair of sites and other sites ranked (somewhere) after the respective pair, as well as a formulation based on distance variables. However, these formulations were found to be significantly inferior to TVP-HP and TVP-E in [5], whence we refer to this reference for further details. Finally, adapted formulations for the case where the TVP is rather considered as a combination of the LOP and the ATSP are stated in [1, 5].

In this section, our efforts are directed to derive integer programming formulations for the TVP that fulfill two requirements. The first one is that the feasible solutions of a formulation are in one-to-one correspondence with those of the TVP, and, to achieve compactness and strength at the same time, the second one is that a formulation solely consists of equations and inequalities which take part in a minimal description of the polytope that is given as the convex hull of the (incidence) vectors describing these solutions. The latter condition subdivides into the two necessities that each equation must be part of a minimum equation system for the respective polytope and that every inequality must induce a facet of it. In total, we present three according formulations which are subject to an experimental comparison in Section 5. Besides that, the accompanying analysis of the impact of certain equation and inequality classes serves as an intermediate step to the polyhedral results in Section 4.

As a first formulation, we propose TVP-XY, which is obtained from TVP-HP by replacing the three-di-cycle inequalities (4) and (5) with their extended pendants (15)–(20).

This comparably small change is motivated as follows. In [5, 6], Hildenbrandt defines the polytope

(related to TVP-HP) whose vertices are in one-to-one correspondence with the incidence vectors of the feasible solutions to the TVP, expressed in AHPP- and LOP-variables. Also, the equation (1) has been identified as a minimum equation system for $P_{\text{TV}}^n$, and the inequalities (2), (3), (6) and (7) have been identified as facets of $P_{\text{TV}}^n$, $n\ge 4$. However, the inequalities (4) and (5) do not define facets of $P_{\text{TV}}^n$, $n\ge 4$, whereas the inequalities (15)–(20) do (facet class 29 in [5]). Their exchange thus ensures the fulfillment of the second requirement mentioned above. In addition, we propose and explicitly state TVP-XY to foster its consideration and evaluation as a fundamental formulation on its own, which is also supported by our computational results in Section 5. As opposed to that, in [5, 6], the replacement of (4) and (5) by (15)–(20) is rather treated as optional, and the resulting computational effect, especially regarding the upper bounds obtained from the continuous relaxation, cannot be sufficiently deduced respectively distinguished from other effects that are subject to TVP-HP simultaneously.

While all constraint classes of TVP-XY take part in a minimal description of $P_{\text{TV}}^n$, it is noteworthy that (as opposed to TVP-HP) TVP-XY is yet not irreducible in the sense that its feasible solutions remain in one-to-one correspondence with those of the TVP when removing inequalities (2) and (3). This is formally recorded in Proposition 1. In other words, these inequalities are kept in TVP-XY only to strengthen its continuous relaxation. Moreover, by construction, the latter provides an upper bound on the optimal value that is at least as strong as the one of the continuous relaxation of TVP-HP.

In this section, we investigate the polytope $P_{\text{TVE}}^n$ defined in Section 3 and provide fundamental results concerning its (minimal) description by linear equations and inequalities. As a byproduct, these results also clarify some statements in [5, 6] about the polytope $P_{\text{ETV}}^n$ considered there.

Our starting point is the following result by Hildenbrandt:

Deviating from the presentation in [5, 6], we however find that, if $n=4$, then there is another set of equations that is valid for all incidence vectors of feasible solutions to the TVP consistently expressed in $x$-, $y$-, and $b$-variables.