Problem Statement

Penguins are the last remaining species on Earth and they must figure out how to defend themselves against intergalactic attacks. Penguin Labs has recently released defense towers that can successfully shield cities within a 3 mile radius from all attacks. Each tower takes 170 kilowatts to power. If towers are placed too close together, the resonance of intergalactic radiation will cause the tower to consume more energy than necessary.

As one of the 170 chosen penguin agents, you are tasked with placing these towers throughout the penguin empire such that all cities are safe and you minimize the energy consumption (global warming is not good for penguins).

Algorithm

I used Gurobi, a commercial mathematical optimization software, for my solution.

Each Gurobi optimization problem has three components: (1) variables, (2) constraints, and (3) objective function(s). My code instantiates each of these (in that order) and calls model.optimize() to solve the ILP.

• Variables: I create a binary variable for each point within coverage_radius of a city. Each binary represents a possible tower placement.
• Constraints: In order to have a valid solution each city must have a tower at most coverage_radius away. We use constraints to ensure this. How? When creating the variables for the possible tower placements we keep track which variables ‘belong’ to each city (i.e. points inside coverage_radius). Then, for each city, we make these surrounding variables (including the city itself) sum to one, i.e. there’s exactly one tower protecting each city. P.S. We force it to be exactly one to make the problem easier to solve for Gurobi. It’s a reasonable assumption to make in most cases. For the general case we could have the constraint be greater than or equal to 1.
• Objective Function: From the project spec, if a tower is placed, we need to add 170 * exp(# towers within penalty_radius). We achieve this by, for each variable, keeping track of all the other variables within penalty_radius of it (in dict called tower_constraints). Then, the cost for placing a tower is that variable times the exp of the sum of the nearby variables. Why? Well, if a variable does not have a tower, the penalty will never be applied since we multiply the exp by 0. On the other hand, if a tower is placed, the variable will be equal to 1 and we will get the corresponding penalty applied. We do this for each possible variable (i.e. tower placement position) and add them all up. This is our objective function. P.S. The actual code approximates exp with a line. This is make the optimization easier to solve. Without it, it would be too hard to solve for Gurobi.

Once we have defined all the above terms we call optimize. If the model is infeasible, we relax the infeasible city constraints to allow any number of towers to protect a city. We do this until the model is feasible. Finally, if there are multiple solutions, we get whichever one minimizes the real penalty function from the project spec.

Why Gurobi?

Gurobi allows me to use complicated optimization techniques without having to understand or know them. It also allows me to easily change parameters and test different methods. Using an ILP solver made sense to me since that’s almost how the problem is stated on the spec. In trying to achieve that, I had to make two simplifications from the original spec, (1) represent exp as a line and (2) one tower protects each city. These simplifications allowed me to find potential solutions in a reasonable amount of time without compromising too much on the spirit of the original optimization problem. It seems to have worked out quite well since I’m at the top of the leaderboard.

Other Approaches?

At the start I did some reasearch as to which optimizer to use. I tried cvxpy but it could not solve non-convex problems (which I actually didn’t really need in the end) so I ended up using Gurobi for a couple of reasons: (1) it claims to be the fastest solver, (2) supports MIPs and non-convex optimization, (3) has a free academic liscence, (4) has a python api, and (5) CS 170 TAs knew about it.

A lot of the time for this project was spent trying to simplify the problem as much as possible without deviating too much from the original project statement. I started by replicating the exact same optimization problem described in the spec, but Gurobi was too slow. In the end I decided to approximate exp with a linear function (tried quadratic but it was too slow and made my optimization problem non-convex) and having exactly one tower protecting each city (I tried having some sort of bound, but it made the code slower and often led to worse solutions). I also told Gurobi to focus on finding feasible solutions instead of proving optimality since I only ran the code for a fixed amount of time (800s) and wanted the best solution possible in the time. Side note: After talking to Rahul (TA) I looked into metaheuristics, but I figured it would be too much work to implement. Plus, I already had a pretty good solution with Gurobi.

Computation Resources

I just used my 2017 Macbook Air (Core i5, 8gb ram) to do all the computations. Since Gurobi would take almost an hour to find the optimal solution to the optimization problem. I simply had it stop after 800s and give me the best solution so far. This worked surprisingly well. All in all, the code would take ~18hrs to run on my laptop. I tried to use the hive, AWS, and GCP but it was too difficult to set up Gurobi/my code.

P.S. the reason why stopping after 800s worked well is because if you took a look at the logs there were massive diminishing returns, i.e. running it for 800s would be get Gurobi 95% close true optimal solution (which might take 3,600s (1hr) to actually reach).