Citing this page:

Use the BibTeX entry:

@Misc{csr2018,
 author = {Rafael G. Cano and Cid C. de Souza and Pedro J. de Rezende},
 title = {Geometric Knapsack -- Instances and Experimental Results},
 year = {2018},
 note = {{\sl www.ic.unicamp.br/$\sim$cid/Problem-instances/Geometric-Knapsack}}
}

Problem description

Geometric knapsack problems (GKP) are extensions of the classic knapsack problem to a geometric setting. In the classic version, we are given a set of items with specified weights and values, together with a knapsack of limited capacity. The objective is to select a subset of items whose combined weight does not exceed the capacity of the knapsack and whose total value is maximum.

The geometric variants typically consist of the so-called fence enclosure problems. We study a two-dimensional version in which items are points in the plane. Consider a set P = {p₁, p₂, ..., p_n} of n distinct points. With each point p_i ∈ P there is an associated real value v_i, unrestricted in sign. The "knapsack" (also called fence) consists of a simple polygon, and the selected items are the points that it encloses. Unlike the classic variant, items do not have an explicit weight. However, there is a cost c per unit length of fence. The objective is to maximize the net profit given by the total value of the enclosed points minus the cost of the fence. An example is shown in Figure 1.

Figure 1: An instance of the GKP with an optimal fence. Positive and negative point values are represented by blue and red circles, resp., with radii proportional to the magnitude of the values.

---

Input Instances

Our proposed benchmark contains two sets of instances, which we refer to as uniform and layered instances. In the former, the coordinates and the value associated with each point are randomly selected from a uniform distribution. In the latter, point values are assigned according to the depth of each point in the list of convex layers of the point set; points in the outermost layers have a higher probability of receiving positive values, whereas the ones in the innermost layers tend to receive negative values. For more details, see the discussion in [1].

Each instance file contains, in the first line, an integer indicating the number n of points in the instance. Then, there are n lines, each containing three integers that represent the abscissa, the ordinate and the value of each point, respectively.

The complete benchmark can be downloaded here: Benchmark instances (18.9 K).

---

Experimental Results

As described in [1], we proposed and experimentally evaluated an integer linear programming (ILP) model that solves the GKP exactly. We ran our experiments on an Intel Xeon E5-2603, 1.60GHz CPU with 32GB RAM. Integer programs were solved with CPLEX 12.8 using traditional search with a single thread. The code was written in C++ and compiled with gcc 5.4.0. For each set of instances, we evaluated the behavior of our ILP using three fence cost values. We adopted a time limit of 5 minutes per instance.

We report, for each instance, the number of points n, the cost per unit length of fence c, the number of variables and constraints in the ILP, the number of cuts added during the resolution of each problem, the objective value after solving the linear relaxation at the root node and the corresponding running time, the best primal and dual bounds found during the search, and the total running time.

Our complete set of results that were reported in [1] can be downloaded here: Results (CSV format) (7.9 K)

---

Acknowledgments

This work was supported by Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq), grants #304727/2014-8 and #309627/2017-6 and by Fundação Amparo à Pesquisa do Estado de São Paulo (FAPESP) grant #14/12236-1.

---

References

• [1] Optimal Solutions for a Geometric Knapsack Problem using Integer Programming, R. G. Cano, Cid. C. de Souza, P. J. de Rezende, submitted (2018).

---

Address

Rafael G. Cano, Cid C. de Souza and Pedro J. de Rezende
Universidade Estadual de Campinas
Instituto de Computação
Av. Albert Einstein, 1251
13083-852, Campinas, SP, Brazil
Phone: +55 19 3521.5877
Fax: +55 19 3521.5847
e-mail: