Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Implementação de Integer Linear Programming usando Programação Dinâmica.

0 votos
14 visitas
perguntada Nov 4 em Ciência da Computação por VITOR B BORGES (1 ponto)  

A pergunta corresponde à Seção 2.14 localizado na página 63 do livro "Dynamic Programming: A computational tool" de Art Lew e Holger Mauch.

Podemos assumir que todas as entradas dos vetores \( \textbf{c} \), \( \textbf{b} \) e da matriz \( \textbf{A} \) são números inteiros não-negativos. Considere o problema de maximização com restrições '\( \leq \)'.

\[ max \space c^{T}x \\ s.t. \space Ax \leq b \\ x_{1}, ... , x_{n} \in \mathbb{N} \cup \{0\} \]

O enuncido propõe duas funções de recursão, a função que será utilizada nesta implementação é a seguinte:

\[ f(j, (y_{1},...,y_{m})) = \\ \small{ \left\{ \begin{matrix} \underset{x_{j+1} \in D}{max} \{ c_{j+1}x_{j+1} + f(j + 1, (y_1 - a_{1,j+1}x_{j+1}, ... , y_{m} - a_{m,j+1}x_{j+1})) \} &, if \space j < n\\ 0 &, if \space j = n \end{matrix} \right\} } \]

Em que os valores \( a_{i,j} \) são entradas da matriz \( \textbf{A} \). Uma decisão será tomada no estágio \( j \) assinalando à \( x_{j+1} \) um valor do um conjunto discreto de decisões factíveis \( D \).

O conjunto de decisões factíveis é definido da seguinte forma:

\[ D = D(j, (y_{1},...,y_{m})) = \{ 0, 1, ..., min\{ \lfloor \frac{y_{1}}{a_{1,j}} \rfloor, .. , \lfloor \frac{y_{m}}{a_{m,j}} \rfloor\} \} \\ set \space \frac{y_{i}}{0} \rightarrow \infty \]

A tupla \( (y_{1}, ..., y_{m}) \) é o vetor de restrições que passou para o próximo estágio da recursão. O objetivo do problema é computar \( f(0, (b_{1}, ..., b_{m})) \), com o \( j = 0\) e as restrições iniciais do problema.

O caso proposto é a seguinte instância do problema:

Seja \( c = (3, 5) \), \( b = (4, 12, 18) \) e

\[ A = \begin{pmatrix} 1 & 0 \\ 0 & 2 \\ 3 & 2 \end{pmatrix}. \]

Compartilhe

2 Respostas

0 votos
respondida Nov 4 por VITOR B BORGES (1 ponto)  
editado Nov 4 por VITOR B BORGES

A solução do problema de Programação Dinâmica será realizada na linguagem Python 3 e a biblioteca numpy (np).

Iremos iniciar esta implementação estabelecendo os parâmetros propostos pelo exercício.

c = np.array([
    [3],
    [5]])

b = np.array([
    [4],
    [12],
    [18]])

A = np.array([
    [1, 0],
    [0, 2],
    [3, 2]])

A primeira função gera o conjunto \( D \) de decisões factíveis.

def D(j, Y):

h = [] #esta lista vai estocar os valores de y divididos pelas
       #entradas a da matriz para depois valiarmos qual o mínimo.

for k in range(len(Y)):

    if A[k][j - 1] == 0: #nao podemos mandar o python dividir por 0
                         #entao este condicional checa isto antes
                         #da divisao.

        h.append(np.inf)

    else:

        h.append(int(Y[k]/A[k][j - 1]))

bound = min(h) #este é o limite superior do conjunto D.

D = list(range(bound + 1)) #O conjunto D são todos os inteiros
                           #não-negativos menores que este 
                           #limite superior.

return D

Depois disso iremos replicar a função f que devolve a imagem da solução ótima, uma maneira de resgatar quais são os valores desta solução ótima será demonstrada posteriormente.

def f(j, Y):

if j < len(c):

    F = [] #esta lista vai guardar as imagens de F para cada uma 
           #das decisões factíveis.

    for x in D(j + 1, Y):

        new_Y = [int(Y[k] - A[k][j]*x) for k in range(len(Y))]
                #esta list-comprehension transforma os valores do
                #vetor de restrições antes de passá-los para o
                #próximo passo da recursão.

        F.append((c[j]*x)[0] + f(j + 1, new_Y))

    return max(F) #retorna qual valor máximo atingido.

else:

    return 0

Se, após importada a biblioteca numpy, as funções àcima forem copiadas e os parâmetros do exemplo proposto forem estabelecidos, observa-se que a função f retorna o valor 36, porém este inteiro é apenas o produto interno entre o vetor \( \textbf{c} \) e a solução ótima \( \textbf{x} \). Para recuperarmos quais são as entradas deste vetor \( \textbf{x} \) precisaremos fazer algumas alterações na função f.

A principal alteração será a criação de um dicionário \( cached \_ results \) que irá estocar quais são as entradas do vetor \( \textbf{x} \) que correspondem à cada resultado possível.

def ILS_solution(j, Y, decisions = None, cached_results = None):

if decisions is None:

    decisions = [] #esta lista vai guardar o vetor x para cada passo da recursão

if cached_results is None:

    cached_results = dict() #este dicionário irá guardar o que foi mencionado acima

if j == len(c):

    cached_results[np.dot(np.array(decisions), c)[0]] = tuple(decisions)

    decisions.pop()

    return 0, 0

else:

    F = []

    for x in D(j + 1, Y):

        decisions.append(x)

        new_Y = [int(Y[k] - A[k][j]*x) for k in range(len(Y))]

        f = (c[j]*x)[0] + ILS_solution(j + 1, new_Y, decisions = decisions, cached_results = cached_results)[0]

        F.append(f)

    try:

        decisions.pop(0)

    except:

        None

    return max(F), cached_results[max(cached_results.keys())]

    decisions.pop(0)

if __name__ == '__main__':

    print(ILS_solution(0, b))

Com os parâmetros estabelecidos no primeiro bloco de código o retorno da função acima é o seguinte:

(36, (2, 6))

36 é o produto interno entre \( \textbf{c} \) e a solução ótima \( \textbf{x} = (2, 6) \).

0 votos
respondida Nov 4 por VITOR B BORGES (1 ponto)  
editado Nov 4 por VITOR B BORGES

Para testarmos a generalidade da aplicação de Programação Dinâmica acima iremos solucionar também o problema proposto na Seção 2.15 do mesmo livro. A Seção 2.15 propõe um problema de otimização de mochila com valores inteiros.

Seja a capacidade da mochila igual à 22, considere a existência de \( n = 3 \) classes de objetos, \( (A, B, C) \) com valores \( (v_{0}, v_{1}, v_{2}) = (15, 25, 24) \) e pesos \( (w_{0}, w_{1}, w_{2}) = (10, 18, 15)\). Este problema pode ser modelado usando \(ILS\) com parâmetros \( c = (15, 25, 24) \), \( b = (22, 1, 1, 1) \) e

\[ A = \begin{pmatrix} 10 & 18 & 15\\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}. \]

c = np.array([
[15],
[25],
[24]])

b = np.array([
    [22],
    [1],
    [1],
    [1]])

A = np.array([
    [10, 18, 15],
    [1, 0, 1],
    [0, 1, 0],
    [0, 0, 1]])

Quando passamos estes parâmetros para a implementação utilizada na resposta acima recebemos a seguinte resposta da função \( ILS\_solution()\):

(25, (0, 1, 0))

Que condiz extamente com o resultado encontrado no livro, levamos exatamente uma unidade do objeto \(B\) que possui o maior valor \(= 25\).

comentou Nov 6 por pedro zarur (6 pontos)  
Parabéns pela resolução, Vítor! Esse é um ótimo exemplo de problema a ser resolvido com programação dinâmica.
...