Formulação não-linear

Queremos colocar $k$ retângulos de dimensões $(l,w)$ em uma região convexa de tal maneira que não ocorra superposições entre os retângulos.

Se a região convexa é um retângulo, então o objetivo é encontrar $r = (r_x^1, r_y^1, r_x^2, r_y^2, \ldots , r_x^n, r_y^n)$, onde $r_x^i$ é a coordenada $x$ do centro do retângulo $i$ e $r_y^i$ é a coordenada $y$ do centro do retângulo $i$, resolvendo o problema:

$$\begin{array}{ll} \mbox{Minimizar} & f(r)\\ \mbox{sujeito a... ..._y^i \le u(r_y^i), \mbox{ para } i = 1, \ldots , k. \end{array}$$

onde $f(r)$ é uma das funções vistas na Seção e $l(x)$ é o limitante inferior de $x$ e $u(x)$ é o limitante superior de $x$.

Se a região convexa, definida pela função $h(r)$, não é um retângulo, então o objetivo é encontrar $r = (r_x^1, r_y^1, r_x^2, r_y^2, \ldots , r_x^n, r_y^n)$, onde $r_x^i$ é a coordenada $x$ do centro do retângulo $i$ e $r_y^i$ é a coordenada $y$ do centro do retângulo $i$, resolvendo o problema:

$$\begin{array}{ll} \mbox{Minimizar} & f(r)\\ \mbox{sujeito a} & \\ & h(r) \le 0. \end{array}$$

Que pode ser alterada para que, caso $h(r)$ seja positiva, a função sofra uma penalidade. Assim, podemos resolver o problema:

$$\begin{array}{ll} \mbox{Minimizar} & f(r) + \max ( 0, h(r) )^2\\ \end{array}$$

Se o valor da função objetiva no minimizador global desses problemas é zero então a resposta do problema de decisão é SIM, caso contrário, a resposta é NÃO.

Observe que os problemas descritos acima são problemas de otimização contínua onde a função objetiva tem a primeira derivada contínua.