[Backend] Efficient TSP Solver API with Micronaut

By See Hiong

April 27, 2024 - 7 minutes read - 1292 words

Problem Statement

I’m embarking on a journey to solve the Travelling Salesman Problem (TSP) utilizing Choco-solver, an effective Java library for constraint programming. Additionally, I’ll be converting this solution into an API using Micronaut, a cutting-edge, JVM-based framework for building modular, testable microservices and serverless applications.

Setting up with Micronaut

Following the official Micronaut guide, I downloaded the source and proceeded with the setup.

Dependencies Configuration

I made adjustments to the dependencies in the build.gradle file to incorporate necessary libraries such as log4j, Lombok annotations, and Choco-solver.

dependencies {
    annotationProcessor("io.micronaut:micronaut-http-validation")
    annotationProcessor("io.micronaut.serde:micronaut-serde-processor")
    annotationProcessor("org.projectlombok:lombok")

    implementation("org.projectlombok:lombok")
    implementation("org.slf4j:slf4j-api")
    implementation("io.micronaut.serde:micronaut-serde-jackson")
    implementation("org.choco-solver:choco-solver:4.10.14")

    compileOnly("io.micronaut:micronaut-http-client")
    runtimeOnly("ch.qos.logback:logback-classic")
    testImplementation("io.micronaut:micronaut-http-client")
}

Running micronaut

By running the gradle task from Intellij or via command line, .\gradlew run, this will be the expected result:

micronaut-hello-world

Working on the TSPSolver

Input Definition

In the TSPSolver.java, I began by defining the inputs required for the solver. This includes setting up variables to represent the tour, distances between cities, and the total distance traveled.

public static void main(String[] args) {
    TSPSolver solver = new TSPSolver();
    int[][] distances = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0},
    };
    solver.solveTSP(distances); // Solve the TSP instance
}

Next the variables are being setup, where n is the total number of cities to be toured:

IntVar[] tour = model.intVarArray("tour", n, 0, n - 1); // Tour representing the order of cities visited
IntVar[] distance = model.intVarArray("distance", n, 0, 1000000); // Auxiliary variables for distances
IntVar totalDistance = model.intVar("totalDistance", 0, 1000000); // Total distance traveled

Constraint Setup

To ensure the tour adheres to the constraints of the TSP, I defined constraints using Choco-solver. This includes specifying the distances between cities and enforcing that the tour forms a single circuit, visiting each city exactly once.

for (int i = 0; i < n; i++) {
    Tuples tuples = new Tuples(true); // Create tuples to represent valid combinations of city and distance
    for (int j = 0; j < n; j++) {
        if (j != i) {
            tuples.add(j, distances[i][j]); // Add valid combinations of city and distance to tuples
        }
    }
    model.table(tour[i], distance[i], tuples).post(); // Apply table constraint for each city
}

// Ensure that the tour forms a single circuit, visiting each city exactly once
model.subCircuit(tour, 0, model.intVar(n)).post();
}

Solver Configuration

I configured the solver to search for the optimal solution using a FirstFail search strategy, prioritizing smaller values during the search process.

Solver solver = model.getSolver();
solver.setSearch(
    Search.intVarSearch(
        new FirstFail(model), // Use FirstFail search strategy to select variables
        new IntDomainMin(), // Priorities smaller values from domain of integer variables during search
        distance));

Model Solving

Upon solving the model, I iterated through the solution to extract the optimal tour and total distance traveled. This information was then logged for analysis.

Map<Number, Integer[]> optimalSolution = new HashMap<>();
while (solver.solve()) {
    Integer[] optimalTour = new Integer[n+1];
    int current = 0; // Start from the first city
    log.info("City {}", current); // Print the current city
    optimalTour[0] = current;
    for (int i = 1; i <= n; i++) {
        int next = tour[current].getValue(); // Get the next city in the tour
        optimalTour[i] = next;
        log.info("City {}", next); // Print the next city
        current = tour[current].getValue(); // Move to the next city
    }

    optimalSolution.put(totalDistance.getValue(), optimalTour);
    log.info("\nTotal tour distance: {}", totalDistance.getValue()); // Print the total distance
}

Final TSPSolver

This is my final TSPSolver.java:

package example.micronaut;

import jakarta.inject.Singleton;
import lombok.extern.slf4j.Slf4j;
import org.chocosolver.solver.Model;
import org.chocosolver.solver.Solver;
import org.chocosolver.solver.constraints.extension.Tuples;
import org.chocosolver.solver.search.strategy.Search;
import org.chocosolver.solver.search.strategy.selectors.values.IntDomainMin;
import org.chocosolver.solver.search.strategy.selectors.variables.FirstFail;
import org.chocosolver.solver.variables.IntVar;

import java.util.HashMap;
import java.util.Map;

@Slf4j
@Singleton
public class TSPSolver {

    public TSPSolution solveTSP(int[][] distances) {
        int n = distances.length;
        Model model = new Model("TSP");

        // Variables
        IntVar[] tour = model.intVarArray("tour", n, 0, n - 1); // Tour representing the order of cities visited
        IntVar[] distance = model.intVarArray("distance", n, 0, 1000000); // Auxiliary variables for distances
        IntVar totalDistance = model.intVar("totalDistance", 0, 1000000); // Total distance traveled

        // Constraints
        // Define the distances between cities using table constraints
        for (int i = 0; i < n; i++) {
            Tuples tuples = new Tuples(true); // Create tuples to represent valid combinations of city and distance
            for (int j = 0; j < n; j++) {
                if (j != i) {
                    tuples.add(j, distances[i][j]); // Add valid combinations of city and distance to tuples
                }
            }
            model.table(tour[i], distance[i], tuples).post(); // Apply table constraint for each city
        }

        // Ensure that the tour forms a single circuit, visiting each city exactly once
        model.subCircuit(tour, 0, model.intVar(n)).post();

        // Define the objective: minimize the total distance traveled
        model.sum(distance, "=", totalDistance).post();
        model.setObjective(Model.MINIMIZE, totalDistance); // Set the objective to minimize total distance

        // Solver setup
        Solver solver = model.getSolver();
        solver.setSearch(
                Search.intVarSearch(
                        new FirstFail(model), // Use FirstFail search strategy to select variables
                        new IntDomainMin(), // Priorities smaller values from domain of integer variables during search
                        distance));

        // Solve the Model and Display the Path
        Map<Number, Integer[]> optimalSolution = new HashMap<>();
        while (solver.solve()) {
            Integer[] optimalTour = new Integer[n+1];
            int current = 0; // Start from the first city
            log.info("City {}", current); // Print the current city
            optimalTour[0] = current;
            for (int i = 1; i <= n; i++) {
                int next = tour[current].getValue(); // Get the next city in the tour
                optimalTour[i] = next;
                log.info("City {}", next); // Print the next city
                current = tour[current].getValue(); // Move to the next city
            }

            optimalSolution.put(totalDistance.getValue(), optimalTour);
            log.info("Total tour distance: {}", totalDistance.getValue()); // Print the total distance
        }

        if (model.getSolver().hasObjective()) {
            Number optimalDistance = model.getSolver().getBestSolutionValue(); // Get the optimal distance
            log.info("Optimal tour distance: {}", optimalDistance);
            return new TSPSolution(optimalSolution.get(optimalDistance), optimalDistance);
        } else {
            return null;
        }
    }

    public static void main(String[] args) {
        TSPSolver solver = new TSPSolver();
        int[][] distances = {
                {0, 10, 15, 20},
                {10, 0, 35, 25},
                {15, 35, 0, 30},
                {20, 25, 30, 0},
        };
        solver.solveTSP(distances); // Solve the TSP instance
    }
}

TSPSolution Model

To encapsulate the solution, I created a TSPSolution model using Lombok annotations, facilitating easy serialization and deserialization.

package example.micronaut;

import io.micronaut.serde.annotation.Serdeable;
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

@Data
@AllArgsConstructor
@NoArgsConstructor
@Serdeable.Serializable
public class TSPSolution {

    private Integer[] optimalTour;
    private Number totalDistance;

}

First attempt

For this simple case, the result is just as per expected:

micronaut-tsp-first-attempt

Converting to an API

To make the solution accessible as an API, I wrapped it within a controller class, TSPController.java, utilizing Micronaut annotations to define endpoints.

package example.micronaut;

import io.micronaut.http.MediaType;
import io.micronaut.http.annotation.*;

@Controller("/tsp")
public class TSPController {
    private final TSPSolver tspSolver;

    public TSPController(TSPSolver tspSolver) {
        this.tspSolver = tspSolver;
    }

    @Post("/solve")
    @Produces(MediaType.APPLICATION_JSON)
    @Consumes(MediaType.APPLICATION_JSON)
    public TSPSolution solveTSP(@Body int[][] distances) {
        return tspSolver.solveTSP(distances);
    }

}

Putting it in action

With the API set up, I tested various inputs using tools like Postman, observing the solutions returned for different scenarios.

micronaut-postman-tsp-first-attempt

With the next set of inputs:

[
    [0, 10, 15, 20, 25],
    [10, 0, 35, 25, 20],
    [15, 35, 0, 30, 10],
    [20, 25, 30, 0, 15],
    [25, 20, 10, 15, 0]
]

This is the result:

micronaut-tsp-second-attempt

micronaut-postman-tsp-second-attempt

The final set of inputs:

[
  [0, 10, 15, 20, 25, 30, 35, 40],
  [10, 0, 35, 25, 20, 45, 50, 55],
  [15, 35, 0, 30, 10, 40, 45, 60],
  [20, 25, 30, 0, 15, 50, 55, 70],
  [25, 20, 10, 15, 0, 35, 40, 65],
  [30, 45, 40, 50, 35, 0, 25, 70],
  [35, 50, 45, 55, 40, 25, 0, 75],
  [40, 55, 60, 70, 65, 70, 75, 0]
]

The corresponding result:

micronaut-postman-tsp-third-attempt

In conclusion, this project showcases the seamless integration of Choco-solver and Micronaut to solve the Travelling Salesman Problem efficiently and transform it into a versatile API. By harnessing the power of constraint programming and modern Java frameworks, we’ve demonstrated a robust solution for optimizing city tours. Whether you’re exploring algorithmic challenges or building real-world applications, this approach offers scalability, modularity, and performance. With further refinement and customization, this solution can be tailored to address a wide range of optimization problems in various domains.