1
$\begingroup$

Suppose, we want to locate some given facilities $\left \{ (i,j) \ |\ (i,j) \in \text[{1,\cdots, N}]\right \}$ in a specific area. Each facility has a predefined dimension with a length $l_{i}$ and width $w_{i}$, (they are not necessarily square). The overall dimensions of the area are $L$ and $W$. The objective is to find the best fit shape of the facilities in the area. As far as I know, this problem can be formulated as mixed-integer programming by defining the non-overlap constraints as follows:

\begin{align} &x_i+w_i \le x_j & \text{or} \\ &x_j+w_j \le x_i & \text{or} \\ &y_i+h_i \le y_j & \text{or} \\ &y_j+h_j \le y_i \end{align}

or other formulations like $\text{ABS}$ models in the facility location literature.

The important thing is that to achieve a good feasible solution by the above-mentioned formulations, we should define the facility shape in the fixed orientation as prior, for example horizontal. What I am interested to know is about the orientation of the facility shape and rotation of them by formulation. I was wondering if, how we can change the above formulation to capture the rotation of the facility shape automatically by using mixed-integer programming?

$\endgroup$
2
  • $\begingroup$ Do you instead mean $N$ facilities $i\in\{1,\dots,N\}$? $\endgroup$ – RobPratt Apr 23 at 13:58
  • $\begingroup$ @RobPratt, $i$ and $j$ are the facilities index and belong to set {1, ..., N}. $\endgroup$ – A.Omidi Apr 23 at 14:11
2
$\begingroup$

It sounds like you want to pack $N$ rectangles with given dimensions $w_i \times h_i$ in a $W \times H$ rectangle, as discussed here. To allow each rectangle to be rotated 90 degrees (with dimensions $h_i \times w_i$), you can introduce a binary variable $r_i$ to indicate whether to rotate rectangle $i$ or not. Then modify the constraints like this:

\begin{align} &x_i+w_i(1-r_i)+h_i r_i \le x_j & \text{or} \\ &x_j+w_j(1-r_j)+h_j r_j \le x_i & \text{or} \\ &y_i+h_i(1-r_i)+w_i r_i \le y_j & \text{or} \\ &y_j+h_j(1-r_j)+w_j r_j \le y_i \end{align}

$\endgroup$
1
  • $\begingroup$ Dear Dr. Pratt, many thanks for your useful answer. It works fine. :) $\endgroup$ – A.Omidi Apr 23 at 20:40

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.