AlgoBOWL Competition - 2nd Place Finish
CS@Mines' AlgoBOWL assigned an NP-hard problem and required teams to: (1) create very large, adversarial inputs for the teams to solve, (2) design and run your team's solver on inputs from all teams, and (3) verify solution validity for other team's solution submissions. For our semester's competition, teams were given the Tents & Trees problem to attempt to create the most optimized solver for. In this problem, the individual is given a grid with ‘trees’ placed in various squares and requirements for the number of tents to be contained in each row and each column. The ‘catch’ is that the tree placements and the row and column requirements do not have to be theoretically possible to fully fulfill. The overall goal is to minimize the number of violations of the following rules: (1) All trees need at least one tent placed in an adjacent space. (2) Tents cannot be placed within the 8 surrounding spaces of another tent. (3) Rows and columns must each have their designated exact amount of tents within them.
For each input, our heuristic script ran a variety of heuristic solutions for tent placements, including adjacency-averse, tree-proximity, row/column-quota, combined tree proximity and adjacency-aversion, future-flexibility, and density-weighted variants, then kept the single best (lowest-violation) output for that input as the starting point for our Tabu search.
From the best heuristic seed per input, the Tabu search explored local add/remove moves, kept a short-term tabu list to prevent falling into cycling over local minimums, and accepted the best admissible neighbor (with aspiration when an improving move beat best-so-far). We stopped on zero violations, after a budgeted number of iterations/time, or once we observed no meaningful progress being made, which then we'd tweak the algorithm's hyperparameters.
For every finalized solution, we recomputed matchings to emit the required format (total violations, tent count, then 1-indexed tent coordinates with U/D/L/R or X for unmatched) and validated submissions before turn-in. Through tracking our placement closely and amidst fierce competition, we placed 2nd out of 50+ teams of senior and graduate-level students.
For each input, our heuristic script ran a variety of heuristic solutions for tent placements, including adjacency-averse, tree-proximity, row/column-quota, combined tree proximity and adjacency-aversion, future-flexibility, and density-weighted variants, then kept the single best (lowest-violation) output for that input as the starting point for our Tabu search.
From the best heuristic seed per input, the Tabu search explored local add/remove moves, kept a short-term tabu list to prevent falling into cycling over local minimums, and accepted the best admissible neighbor (with aspiration when an improving move beat best-so-far). We stopped on zero violations, after a budgeted number of iterations/time, or once we observed no meaningful progress being made, which then we'd tweak the algorithm's hyperparameters.
For every finalized solution, we recomputed matchings to emit the required format (total violations, tent count, then 1-indexed tent coordinates with U/D/L/R or X for unmatched) and validated submissions before turn-in. Through tracking our placement closely and amidst fierce competition, we placed 2nd out of 50+ teams of senior and graduate-level students.