Semester assignments implementing classical metaheuristic algorithms in Julia. Three different combinatorial optimisation problems are studied, each solved with progressively more sophisticated algorithms.
Assignments 1, 4, 6
Find the minimum-cost path visiting every node exactly once, subject to precedence constraints: some nodes must be visited before others. Constraints are encoded in the cost matrix — a value of -1 on edge (i,j) means node j must be visited before node i. This is an NP-hard extension of TSP. The challenge is that most local search moves (swaps, reversals) may violate precedence and must be checked before being accepted.
Objective: minimise total travel cost.
Assignment 3
Schedule n jobs on m processors to minimise makespan (total completion time). Each job is a sequence of operations; each operation runs on a specific processor for a fixed duration. Two constraints must always hold: a processor handles one operation at a time, and a job's operations must run in order.
Objective: minimise the time at which the last operation finishes.
Assignment 5
Find the shortest tour visiting every city exactly once and returning to the start. No precedence constraints, but the focus is on efficient large-scale destroy-and-repair search.
Objective: minimise total tour length.
Steps:
- Construction — start from the node with no predecessors. Greedily pick the cheapest unvisited node whose predecessors have all been visited.
- 2-opt local search — try all pairwise segment reversals, discard any that violate precedence, move to the best improving neighbour. Repeat until no improvement.
- Perturbation — randomly shuffle 4 positions in the best known route. If feasible, re-apply 2-opt. Keep the result if it improves cost. Repeat within time limit.
julia assignment1/s222569.jl instance.sop solution.sol 60Problem: Assign n orders to k production lines within time horizon H. Each order has a production time and earns revenue. Additional pairwise revenue is earned when two orders share a line. Maximise total revenue without exceeding any line's capacity.
Steps:
- Greedy randomised construction — for each line, build a Restricted Candidate List (RCL) of orders whose incremental revenue is within
alpha = 0.13of the best. Randomly pick from the RCL and add if it fits inH. - Local search — try all pairwise order swaps between lines. Accept only if both lines still fit in
Hand total revenue increases. Uses delta-evaluation to avoid full recalculation. - Loop — repeat construction + local search until time limit. Keep the best solution found.
julia assignment2/s222569.jl instance.txt solution.sol 60Steps:
- Initial solution — randomly assign operations to processors, computing start/finish times while respecting processor availability and job order.
- Move — randomly pick a processor and swap two of its operations. Recompute all start/finish times and makespan.
- Acceptance — always accept improvements. Accept a worse solution with probability
exp(-delta/T). - Cooling — multiply
Tby0.97each iteration (starts atT = 1000). - Reheating — if 2000 consecutive iterations produce no accepted move, reset
T = 1000to escape the local region.
julia assignment3/s222569.jl instance.txt solution.txt 60Steps:
- Construction — same greedy nearest-neighbour heuristic as Assignment 1.
- Tabu Search — find the best valid 2-opt node swap not involving any city in the tabu list. Apply it unconditionally. Add the two swapped cities to a circular tabu list of length
K. - Diversification — if stuck for 100 iterations, randomly shuffle ~25% of route positions (checking feasibility) to escape the local region.
- Reset — if still stuck, reset the tabu list with
K = 10and continue.
julia assignment4/s222569.jl instance.sop solution.sol 60No external packages — uses Julia standard library only.