- Category: Data Science, Optimization
- Language: Python and Julia
- Date: June 2023
- Results: Ranked 1st among 95 students
- Best scores for every instance
- GitHub: Project Repository (Python)
- Project Repository (Julia)

I participated with Thimoté Dupuch in a programming contest where we worked on an surveillance optimization project. Our mission was to optimize the placement of surveillance points to cover specific targets while avoiding obstacles in a 2D grid. The goal is to minimize the number of surveillance points needed to effectively monitor all targets in the grid. Before settling on the final implementation in Julia using linear programming, we first explored various approaches in Python. We experimented with algorithms like local search, greedy, genetic, heuristic, and recursive methods to compare their performances and identify the most efficient solution. Then, we used Julia to formulate the problem as a binary linear programming model and efficiently solved it with the HiGHS solver.

During the initial stages of the project, we first decided to explore multiple strategies to solve the surveillance optimization problem. We opted to use Python as our programming language for its versatility and ease of implementation. We developed several algorithms, each with its own unique approach to the problem.

After implementing these algorithms, we thoroughly tested and compared their performances on various instances of the surveillance problem. However, it became evident that the linear programming approach using the JuMP package in Julia outperformed all the other methods. It provided a more robust and optimal solution for the problem at hand.

The provided code is written in the Julia programming language and aims to solve a surveillance optimization problem. The goal is to determine the minimum number of surveillance points required to cover all specified target locations while avoiding obstacles. The code uses the JuMP library to formulate and solve the optimization problem, and the HiGHS solver is employed to find the optimal solution. Let's break down the structure and purpose of the code:

Overall, the code follows a structured approach to solve the surveillance optimization problem by formulating it as a binary linear programming model using JuMP and finding the optimal solution with the HiGHS solver. It effectively uses functions to organize and encapsulate related tasks, making the code modular and easy to understand.

```
using JuMP
using HiGHS
# Function to check if a target is visible from a given surveillance point
function is_visible(x_cible, y_cible, x_surv, y_surv, grille)
if grille[x_surv, y_surv] == 2 # If the surveillance point is on an obstacle
return false
end
dx = x_cible - x_surv
dy = y_cible - y_surv
if dx == 0 && dy == 0
return true
end
# Check visibility on a single row
if dx == 0
direction = sign(dy)
for j in y_surv + direction:direction:y_cible - direction
if grille[x_surv, j] == 2 # If there is an obstacle on the row
return false
end
end
return true
end
# Check visibility on a single column
if dy == 0
direction = sign(dx)
for i in x_surv + direction:direction:x_cible - direction
if grille[i, y_surv] == 2 # If there is an obstacle on the column
return false
end
end
return true
end
return false # The target and surveillance point are neither on a row nor on a column
end
# Read input from a file and initialize the grid
f = open("Instances/gr16.txt", "r")
lines = readlines(f)
nb_lignes_fichier = size(lines)[1]
nb_lignes = parse(Int, lines[1][end-1:end])
nb_colonnes = parse(Int, lines[2][end-1:end])
grille = zeros(nb_lignes, nb_colonnes)
# Function to assign a value to grid cells based on the input
function assign(objet)
if objet == "CIBLE"
return 1
else
return 2
end
end
# Initialize the grid based on the input file
for i in 4:size(lines)[1] # Ignore the first three lines
line = lines[i]
parts = split(line)
objet = parts[1]
x = parse(Int, parts[2]) + 1
y = parse(Int, parts[3]) + 1
int_objet = assign(objet)
grille[x, y] = int_objet
end
# Create a JuMP model using HiGHS optimizer
m = Model(HiGHS.Optimizer)
# Decision variables
@variable(m, surveillant[1:nb_lignes, 1:nb_colonnes], Bin)
# Constraint 1: Each target must be surveilled at least once
for i in 1:nb_lignes
for j in 1:nb_colonnes
if grille[i, j] == 1 # If it is a target
@constraint(m, sum(surveillant[x, y] for x in 1:nb_lignes, y in 1:nb_colonnes
if is_visible(i, j, x, y, grille) && grille[x, y] != 2) >= 1)
end
end
end
# Objective: Minimize the number of surveillance points
@objective(m, Min, sum(surveillant[i, j] for i in 1:nb_lignes, j in 1:nb_colonnes))
# Set time limit for the optimization
set_time_limit_sec(m, 180.0)
# Solve the model
optimize!(m)
# Display the positions of the surveillance points
resultats_optim = []
println("Surveillance points positioned:", objective_value(m))
for i in 1:nb_lignes
for j in 1:nb_colonnes
if value(surveillant[i, j]) > 0.5
push!(resultats_optim, (i - 1, j - 1))
end
end
end
println(resultats_optim)
# Write the results to a file
fichier = open("Submissions/res_16.txt", "w")
write(fichier, "EQUIPE theo_thimote.jpeg\n")
write(fichier, "INSTANCE 16\n")
for resultat in resultats_optim
x, y = resultat
write(fichier, "$x $y\n")
end
close(fichier)
```