Help with Efficient Branching Strategy for Takeoff Slot Allocation Model Using Choco Solver

[Youcef1810]

Discussed in https://github.com/chocoteam/choco-solver/discussions/1109

^{Originally posted by **Youcef1810** October 27, 2024} Hello Choco Solver Team, In the context of allocating takeoff slots to avoid in-flight conflicts, I’ve developed a CSP model using the Choco solver. However, the constraint programming model is highly complex, and I need an efficient branching strategy due to the high resolution time stemming from model complexity and constraints. I would greatly appreciate your advice, as I’ve been recommended LDS and LNS as potential branching strategies. While I have initial solutions, I am finding it challenging to implement and adapt them to my code. Here is an outline of the variables and current setup: // Fixed number of flights and initialization of starting solution for flight delays int l = 26; // Number of flights int[] initialSolution = {9, 2, 0, 6, 8, 7, 6, 6, 7, 6, 5, 4, 3, 2, 2, 0, 1, 0, 3, 0, 3, 2, 5, 4, 1, 0}; // Initialize delay variables for each flight, with values based on the initial solution IntVar[] delays = new IntVar[l]; IntVar[] sortedDelays = model.intVarArray("SortedDelays", delays.length, 0, maxDelay); for (int i = 0; i < l; i++) { delays[i] = model.intVar("delay_" + i, 0, 90); // Max delay of 90 minutes try { delays[i].instantiateTo(initialSolution[i], null); // Assign starting solution } catch (ContradictionException e) { e.printStackTrace(); // Handle contradictions if they arise } } // Create the solver Solver solver = model.getSolver(); // Initialize delay variables IntVar[] delay = new IntVar[l]; for (int i = 0; i < l; i++) { delay[i] = model.intVar("delay_" + i, 0, 90); // Max delay of 90 minutes } // Search strategy for LDS Map map = IntStream.range(0, l) .boxed() .collect(Collectors.toMap(i -> delays[i], i -> initialSolution[i])); // Reset solver to avoid interference model.getSolver().hardReset(); // Define search strategy solver.setSearch(Search.intVarSearch( new InputOrder<>(model), // Select variables in input order var -> { if (map.containsKey(var) && var.contains(map.get(var))) { return map.get(var); // Use initial solution value if available } return var.getLB(); // Otherwise, return lower bound }, delays )); // Apply Limited Discrepancy Search (LDS) solver.setLDS(12); // Set discrepancy limit to 12 // Set time limit for the search solver.limitTime("100s"); // Display solutions solver.showSolutions(() -> Arrays.toString(delays)); // Solve the model solver.solve(); // Show result statistics solver.showShortStatistics(); The decision variables in this model are the flight delays, limited to a maximum of 90 minutes. The current setup also attempts to utilize LDS, with a time constraint for optimization, but I am experiencing challenges in fully adapting the branching strategy to this code. I would be very grateful for any advice or adjustments that could improve efficiency, especially with LDS and LNS strategies. Thank you very much for your support! Best regards,

[cprudhom]

See #1109