Linearização de desigualdades não-lineares

Há algum tempo atrás, assisti uma apresentação em que o palestrante chegou a uma equação não linear e disse que era possível linearizá-la, entretanto sem dizer como, apenas passando uma referência.

Não consegui encontrar a referência na época, mas recentemente alguém postou no OR Exchange (sistema semelhante ao StackOverflow, mas voltado à Pesquisa Operacional) uma dúvida relacionada. Uma das respostas passou uma referência para um documento do AIMMS chamado Integer Programming Tricks [1].

Nesse documento há algumas técnicas de modelagem de programação linear inteira. Algumas delas eu já conhecia como por exemplo modelar restrições disjuntas (quando exatamente uma de duas restrições deve ser satisfeita).

A novidade é a técnica usada para transformar um produto de duas variáveis, por exemplo x_1 \cdot  x_2, em uma equação linear. Há três casos que devemos considerar: quando ambas variáveis são binárias; quando uma das variáveis é binária e a outra é contínua; e quando as duas variáveis são contínuas.

Caso 1: Ambas variáveis binárias

No caso em que ambas x_1 e x_2 são binárias, a modelagem é fácil:

(1) \, y \le x_1

(2) \, y \le x_2

(3) \, y \ge x_1 + x_2 - 1

(4) \, y \in \{0, 1\}

Fazendo as 4 possíveis combinações de valores, é fácil ver que y = x_1 \cdot x_2.

Caso 2: Uma das variáveis é contínua

A formulação nesse caso não é muito diferente. Vamos supor que é x_2 a variável contínua e é limitada por 0 \le x_2 \le u. Temos:

(5) \, y \le u \cdot x_1

(6) \, y \le x_2

(7) \, y \ge x_2 - u(1 - x_1)

(8) \, y \ge 0

Se x_1 = 0, temos que y = 0. Se x_1 = 1, então (7) vira y \ge x_2, que combinado com (6), implica y = x_2.

Caso 3: Ambas as variáveis contínuas

Esse caso é bem mais complicado e requer a introdução de um novo conceito: formulações lineares por partes (numa tradução livre de piecewise linear formulation).

Formulação linear por partes

Essa técnica consiste em aproximar uma dada função/restrição não-linear por uma função linear por partes, e é bastante comum em métodos numéricos.

Uma função é linear por partes (piecewise linear function) se pudermos subdividir o domínio em intervalos nos quais a função é linear.

x

Função não linear aproximada por uma função linear por partes

As funções que podem ser aproximadas por essa técnica devem ser separáveis. Uma função é separável se ela pode ser escrita como a soma de funções que só dependem de uma variável. Por exemplo, x_1^3 + x_2^2 é separável, mas x_1 \cdot x_2 não é.

Assim, dada uma função separável, considere uma função g do somatório. Suponha que aproximamos g usando uma função linear por partes f, com intervalos definidos pelos pontos x_1, x_2, \cdots, x_n, sendo que a função f entre x_i e x_{i+1} é linear.

Podemos modelar a função f(x) através de programação linear. Para isso, considere as variáveis contínuas \lambda_i, tal que 0 \le \lambda_i \le 1. Temos então

(9) \, \sum_{i=1}^n \lambda_i = 1

(10) \, f(x) = \sum_{i=1}^{n} f(x_i) \lambda_i

(11) \, x = \sum_{i=1}^{n} x_i \lambda_i

Com a restrição adicional de que no máximo dois \lambda‘s sejam não nulos e no caso de serem dois, esses \lambda‘s devem ser consecutivos. A ideia é que se só um \lambda_i for não nulo, ele representa x_i e f(x_i). No caso de \lambda_i e \lambda_{i+1} serem não nulos, eles representam x' = x_i \lambda_i + x_{i+1} \lambda_{i+1} e f(x') =  f(x_i) \lambda_i + f(x_{i+1}) \lambda_{i+1}.

Note que como \lambda_i + \lambda_{i+1} = 1, [x', f(x')] é uma combinação convexa de [x_i, f(x_i)] e [x_{i+1}, f(x_{i+1})] e portanto pertence à reta que une esses dois pontos.

Essa restrição pode ser embutida no algoritmo do simplex. Para isso, os resolvedores de programação linear inteira usam o SOS2 (Special Order Sets 2), no qual devemos especificar o conjunto de variáveis x_i e f(x_i) (os SOS2 não tem nada a ver com SOS1, sobre o qual falei num post anterior).

Entretanto, alguns resolvedores como o GLPK não possuem essa funcionalidade embutida. Em [2], eles apresentam uma formulação de PLI para modelar essa restrição.

São introduzidas novas variáveis binárias, z_i para i = 1, \cdots, n-1. Temos que z_i = 1 se e somente se, o valor de x está entre x_i e x_{i+1}. Também introduzimos uma variável contínua s_i para i = 1, \cdots, n-1, onde 0 \le s_i \le 1. Nesse caso s_i representa a combinação convexa entre x_{i} e x_{i+1}.

Definindo y_i = f(x_i) para i = 1, \cdots, n e y = f(x), temos o seguinte conjunto de restrições:

(12) \, \sum_{i = 1}^{n-1} z_i = 1

(13) \, s_i \le z_i

(14) \, x = \sum_{i = 1}^{n-1} x_i z_i + (x_{i+1} - x_{i}) s_i

(15) \, y = \sum_{i = 1}^{n-1} y_i z_i + (y_{i+1} - y_{i}) s_i

Como z_i‘s são binárias, exatamente um z_j será igual a 1 (e o resto zero). Nesse caso, (14) reduzirá para:

x = x_j + (x_{j + 1} - x_{j}) s_j,

que podemos reescrever como

x = x_j (1 - s_j) + x_{j+1} s_j

Para a equação (15) teremos, de maneira análoga:

y = y_j (1 - s_j) + y_{j+1} s_j

Ficando mais evidente ver que [x, y] é combinação convexa de [x_j, y_j] e [x_{j+1}, y_{j+1}].

Eliminação do produto de variáveis diferentes

Agora que vimos como fazer a formulação linear por partes, vamos ver como linearizar x_1 \cdot x_2 supondo que ambas são contínuas.

Para esse fim, definimos duas variáveis y_1 = \frac{1}{2} (x_1 + x_2) e y_2 = \frac{1}{2} (x_1 - x_2). Agora é fácil ver que y_1^2 - y_2^2 = x_1 \cdot x_2, e é uma função separável.

Agora podemos usar a formulação apresentada anteriormente da seguinte forma: aproximar y_1^2 usando k pontos (note o tradeoff entre precisão e tempo de execução), gerando pares [{y_1}_i, {y_1}_i^2] para i = 1, \cdots, k. Agora basta substituir ocorrência de y_1 pelo ‘x’ de (14) e y_1^2 pelo ‘y’ da equação (15). Repetimos o mesmo procedimento para a função -y_2^2.

Pronto! Agora todas as restrições do modelo são lineares!

Conclusão

Aprendi uma técnica muito útil para atacar alguns problemas com funções/restrições não-lineares. Ainda pretendo aprender programação não-linear, quer cursando uma disciplina, quer estudando um livro por conta.

Fiquei na dúvida sobre como aproximar uma função com domínio muito grande. Podem ser necessários muitos intervalos para uma boa aproximação e o número de variáveis cresce proporcionalmente.

Outra pergunta que não sei responder é o que dá para fazer quando ambas as variáveis são inteiras. É possível transformar uma variável inteira em binária, mas novamente, dependendo do tamanho do domínio das variáveis inteiras, a formulação pode ficar com um tamanho demasiadamente grande. Será que existe um jeito mais eficiente de linearizar x_1 \cdot x_2 nesse caso?

Só descobri esse material graças ao tópico no OR Exchange. Por sua vez, só fiquei sabendo do tópico graças ao twitter do OR Exchange. Aliás, tenho conseguido usar o twitter como ferramenta para obtenção de informações (úteis!). A maior parte das contas que passei a seguir ultimamente são agregadores de notícias/links relacionados à pesquisa operacional.

Referências

[1] AIMMS Modelling Guide – Integer Programming Tricks
[2] SOS2 constraints in GLPK

Os comentários estão fechados.

%d bloggers like this: