## One-dimensional Sensor Placement Problems

This page distributes instances of the *1-D Sensor Placement
Problem*, whereby a set of *n* sensors have to be optimally
placed to cover a given area while minimizing the fixed deployment cost
plus an energy cost that is linear in the surface covered (and therefore
quadratic in its radius). This Mixed-Integer Quadratic Program (MIQP) is
solved in [FGGP11, FrFG13] by approaches based on the "(Approximatd)
Projected Perspective Relaxation" to MIQPs with specific structure
(nonlinear separable semicontinuous variables).

The first two groups are randomly-generated instances with either 2000 or
3000 sensors. The first group is composed of 120
instances with randomly generated gaussian data; please refer to [FGGP11]
and to the readme of the generator for more
details. The second group is composed of 48
instances that have been generated according to the *NP*-hardness proof
of the problem [AgGP12], that is, starting from a PARTITION instance. Please
refer to the cited sources and to the readme of the
generator for more details.

Both these groups happen to be "easy", i.e., they are most often solved
at root when using appropriately tight formulations. For [FrFG13] we have
therefore developed a small set of "harder" ones
by replicating smome of he PARTITION and SUBSET SUM instances that can be
found here and then applying the reduction procedure from
PARTITION as in [AgGP12]. These instances do require a fair amount of
branching even when tackled with the best exact approaches known so far.

Last updated: 07/05/2013.

### Bibliography

[AgGP12] A. Agnetis, E. Grande, A. Pacici "Demand Allocation with
Latency Cost Functions" *Mathematical Programming* **132**(1-2),
277–294, 2012

[FGGP11] A. Frangioni, C. Gentile, E. Grande, A. Pacifici
"Projected
Perspective Reformulations With Applications in Design Problems"
*Operations Research* **59**(5), 1225–1232, 2011

[FrFG13] A. Frangioni, F. Furini, C. Gentile
"Approximated
Perspective Relaxations: a Project&Lift Approach" *Technical Report*
**13-04**, Dipartimento di Informatica, Università di Pisa, 2013