Local search: nonlinear programming engine

This page describes the separator of the nonlinear programming engine of the local search. It requires Knitro: PackingSolver must be built with -DPACKINGSOLVER_USE_KNITRO=ON.

Principle

As in the linear programming engine, the items may be shrunk instead of overlapping, and a separation solves a sequence of programs, each one moving the items slightly and maximizing their weighted scales. The programs are nonlinear, so that the items may also rotate within their allowed rotation ranges, which is useful for the items with continuous rotations.

The shrunk items, the loss, the separation, the guided local search weights, the initial layout and the disruption are the same as in the linear programming engine. The distance between two layouts also counts the rotations of the items.

Nonlinear program of a step

A step builds a nonlinear program for each bin, around the current layout.

Input:

  • the items \(i\) of the bin; for each item \(i\): its current position \(\bar{p}_i\), the maximum move \(\delta_i\), its rotation range \([\theta^{\min}_i, \theta^{\max}_i]\) relative to its current angle (at most 5° in each direction, for the item types with continuous rotations, decreasing with the movement ratio; \(\{0\}\) otherwise), its area \(a_i\) and its guided local search weight \(g_i\)

  • the convex parts of the items; for each part \(P\) of an item \(i(P)\): its vertices and its center \(c_P\), relative to the reference point of the item, at its current angle

  • the obstacles of the bin, decomposed into convex parts, which don’t move

  • the pairs of parts which may get close to each other during the step, with their spacing \(s\)

  • the bounding box of the bin and the item-bin spacing

The position in the bin of a vertex \(u\) of a part \(P\) of an item at position \(p\), rotated by \(\theta\), with scale \(\lambda\) is

\[U(u) = p + R(\theta) \big( c_P + \lambda (u - c_P) \big)\]

where \(R(\theta)\) is the rotation of angle \(\theta\). For an obstacle, it is the vertex itself.

Variables:

  • \(p_i \in \mathbb{R}^2\): the position of the reference point of item \(i\), in the box \(\bar{p}_i \pm \delta_i\), and such that the centers of its parts are in the bin

  • \(\theta_i \in [\theta^{\min}_i, \theta^{\max}_i]\): the rotation of item \(i\) around its reference point

  • \(\lambda_i \in [0, 1]\): the scale of item \(i\)

  • \(\alpha_{PQ} \in \mathbb{R}\) and \(\beta_{PQ} \in \mathbb{R}\), for each pair of parts \((P, Q)\): the angle of the normal \(n(\alpha_{PQ}) = (\cos \alpha_{PQ}, \sin \alpha_{PQ})\) and the offset of a line separating the two parts

Objective: maximize the weighted scales of the items

\[\max \sum_i g_i \, a_i \, \lambda_i\]

Constraints:

  • Separation: for each pair of parts \((P, Q)\), the vertices of \(P\) are on one side of the separating line, and the vertices of \(Q\) on the other side, at least at the spacing

\[\forall u \in P \qquad \beta_{PQ} - n(\alpha_{PQ}) \cdot U(u) \ge 0\]
\[\forall u \in Q \qquad n(\alpha_{PQ}) \cdot U(u) - \beta_{PQ} \ge s\]

  • Containment: the vertices of the parts which may reach the borders of the bounding box of the bin stay inside it, minus the item-bin spacing; for the left side of the bin, for example:

\[U(u)_x \ge X^{\min} + s_{\text{bin}}\]

Two convex parts don’t overlap if and only if such a line exists, so, unlike in the linear programming engine, no separating edge needs to be selected: the optimization chooses the lines. These are the quasi-phi-functions of Stoyan, Pankratov and Romanova (2016).

The lines are initialized with the lines separating the parts with the largest gap in the current layout (or with the smallest penetration if they overlap), computed exactly from the Minkowski difference of the two parts.

Always feasible. As in the linear programming engine, the current positions with null scales are a solution: the parts are then reduced to their centers, which stay in the bin, and two distinct centers can always be separated by a line. The exceptions are a center inside an obstacle, and two centers closer than the spacing.

The programs are solved with the interior point method of Knitro, with tight feasibility tolerances so that the solutions pass the exact overlap checks. The active set and SQP methods of Knitro don’t move away from the warm start.

Strengths and limitations

The nonlinear programs are much more expensive than the linear ones: a step can take from a tenth of a second to several seconds, so on large instances the engine barely moves from its initial layout within typical time limits. It is not part of the automatic selection.

It can be selected with --use-local-search-nonlinear-programming 1 (CLI) or use_local_search_nonlinear_programming (Python).

Source files

  • src/irregular/nonlinear_programming/separation_model.hpp, src/irregular/nonlinear_programming/separation_model.cpp: the nonlinear program of a step

  • src/irregular/nonlinear_programming/separating_line.hpp, src/irregular/nonlinear_programming/separating_line.cpp: the initial separating lines

  • src/irregular/nonlinear_programming/separator.hpp, src/irregular/nonlinear_programming/separator.cpp: the separator

References: