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

[Youcef1810]

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<IntVar, Integer> 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]

Hi @Youcef1810

I would like to make a few general remarks.

1. Use the code formatting tags to make the code readable.
2. Do not post the same question in multiple threads. This does not increase the likelihood of getting an answer.
3. We answer questions as quickly as possible, but please be aware that response times are not guaranteed as we answer in our spare time.

Now, about your model:

• The code presented does not contain any constraints. Is this normal?
• You need to look at the AirPlaneLanding example in the tutorials. It contains a lot of information.

Best regards
CP