I'm unsure of how to formulate my problem as an optimisation, any suggestion would be greatly appreciated.

I have a group of axis aligned rectangles that are all bounded by one larger rectangle. Each rectangle has an initial (x,y) centroid, height (fixed) and width.

enter image description here

The larger rectangle has a number of guides lines (0/4, 1/4, 1/3, 1/2, 2/3, 3/4, 4/4 vertical lines) that can be activated, but for each activated guide line there is an additional cost.

enter image description here

For each of the bounded rectangles I want to allow small changes in the centroid's x parameter and the width parameter, so the the rectangle width edges align to a guide line but for as few guide lines are activated as possible.

enter image description here


Based on your description of the problem I've reached the following MILP. I only considered the horizontal axis, assuming that the vertical axis is fixed. Note that is not applicable in the current form.

Let $S$ be the set of rectangles and $G$ the set of guidelines. For each rectangle $s \in S$ let:

  • $c^s$ be the center of $s$,
  • $w^s_L$ and $w^s_L$ be left/right border of $s$.

For each guideline $g\in G$ let:

  • $p^g$ be the position of guideline.
  • $b^g$ be the binary variable that gives the activation of the guideline $g$

Finally, for each $g$ and each $s$, the binary variables $b^{s,g}_L$ and $b^{s,g}_R$ are the variables that indicated that the left/right border of $s$ has been assigned to the guideline $g$.

\begin{align} \min\quad &\sum_{g\in G}b^g\\ \textrm{s.t.:}\qquad&\textrm{for all s }\in S: \\ &\qquad c^s= \frac{w^s_L+w^s_R}{2} \\ &\qquad w_L^s = \sum_{g\in G} p^g b_L^{s,g} \\ &\qquad w_R^s = \sum_{g\in G} p^g b_L^{s,g} \\ &\qquad \sum_{g\in G} b_L^{s,g} = 1\\ &\qquad \sum_{g\in G} b_R^{s,g} = 1\\ &\qquad b_L^{s,g} \leq b^g \qquad \forall g \in G\\ &\qquad b_R^{s,g} \leq b^g \qquad \forall g \in G\\ \end{align} Explanation of the constraints:

  • (1), the centroid position is the mean of the left and right border.
  • (2) and (3), the position of the left/right border is equal to the sum of position of the guideline that it has been assigned (only one can be assigned).
  • (4) and (5), for each $s$ and border side (left/right) only guideline can be assigned.
  • (6) and (7), the guidelines can only be assigned if the guide line is active.

Note that by the problem specification that you gave:

  • it is allowed to a rectangle to have width zero, therefore the solution will be only one guideline active. This can be avoided by adding a constraint $w^s_L-w_R^s\geq w^s_{\min}$.
  • there is no cost for stretching the rectangles or moving the centroid, therefore the solution will be always two guidelines active. You could add some parameters that represent the initial position and width of the rectangles which allows you to calculate the variations and penalize it. Avoid using the $\ell_2$ norm to calculate the variations, otherwise your problem will become a MIQP. There are ways to model absolute value ($\ell_1$ norm) using linear constraints.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.