---

PYTHON VERSION

Surveillance Optimization Algorithms

---

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.

Local Search Algorithm: We devised a local search approach that iteratively explored the neighboring solutions to improve the objective function. This method aimed to find local optima by iteratively making small adjustments to the initial solution.

Greedy Algorithm: The greedy algorithm focused on making locally optimal choices at each step with the hope of finding a global optimal solution. It involved selecting the best possible decision at each stage without considering the long-term impact.

Genetic Algorithm: Inspired by the process of natural selection, we designed a genetic algorithm that involved creating a population of potential solutions, applying genetic operations like mutation and crossover, and selecting the best-fit individuals for the next generation.

Heuristic Algorithm: The heuristic algorithm employed a rule-based approach to make educated guesses and approximate solutions efficiently, even if not guaranteed to be optimal.

Recursive Algorithm: We also experimented with a recursive approach, where the algorithm called itself with smaller subsets of the problem until reaching a base case and then backtracked to find the optimal solution.

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.

---

JULIA VERSION

Solving an Integer Linear Programming Problem

---

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:

Imports: The code begins by importing two required libraries, JuMP and HiGHS, which are used for mathematical modeling and optimization, respectively.

`is_visible` Function: This function checks if a target is visible from a given surveillance point on a grid. It takes the coordinates of the target and surveillance point as inputs, along with the grid containing obstacle information. The function uses simple geometric calculations to determine visibility, ensuring there are no obstacles in the line of sight.

Reading Input and Initializing the Grid: The code reads input data from the file "Instances/gr16.txt." The first two lines of the file provide the number of rows and columns in the grid. The subsequent lines specify the locations of targets and obstacles. The grid is initialized with zeros, and each target and obstacle location is marked with a value of 1 and 2, respectively.

`assign` Function: This function is a helper function that assigns values (1 or 2) to the grid cells based on the input "objet," which can be either "CIBLE" (target) or "OBSTACLE."

JuMP Model Creation: The code creates a JuMP model using the HiGHS optimizer. JuMP provides an intuitive way to define the optimization problem and the variables to be optimized.

Decision Variables: The code defines decision variables `surveillant` as a binary matrix. Each element (i, j) in the matrix indicates whether there is a surveillance point at position (i, j) in the grid.

Constraints: The code creates constraints to ensure that each target is observed by at least one surveillance point. It iterates through each target location and adds a constraint that sums the surveillance points' variables within the visibility range of the target. If a target is visible from a surveillance point and there are no obstacles in the line of sight, the constraint is added.

Objective Function: The objective is to minimize the number of surveillance points needed. Therefore, the code defines an objective function that sums the surveillance point variables across the entire grid.

Time Limit Setting: The code sets a time limit of 180 seconds for the optimization process to avoid excessive computation time.

Model Optimization: The code calls the `optimize!` function to solve the optimization problem and find the minimum number of surveillance points.

Result Display: After solving the optimization problem, the code displays the positions of the surveillance points and the total number of surveillance points used.

Writing Results to File: The code writes the results to the file "Submissions/res_16.txt." It includes the team name ("EQUIPE theo_thimote.jpeg"), the instance number ("INSTANCE 16"), and the coordinates of the surveillance points.

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)