Esse problema é conhecido em inglês como Two-dimensional Orthogonal Packing Problem, aqui vamos abrevia-lo para 2OPP. Nesse problema são dados um retângulo grande, chamado recipiente, um conjunto de retângulos menores, chamados de itens e desejamos decidir se existe um empacotamento dos itens dentro do recipiente.
A figura abaixo tem um exemplo de instância do 2OPP. Queremos saber se os itens a esquerda são empacotáveis no recipiente a direita:
Em um empacotamento:
Caso exista tal empacotamento, devemos devolver as posições onde cada item pode ser empacotado. Caso o empacotamento não exista, é necessário ter certeza disso antes de responder negativamente.
Esse problema surge em diversos contextos, por exemplo, quando uma empresa precisa obter itens retangulares de uma chapa de madeira ou metal, ou quando precisamos carregar um caminhão com geladeiras, móveis ou pallets que não podem ser empilhados. O problema também surge no armazenamento de itens em um depósito e em diversas outras situações.
Ainda, menos intuitivo, esse problema também aparece quando engenheiros elétricos precisam dispor chips, componentes, baterias etc, em uma placa eletrônica. Muitos outros problemas recaem no 2OPP, por isso ele é tão importante e tão estudado.
Meu objetivo aqui é mostrar uma das modelagens mais intuitivas e elegantes para esse problema, utilizando programação por restrições (constraint programming em inglês). Ela é aceitável no quesito de eficiência, embora existam outras formulações e algoritmos capazes de encontrar uma solução mais rapidamente.
O problema foi modelado em linguagem de programação c++ para ser executado pelo resolvedor de programação por restrições CP Optimizer 12.7.0, um componente do IBM ILOG CPLEX Optimization Studio 12.7.0.
Primeiramente definimos a largura e a altura do recipiente, respectivamente W (de Width) e H (de Height). No caso do exemplo da Figura 1, W = 20 e H = 40. Depois definimos o número de itens, no exemplo queremos empacotar cinco itens, e as dimensões de cada um dos itens.
As variáveis do problema são X[i] e Y[i] para cada item i, indicando a posição onde o item é empacotado. O domínio de cada variável X[i], ou seja, os valores que a variável pode assumir, é o conjunto de inteiros entre 0 e W – w[i]. Analogamente, o domínio de Y[i] está entre 0 e H – h[i]. Garantindo que a posição de um item está nesse domínio, já garantimos que os itens não ultrapassem as bordas do recipiente.
Definidas as variáveis, iremos adicionar restrições que impeçam a sobreposição dos itens. Intuitivamente essa restrição diz que para cada par de item i e j, eles devem ser disjuntos em algum dos eixos, ou seja, uma dessas quatro desigualdades deve ser satisfeita:
X[i] + w[i] ≤ X[j] OU
X[j] + w[j] ≤ X[i] OU
Y[i] + h[i] ≤ Y[j] OU
Y[j] + h[j] ≤ Y[i].
Essa restrição garante a não sobreposição dos itens e com isso o modelo está completo. O resolvedor ira procurar uma atribuição de valores para as variáveis X[i] e Y[i] para todos os itens i, dentro do domínio de cada uma delas, e que não viole a restrição acima. Como a programação por restrições procura por todas as possíveis combinações de valores, garantimos que, se ele não encontrar uma solução é porque ela realmente não existe.
Veja como fica o código:
IloEnv env; //ambiente do CP Optimizer
IloModel mdl(env); //modelo do problema
IloInt W = 20; //largura do recipiente
IloInt H = 40; //altura do recipiente
IloInt number_of_items = 5;
IloIntArray w(env, number_of_items);
IloIntArray h(env, number_of_items);
//dimensoes dos itens
w[0] = 15; h[0] = 10;
w[1] = 10; h[1] = 20;
w[2] = 10; h[2] = 30;
w[3] = 5; h[3] = 10;
w[4] = 5; h[4] = 20;
//variaveis do problema
IloIntVarArray X(env);
IloIntVarArray Y(env);
//Dominio das variaveis
for (IloInt i = 0; i < number_of_items; i++) {
X.add(IloIntVar(env, 0, W - w[i]));
Y.add(IloIntVar(env, 0, H - h[i]));
}
//Restrições de não sobreposição
for (IloInt i = 0; i < number_of_items; i++) {
for (IloInt j = i + 1; j < number_of_items; j++) {
mdl.add(X[i] + w[i] <= X[j] || X[j] + w[j] <= X[i] || Y[i] + h[i] <= Y[j] || Y[j] + h[j] <= Y[i]);
}
}
IloCP cp(mdl); //resolvedor do CP Optimizer
//executando o resolvedor
if (cp.solve()) {
//imprimindo a solução
for(IloInt i = 0; i <number_of_items; i++){
std::cout << i << " (" << cp.getValue(X[i]) << ".." << cp.getValue(X[i]) + w[i] << ", "
<< "" << cp.getValue(Y[i]) << ".." << cp.getValue(Y[i]) + h[i] << ")" << std::endl;
}
} else {
cp.out() << "No solution found" << std::endl;
}
Resolvendo esse modelo com o CP Optimizer, concluímos que o exemplo da Figura 1 é viável, ou seja, existe uma disposição no qual os aqueles itens cabem no recipiente disponibilizado. Obtemos a seguinte solução:
