This page contains a collection of realistic radar allocation problems that originate from a project currently carried out at the Swedish Institute of Computer Science (SICS) in cooperation with Celcius Tech. It is coordinated by Seif Haridi and Per Brand. More project information.

The problem is to allocate a number of radar stations for observation of a geographic area, such that each point is observed by at least three stations. As customary in the radar surveillance domain, the area is divided into hexagonal cells and radar stations are located in a number of cells. Each radar station can divide its signal scope circle into six sectors and each station can vary the signal strength in each sector independently from zero to some given maximum distance. Each cell must be covered by 3 radar stations (desired coverage, dc=3) and all coverage beyond this is to be minimized over-coverage for economic reasons and for detectability. Cells that physically cannot be covered by at least three stations must be covered by as many stations as possible and are then factored out.

The radar map below illustrates a small covering problem. The covering of the cells below is optimal: The over-coverage of the solution is 6 and the LP lower bound is 5.5 (which proves the optimality). An over-constrained pseudo-Boolean encoding (.epb file) was solved to produce this solution by WSAT(PB) in approx. 1s.

 Legend: Yellow triangles: radar units, here max range 3 Turquoise cells: perfectly covered cells Blue cells: cells with over-coverage 2 or 3 Orange cells: under-covered cells Red triangle: selected radar unit Black checkers: cells covered by red unit

The modelling was developed by Seif Haridi, Per Brand and Olle Olsson at SICS. WSAT(PB) is being developed by J.P. Walser at Programming Systems Lab, Saarbruecken. The map is a screen shot of the Argus application developed at SICS and written in Oz.

## Test Problems

A set of 12 test instances, randomly generated as described in Solving Linear Pseudo-Boolean Constraint Problems with Local Search and in a forthcoming SICS technical report. Problem sizes are 10x10, 10x20, 30x30, and 30x70 cells; the problems also vary in the percentage of insignificant cells (0% and 2%) and spread (even and uneven). Experimental results (revised 6/19/97)