Last update: 03/11/2021 (the original page has been moved to the CommaLAB web site, although a redirect has been kept)
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, FrFG16] 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 [FrFG16] 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.
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
[FrFG16] A. Frangioni, F. Furini, C. Gentile “Approximated Perspective Relaxations: a Project&Lift Approach” Computational Optimization and Applications 63(3), 705–735, 2016