I took on the MESS 2024 Computational Optimization Challenge

Created on October 29, 2024

2024   ·   optimization   research   competition

Big Update: It’s a Paper Now!

I’m happy to share that the work I did for this competition has been formalized, validated, and published on arXiv! This was a joint effort with Grégoire de Lambertye.

In the paper, we formalize the solution approach I describe below, run a whole new set of computational experiments (including ablation studies), and properly validate the algorithm’s performance. It was a nice experience to turn a competition entry into a piece of academic research.

You can read the full paper here:

A Fast GRASP Metaheuristic for the Trigger Arc TSP with MIP-Based Construction and Multi-Neighborhood Local Search

Abstract: The Trigger Arc Traveling Salesman Problem (TA-TSP) extends the classical TSP by introducing dynamic arc costs that change when specific “trigger” arcs are traversed… Our algorithm finished in the top three at MESS 2024, demonstrating its suitability for real-time routing applications with state-dependent travel costs.

Now, for those new to the story, here’s how it all started and the method we developed.

What is this?

I participated in the MESS 2024 Computational Optimization Competition, and I want to share it.

Basically, I was bored during the summer break and I wanted to do something. I didn’t have any uni stuff at the time, I was only working for my company, which meant some free time!

I like OR, so I thought this would be a good opportunity to learn something new. For instance, my original plan was to try out the Hexaly solver because I thought it would be excellent at this problem, but they denied me the student access because I work for Quantagonia.

The Problem at Hand

The competition focused on a single problem, the Trigger-Arc Traveling Salesman Problem. I think they made it up themselves, but it’s a variant of the TSP. The organizers provided some half-convincing real-world application, but I think it’s just a fun academic problem.

How does the competition work?

The teams are given a set of instances, and they need to find good solutions for each of them. You can submit as many solutions as you want, and the best one for each instance will be used to evaluate your performance. So no time or computational limits, and every solver or solution approach is allowed. Teams of up to three people were allowed, but I participated alone.

Problem definition

The Trigger Arc Travelling Salesman Problem (TATSP) is defined as the problem of identifying in a graph G a Hamiltonian cycle of minimum cost considering relations defined between arcs. For each arc a in the graph, relations with other arcs can be defined, which act as triggers. If the trigger arc is traversed, the cost of the arc a is reset. Only the last trigger arc encountered before reaching the arc a is considered.

More formally (skippable)

 More formally, consider a directed graph $G = (N, A)$ with weights on the arcs. The node $0 \in N$ is designated as the starting node (depot). Let $c(a) \in \mathbb{R}^+ \, \forall a \in A$ be defined as the cost of traversing the arc $a$. For each arc $a = (h, k)$, a set of relations $R_a = \{(a_1, a) \mid a_1 \in A\}$ is associated. Finally, let $c(r) \in \mathbb{R}^+ \, \forall r \in R_a$, be the traversal cost of the arc $a$ if the relation $r$ is active. Let $T = (a_1, a_2, a_3, \ldots, a_{|N|})$ be the ordered sequence of arcs starting at node $0$ representing a Hamiltonian cycle in $G$. The relation $r = (a_i, a_j)$ is active if and only if the arcs $a_i, a_j \in T$, and the arc $a_i$ precedes the arc $a_j$ in $T$, and there is no other active relation $r_1 = (a_{i'}, a_j) \in R_{a_j}$ such that $a_i$ precedes $a_{i'}$ and $a_{i'}$ precedes $a_j$ in $T$. It follows that for each arc $a$, at most one relation can be active. As a result, the traversal cost of the arc $a \in A$ will be equal to $c(a)$ if there are no active relations in $R_a$ or $c(r)$ if $r$ is the only active relation in $R_a$.

My Solution Approach

We could say that my solution method was the result of a series of improvements:

  1. A small reformulation trick
  2. A first Mixed Integer Programming model
  3. Build a meaningful TSP instance, and solve it
  4. A GRASP for the TATSP

Small reformulation trick

This is not even a trick. But for the formulation, and later for the implementation, it’s useful to think of the costs of the edges as the base costs, and the costs of the relations as the additional costs.

So we simply preprocess every instance by doing c(r) = c(a) - c(r) for each relation. If we don’t do this, we are forced to model this “if else” on the cost of an edge, which is not nice for MIP models or in general for combinatorial optimization.

A Mixed Integer Programming Model for the TATSP

I first developed a MIP model of the problem, I think it’s a good starting point for any optimization problem. Modeling the arc-trigger relations was challenging, but it can be done.

MIP model

 Problem Parameters: - Let $G = (V, E)$ be a directed graph with: - $V = \{0, 1, \dots, N-1\}$ representing the set of nodes (vertices). - $E \subseteq V \times V$ representing the set of edges (arcs) with base costs $c_{ij}$ for $(i,j) \in E$. - $\delta_{\text{in}}(i) = \{(j,i) \in E\}$ and $\delta_{\text{out}}(i) = \{(i,j) \in E\}$ representing the set of incoming and outgoing edges of node $i$. - $R_a \subseteq E \times \{a\}, a\in E$ is composed of pairs $R_a = \{(b,a) : b \in E\}$. We call $b$ the trigger of the target arc $a$. If a relation is active, the cost of traversing the target arc $a$ is $c_a + r_{ba}$, the latter being the cost associated with the relation $(b,a)$. Decision Variables: - $x_{ij} \in \{0, 1\}$: binary variable, equal to 1 if edge $(i,j)$ is part of the tour, 0 otherwise. - $u_i \in [0, N-1]$: continuous variable representing the position of node $i$ in the tour. Note: in the model, we abuse the notation to write $u_a$ for $a \in E$. This corresponds to $u_{i}$ where $a=(i,j)$, i.e., the position of the first node of the arc $a$ in the tour. - $y_{ba} \in \{0, 1\}$: binary variable, equal to 1 if the relation $(b,a)$ is active, 0 otherwise. - $z_{a_1a_2} \in \{0, 1\}$: binary variable, used to model precedence constraints between arcs $a_1$ and $a_2$. Objective Function: We aim to minimize the total cost of the tour, considering the base costs of the arcs and the costs associated with the active relations. \begin{equation} \min \sum_{(i,j) \in E} x_{ij} c_{ij} + \sum_{a \in E} \sum_{(b,a) \in R_a} y_{ba} r_{ba} \end{equation} Constraints: 1. Flow Conservation: Only one incoming and one outgoing edge is allowed for each node. $$\sum_{j \in \delta_{\text{out}}(i)} x_{ij} = 1 \quad \forall i \in V$$ $$\sum_{j \in \delta_{\text{in}}(i)} x_{ji} = 1 \quad \forall i \in V$$ 2. Subtour Elimination: Miller-Tucker-Zemlin constraints to avoid subtours. $$u_i - u_j + N \cdot x_{ij} \leq N - 1 \quad \forall (i,j) \in E, \, j \neq 0$$ 3. At most one relation is active: Only one relation can be active for each target arc, and no relation can be active if the target arc is not part of the tour. $$\sum_{(b,a) \in R_a} y_{ba} \leq x_a \quad \forall a \in E$$ 4. Strengthen relation deactivation constraint: Strengthen the previous constraint to ensure that if the target or the trigger is not part of the tour, the relation cannot be active. $$y_{ba} \leq x_a \quad \forall a \in E, \, b \in R_a$$ $$y_{ba} \leq x_b \quad \forall a \in E, \, b \in R_a$$ 5. Relation is inactive if $b$ follows $a$ in the tour: A relation $(b,a)$ cannot be active if $b$ follows $a$ in the tour. $$y_{ba} \leq z_{ba} \quad \forall a \in E, \, b \in R_a$$ 6. At least one relation is active: For a given relation $(b,a)$, if $a$ and $b$ are part of the tour ($x_a = x_b = 1$), and $b$ precedes $a$ in the tour ($z_{ab} = 0$), then at least one relation targeting $a$ must be active. $$1 - z_{ab} \leq \sum_{(c,a) \in R_a} y_{ca} + (1 - x_a) + (1 - x_b) \quad \forall a \in E, \, b \in R_a$$ 7. Precedence constraints on $z$ variables: If $b$ precedes $a$ in the tour, then $z_{ab} = 0$. If the end node of the edge is shared, $a$ cannot precede $b$ or vice versa. $$u_a \leq u_b + (N-1) \cdot (1 - z_{ab}) \quad \forall (a,b) \in E \times E$$ $$z_{ab} = 1 - z_{ba} \quad \forall (a,b) \in E \times E$$ $$z_{a_1a_2b_1b_2} = z_{b_1b_2a_1a_2} \quad \forall (a_1a_2), (b_1b_2) \in E \times E \text{ if } a_1 = b_1$$ 8. Relation precedence constraints: Given two relations $(b,a)$ and $(c,a)$, if $b$ precedes $c$ which precedes $a$ in the tour ($z_{cb} = z_{ac} = 0$, $x_a = x_b = x_c$), then the relation $(b,a)$ cannot be active if $(c,a)$ is active (recall that only one relation can be active for each target arc). $$y_{ba} \leq y_{ca} + z_{cb} + z_{ac} + (1 - x_c) + (1 - x_b) + (1 - x_a) \quad \forall a \in E, \, b \in R_a, \, c \in R_a, \, b \neq c$$ 9. Set the starting node: Set the position of the starting node in the tour to be the first node. $$u_0 = 0$$

Performance: About the performance of this model, it’s not great. I passed it to Gurobi, and it could only solve to optimality 5/21 instances in the first round, and 1/34 instances in the second round.

But it felt right to have it. Good reasons for starting with a MIP:

  • Modeling makes you think deep about the problem and improves your understanding.
  • It’s fun.
  • What if the model could solve to optimality instances that you will spend hours trying to solve? (This was not the case 🤡)

Build a meaningful TSP instance, and solve it

A key observation is that feasibility for the TATSP problem is trivial: any permutation is a feasible solution. In other words, TSP solutions are also feasible solutions for the Trigger-Arc TSP.

So my question was:

Is there a TSP instance on the same graph, such that its optimal solution is the optimal solution to the TATSP?

The answer is probably no, but this question hints the direction of my next improvement.

I came up with a method that heuristically constructs a TSP instance (sets weights on the same instance graph) in a way that we push the solution of the TSP to trigger the TATSP relations that decrease the cost of the objective the most.

This heuristic is not trivial, and I had the problem that you actually need “prior knowledge” of the solution tour in order to define the TSP instance. Therefore, the edge costs of the TSP instance are defined for a given “prior” tour.

We construct the instance in the following way:

  1. Estimate the probability that an edge is used - inversely proportional to the distance between nodes in the prior tour
  2. Estimate the probability that a relation is active - taking into account the probability that both trigger and target edges are used, and their closeness
  3. Define the TSP instance with costs equal to the expected cost of the edge, considering the relations and their probabilities

This method alone is not great, but allowed me to get decent solutions for all instances, something that the MIP could not do. It’s also very fast.

Final step: A GRASP for the TATSP

GRASP is a simple metaheuristic that stands for Greedy Randomized Adaptive Search Procedure. It works as follows:

  1. Sample a randomized solution (usually a Randomized Greedy Construction Heuristic)
  2. Apply local search to improve the solution, stop if no improvement is found
  3. Repeat until you get a good solution

We already have a way to generate randomized solutions for the TATSP. Given a prior tour (think of it as a seed), we build a TSP instance, and we solve it to get a TATSP tour.

What we need is the Local Search improvement procedure. I considered the following local search operators:

  • 2-opt: Swap two edges, neighborhood of size O(n²)
  • 3-opt: Swap three edges, neighborhood of size O(n³)
  • delay-1: Take an arc an insert it later in the tour, neighborhood of size O(n²)

Implementation

You can find the implementation of this project in this repository: trigger_arc_tsp

We used C++17 to squeeze the last runtime performance possible, and we learned a lot along the way (we are much more experienced in Python).

Using unit tests for MIP modeling

I found it incredibly helpful to write unit tests for the MIP model. I had around 10 small instances that I could compute the solution by hand, that lead to 10 tests checking that the model produced the correct optimal solution. After a change in the model, I could run the tests to make sure the model was working as expected. I would do the same for every other MIP model I write.

Results and Prize

I got some nice results and finished 3rd in the competition 🎉. I want to congratulate the rest of the participants for their great work, and the organizers for the opportunity.