Restrições personalizadas no CP Optimizer

Para começar, algumas ressalvas: existe esse post muito bom feito pelo Joris Kinable, e também existe algum exemplo, embora limitado, no manual de extensões do CP Optimizer, que para versão 12.7 pode ser obtido aqui.

O manual do CP Optimizer recomenda a utilização de restrições personalizadas somente quando as restrições predefinidas não satisfaçam as necessidades do seu modelo. Ainda sugere o uso de propagadores de restrições, que é uma forma mais simples de definir uma restrição personalizada. Mas uma restrição personalizada pode ser necessária quando por exemplo você precisa resolver um subproblema dentro da sua restrição.

Pode ser também que você queira propagar sua restrição apenas quando os domínios das variáveis tenham algum tipo de particularidade, como por exemplo quando uma variável é fixada. Outra alternativa para trabalhar com restrições heterogêneas é usando restrições catalizantes.

Nota importante: Quando você escreve uma nova classe de restrição, você precisa implementar o algoritmo de inferência que elimina os valores inviáveis do domínio das suas variáveis, através dos modificadores elementares que são para uma dada variável/expressão (IlcIntExp) x:

x.setValue(1); //fixa o valor de x, se 1 não for domínio de x, teremos um erro.
x.setMin(1); //atribui 1 como menor valor de x
x.setMax(3); //atribui 3 como maior valor de x
x.setRange(1, 3); //faz a expressão x ficar entre 1 e 3

Para uma variável de intervalo (IlcIntVar) y os modificadores elementares são:

y.setRange(IlcIntArray array); //faz y ter somente valores em array
y.removeValue(1); //remove 1 do domínio de y
y.removeInterval(1, 3); //remove o intervalo [1, 3] do domínio de y

Os modificadores elementares somente removem domínio das variáveis, nunca aumentam ou incluem.

Invariantes

As restrições são responsáveis por manter invariantes do seu modelos, no mesmo sentido que a palavra é usada em análise de algoritmos. Um exemplo retirado do manual do CP Optimizer é o seguinte: Suponha a restrição x <= y, a invariante dessa restrição pode ser expressa da seguinte forma:

• os valores no domínio de x devem ser menores ou iguais ao maior dos valores do domínio de y;
• os valores no dominio de y devem ser maiores ou iguais ao menor dos valores do domínio de x.

Com os modificadores elementares essas invariantes pode ser expressadas como:

x.setMax(y.getMax()); 
y.setMin(x.getMin());

Quando Propagar?

Quando definindo uma restrição personalizada você precisa definir os eventos que vão disparar a propagação dessa restrição. Você faz isso no método post, que exemplificaremos mais tarde. Os eventos possíveis são:

• value, para quando uma variável é fixada;
• range, para quando o mínimo do domínio aumenta ou o máximo diminui;
• domain, qualquer modificação do domínio de uma variável.

Programando a Restrição

Para criar sua restrição personalizada você precisa definir uma subclasse da classe IlcConstraintI, nela você precisara definir o método post() que basicamente diz quando ativar aquela restrição, e o método propagate() que diz como garantir as invariantes da sua restrição, removendo do domínio das variáveis os valores inconsistentes. O cabeçalho da sua classe vai ser algo assim:

#include <ilcp/cpext.h>
class MyConstraintI : public IlcConstraintI {
private:
  //Membros da sua restrição
public :
  MyConstraintI(IloCP cp, ... args ...); // constructor
  ~MyConstraintI(){} // destructor; 
  void post();
  void propagate();
}