4638.sagews

%latex
\section*{Modelagem do problema de leilão combinatorial}

O problema do lei\~{a}o combinatorial \'{e} enunciado como:
\begin{quote}
    Um conjunto de trechos \'{e} colocado em leil\~{a}o e recebe-se propostas, com custo conhecido, caracterizadas pela promessa de servir um subconjuntos destes trechos. O objetivo \'{e} aceitar um determinado subconjunto de propostas de modo a minimizar o custo e garantir que todos os trechos sejam servidos. N\~{a}o \'{e} levado em considera\c{c}\~{a}o quantidades a serem transportadas e permite-se que a escolha contenha trechos ``repetidos''.
\end{quote}

Para modelar o problema do leil\~{a}o combinatorial, seja $T$ o conjunto de trechos e $P$ o conjunto de propostas. Para cada proposta $i \in P$ encontra-se relacionado um custo, denotado por $c_i$ e n\~{a}o negativo, conhecido e um subconjunto de $T$ correspondente aos trechos que a proposta $i$ promete servir. Para representar o subconjunto de $T$ que a proposta $i$ promete servir utilizamos o par\^{a}metro $\text{trechos\_p}_{ij}$, $i \in P$ e $j \in T$, que \'{e} definido como
\begin{equation*}
    \text{trechos\_p}_{ij} = \begin{cases}
        1, & \text{se a proposta $i$ promete servir o trecho $j$,} \\
        0, & \text{caso contr\'{a}rio.}
    \end{cases}
\end{equation*}

Neste problema precisamos determinar quais propostas que ser\~{a}o aceitas. Por esse motivo, utilizamos como vari\'{a}vel de decis\~{a}o $x_i$, $i \in P$, definida como
\begin{equation*}
    x_i = \begin{cases}
        1, & \text{se a proposta $i$ \'{e} aceita,} \\
        0, & \text{caso contr\'{a}rio.}
    \end{cases}
\end{equation*}

Como \'{u}nica restri\c{c}\~{a}o para o problemas devemos garantir que todos os trechos deve ser servidos. Pela forma como definimos o par\^{a}metro $\text{trechos\_p}_{ij}$ e a variável de decisão $x_i$ podemos representar a restrição anterior como
\begin{equation*}
    \sum_{i \in P} \text{trechos\_p}_{ij} \cdot x_i \geq 1, \quad \forall \ j \in T.
\end{equation*}

J\'{a} a fun\c{c}\~{a}o objetivo \'{e} minimizar o custo total que corresponde a soma dos custos das propostas aceitas. Pela forma como definimos o par\^{a}metro $c_i$ e a variável de decisão $x_i$ podemos representar a fun\c{c}\~{a} objetivo por
\begin{equation*}
    \sum_{i \in P} c_i \cdot x_i.
\end{equation*}

A modelagem do problema pode então ser resumida como
\begin{align*}
    \text{min } & \sum_{i \in P} c_i \cdot x_i \\
    \text{s.a } & \sum_{i \in P} \text{trechos\_p}_{ij} \cdot x_{i} \geq 1, \quad \forall \ j \in T \\
    & x_i \in \{0, 1\}, \quad \forall i \in P.
\end{align*}

A modelagem acima corresponde a um problema inteiro binário (em ingl\^{e}s \textit{0-1 or binary integer program}) e enquadra-se, dentre os modelos clássicos, no problema de cobertura (em ingl\^{e}s \textit{set covering problem}).

%latex
\section*{Modelagem alternativa}
Considere a instância constituida pelos dados abaixo para o problema do leil\~{a}o combinatorial na forma como foi modelado na seção anterior:
\begin{align*}
    & T = \{1, 2, 3, 4\}, \\
    & P = \{1, 2\}, \\
    & c_1 = 1, \quad c_2 = 1, \\
    & \text{trechos\_p}_{1,1} = 1, \quad \text{trechos\_p}_{1,2} = 1, \quad \text{trechos\_p}_{1,3} = 0, \quad \text{trechos\_p}_{1,4} = 0, \\
    & \text{trechos\_p}_{1,1} = 1, \quad \text{trechos\_p}_{1,2} = 0, \quad \text{trechos\_p}_{1,3} = 1, \quad \text{trechos\_p}_{1,4} = 0.
\end{align*}
Verificamos que a instância apresentada n\~{a}o ter solu\c{c}\~{a}o pois nenhuma das propostas prometem servir o trecho $4$ e como restri\c{c}\~{a}o do problema todos os trechos devem ser servidas por pelo menos uma proposta.
  
Para que o problema sempre possua solu\c{c}\~{a}o podemos acrescentar uma proposta artifical em $P$ que ir\'{a} servir todos os trechos, i.e., uma ``solu\c{c}\~{a}o trivial''. Precisamos escolher o custo desta proposta artifical de forma adequada para que o custo de qualquer subconjunto de propostas que não inclua a proposta artificial seja inferior ao custo da proposta artificial. Uma possível escolha para o custo da proposta artificial \'{e} a soma dos custos de todas as demais propostas.

Para adequar a modelagem apresentada na se\c{c}\~{a}o anterior com a introdução da proposta artificial, acrescentamos uma variável de decisão $y$ relacionada com a proposta artificial e definida como
\begin{equation*}
    y = \begin{cases}
        1, & \text{se a proposta artificial \'{e} aceita,} \\
        0, & \text{caso contr\'{a}rio.}
    \end{cases}
\end{equation*}
Logo, a modelagem do problema assume a forma abaixo:
\begin{align*}
    \text{min } & \sum_{i \in P} c_i \cdot x_i + \left( \sum_{i \in P} c_i \right) y \\
    \text{s.a } & \left( \sum_{i \in P} \text{trechos\_p}_{ij} \cdot x_i \right) + y \geq 1, \quad \forall \ j \in T \\
    & x_i \in \{0, 1\}, \quad \forall \ i \in P \\
    & y \in \{0, 1\}.
\end{align*}

Para determinarmos se a solu\c{c}\~{a}o encontrada é aplic\'{a}vel ou não podemos verificar o valor da vari\'{a}vel $y$ na solu\c{c}\~{a}o encontrada, se $y = 0$ a solu\c{c}\~{a}o é aplic\'{a}vel e se $y = 1$ a solução não é aplic\'{a}vel, ou o valor da função objetivo, se o valor da função objetivo for menor que $\left( \sum_{i \in P} c_i \right)$ a solu\c{c}\~{a}o \'{e} aplic\'{a}vel e se o valor da função objetivo for maior ou igual a $\left( \sum_{i \in P} c_i \right)$ a solu\c{c}\~{a}o não é aplic\'{a}vel.

"""
Dados
"""

# find_error == True indica a ocorr\^{e}ncia de um erro nos dados da inst\^{a}ncia.
find_error = False

# n_trechos \'{e} o n\'{u}mero de trechos presentes na inst\^{a}ncia.
n_trechos = 28

# n_prop \'{e} o n\'{u}mero de propostas presentes na inst\^{a}ncia.
n_prop = 76

# T \'{e} um conjunto de trechos. Os trechos s\~{a}o identificadas por n\'{u}meros de 1 até n_trechos.
T = range(1, n_trechos + 1)

# P \'{e} um conjunto de propostas. As propostas s\~{a}o identificadas por n\'{u}meros de 1 até n_prop.
P = range(1, n_prop + 1)

# c[i] \'{e} o custo da proposta i, i.e., $\text{i} \in \text{P}$.
c = [0, 21, 41, 31, 30, 24, 35, 48, 19, 31, 50,
40, 23, 25, 19, 35, 34, 25, 75, 26, 55,
64, 54, 65, 54, 120, 150, 150, 53, 59, 55,
39, 41, 38, 55, 66, 70, 53, 55, 61, 97,
70, 100, 90, 69, 65, 55, 61, 65, 65, 75,
55, 97, 71, 41, 65, 69, 57, 59, 65, 77,
69, 77, 55, 67, 55, 73, 55, 85, 69, 18,
78, 52, 71, 68, 74, 70]

# testa consist\^{e}ncia de c com P.
if len(P) + 1 != len(c) :
    print "Verificar objeto c."
    print "len(P) = " + str(len(P))
    print "len(c) = " + str(len(c))
    find_error = True

# trechos_p[i] \'{e} o conjunto dos trechos servidos pela proposta i ($\text{i} i\n \text{P}$).
trechos_p =[set(),
set([3, 7, 8, 11, 12]),
set([1, 2, 3, 4, 7, 8, 11, 12]),
set([7, 8, 11, 20, 21]),
set([2, 3, 5, 9, 10]),
set([7,8, 11, 15]),
set([2, 3, 8, 14, 16]),
set([1, 2, 3, 4, 7, 8, 11, 12]),
set([1, 2, 3]),
set([7, 11, 12, 20, 21]),
set([10, 21, 26, 27, 28]),
set([2, 3, 5, 9, 10]),
set([4, 7, 8, 11, 12]),
set([7, 23, 25, 27, 28]),
set([1, 2, 3]),
set([1, 3, 5, 7, 8, 9, 10, 16]),
set([7, 23, 25, 27, 28]),
set([7, 8, 11, 12, 23]),
set([5, 6, 7, 13, 14, 16, 23, 25, 27, 28]),
set([2, 3, 10, 14, 16]),
set([4, 7, 8, 11, 12, 15, 17, 18, 19, 22]),
set([2, 3, 5, 7, 8, 9, 10, 11, 20, 21]),
set([1, 6, 10, 11, 18, 20, 27, 28]),
set([2, 5, 6, 8, 9, 10, 12, 16, 18]),
set([1, 2, 3, 7, 20, 25, 26, 28]),
set([1, 2, 3, 5, 6, 9, 10, 13, 14, 16]),
set([4, 7, 12, 15, 17, 18, 19, 22]),
set([8, 11, 20, 21, 23, 24, 25, 26, 27, 28]),
set([6, 7, 8, 9, 10, 11, 23, 25, 27, 28]),
set([2, 3, 4, 7, 10, 14, 16, 17, 19, 22]),
set([1, 2, 3, 4, 7, 11, 15, 17, 18, 19]),
set([1, 2, 3, 4, 7, 8, 11, 12]),
set([2, 3, 7, 8, 11, 23, 25, 27, 28]),
set([7, 20, 25, 27, 28]),
set([1, 2, 3, 4, 6, 7, 8, 9, 10, 11]),
set([4, 7, 12, 18, 20, 21, 22, 23, 24, 27]),
set([5, 7, 8, 11, 15, 17, 19, 20, 21, 23]),
set([1, 2, 3, 7, 20, 25, 26, 28]),
set([4, 7, 8, 11, 12, 15, 17, 18, 19, 20]),
set([1, 6, 20, 21, 23, 24, 27, 28]),
set([2, 3, 5, 9, 10, 13, 14, 16, 24, 26]),
set([1, 4, 8, 11, 12, 15, 17, 18, 19, 22]),
set([2, 3, 5, 6, 9, 10, 13, 14, 16]),
set([20, 21, 23, 24, 25, 26, 27, 28]),
set([7, 11, 12, 21, 24, 25, 26, 27, 28]),
set([7, 11, 15, 17, 18, 19, 23, 25, 27, 28]),
set([2, 3, 7, 8, 10, 11, 12, 14, 16, 23]),
set([1, 2, 3, 7, 10, 11, 12, 14, 16, 17]),
set([2, 3, 5, 6, 9, 10, 12, 13, 14, 16]),
set([7, 8, 11, 18, 20, 23, 25, 26, 27, 28]),
set([1, 4, 15, 17, 19, 21, 22, 24]),
set([4, 7, 8, 11, 12, 1, 17, 18, 19, 22]),
set([2, 3, 5, 9, 10, 13, 14, 16, 24, 26]),
set([1, 4, 20, 21, 23, 25, 27, 28]),
set([5, 8, 11, 20, 21]),
set([4, 7, 12, 18, 20, 22, 25, 26, 28]),
set([6, 7, 9, 13, 14, 15, 16, 17, 19, 23]),
set([1, 4, 7, 8, 11, 12, 23, 25, 26, 28]),
set([2, 3, 5, 6, 9, 10, 13, 14, 16]),
set([15, 17, 18, 19, 20, 21, 24, 27]),
set([1, 2, 3, 5, 6, 15, 18, 20, 23]),
set([4, 9, 10, 12, 13, 14, 16, 17, 19, 22]),
set([7, 11, 12, 21, 24, 25, 26, 27, 28]),
set([3, 4, 6, 7, 8, 10, 11, 12, 14, 16]),
set([3, 6, 7, 10, 14, 16, 23, 25, 27, 28]),
set([2, 3, 5, 7, 8, 9, 10, 11, 12, 23]),
set([1, 6, 20, 21, 23, 25, 27, 28]),
set([4, 7, 8, 11, 12, 15, 17, 18, 19, 22]),
set([2, 3, 5, 9, 10, 13, 14, 16, 24, 26]),
set([4, 7, 11, 15, 17, 19, 20, 21, 22, 24]),
set([1, 2, 3]),
set([5, 6, 7, 13, 14, 16, 20, 21, 24, 27]),
set([1, 2, 3, 4, 8, 9, 10, 11, 12]),
set([15, 17, 18, 19, 22, 23, 25, 26, 28]),
set([1, 2, 3, 5, 6, 8, 11, 21, 27]),
set([9, 10, 13, 14, 15, 16, 18, 20, 23]),
set([4, 7, 12, 17, 19, 22, 24, 25, 26, 28])]

# testa consist\^{e}ncia de trechos_p com P.
if len(P) + 1 != len(trechos_p) :
    print "Verificar trechos_p."
    print "len(P) = " + str(len(P))
    print "len(trechos_p) = " + str(len(trechos_p))
    find_error = True

# testa consist\^{e}ncia de trechos_p em rela\c{c}\~{a}o aos trechos existentes.
for i in trechos_p :
    for j in i :
        if find_error == True :
            break
        elif j < 1 or j > n_trechos :
            print "Verificar trechos da proposta " + str(i)
            find_error = True
    if find_error == True :
        break

from sage.numerical.mip import Sum

plc = MixedIntegerLinearProgram(solver="GLPK", maximization=False)

# Adi\c{c}\~{a}o da vari\'{a}vel x[i].
# x[i] == 1 se a proposta i \'{e} aceita,
# x[i] == 0 caso contr\'{a}rio.
x = plc.new_variable(binary=True)

# Adi\c{c}\~{a}o da vari\'{a}vel y.
# y == 1 se a proposta artificial \'{e} aceita,
# y == 0 caso contr\'{a}rio.
y = plc.new_variable(binary=True)[0]

# Adi\c{c}~\{a}o da restri\c{c}\~{a}o serv[j].
# serv[j] corresponde a restri\c{c}\~{a}o que garante que o trecho j vai ser servido.
for j in T :
    plc.add_constraint(Sum(x[i] for i in P if j in trechos_p[i]) + y >= 1, name="serv[" + str(j) + "]")

# Fun\c{c}\~{a}o objetivo
# Minimizar o custo
plc.set_objective(Sum(c[i] * x[i] for i in P) + sum(c) * y)

# plc.show()
f_otimo = plc.solve(log=4)

GLPK Integer Optimizer, v4.44 28 rows, 77 columns, 651 non-zeros 77 integer variables, all of which are binary Preprocessing... 28 hidden covering inequaliti(es) were detected 28 rows, 77 columns, 651 non-zeros 77 integer variables, all of which are binary Scaling... A: min|aij| = 1.000e+00 max|aij| = 1.000e+00 ratio = 1.000e+00 Problem data seem to be well scaled Constructing initial basis... Size of triangular part = 28 Solving LP relaxation... GLPK Simplex Optimizer, v4.44 28 rows, 77 columns, 651 non-zeros 0: obj = 0.000000000e+00 infeas = 2.800e+01 (0) * 1: obj = 4.493000000e+03 infeas = 0.000e+00 (0) * 40: obj = 1.965773196e+02 infeas = 1.984e-18 (0) OPTIMAL SOLUTION FOUND Integer optimization begins... + 40: mip = not found yet >= -inf (1; 0) + 69: >>>>> 2.010000000e+02 >= 1.990000000e+02 1.0% (5; 0) + 71: mip = 2.010000000e+02 >= tree is empty 0.0% (0; 9) INTEGER OPTIMAL SOLUTION FOUND

"""
Verifica\c{c}\~{a}o da solu\c{c}\~{a}o \'{o}tima encontrada.
"""

# Proposta artifical foi utilizada?
# Forma 1
c_y = sum(c)
if f_otimo >= c_y :
    print "Proposta artificial utilizada."
    print "f_otimo = " + str(f_otimo) + " >= " + str(c_y) + " = c_y"
else :
    print "Proposta artificial N\\~{A}O utilizada."
    print "f_otimo = " + str(f_otimo) + " <= " + str(c_y) + " = c_y"
# Forma 2
if plc.get_values(y) == 1 :
    print "Proposta artificial utilizada."
else :
    print "Proposta artificial N\\~{A}O utilizada."

# Todos os trechos foram servidos?
todos_trechos_servidos = True
trechos_servidos = set()
for i in P :
    if x[i] == 1 :
        trechos_servidos = trechos_servidos | trechos_p[i]
for j in T :
    if todos_trechos_servidos == False :
        break
    elif j not in trechos_servidos :
        todos_trechos_servidos = False
print todos_trechos_servidos

Proposta artificial N\~{A}O utilizada. f_otimo = 201.0 <= 4493 = c_y Proposta artificial N\~{A}O utilizada. True

# Solution
print "proposta aceitas (n\'{u}mero)",
for j in range(1, n_trechos + 1):
    print "%3d" % j,
print ""
for i in P:
    if plc.get_values(x[i]) == 1:
        print "%28d" % i,
        for j in range(1, n_trechos + 1):
            if j in trechos_p[i]:
                print "S" * 3,
            else:
                print " " * 3,
        print ""

proposta aceitas (n'{u}mero) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 71 SSS SSS SSS SSS SSS SSS SSS SSS SSS SSS 72 SSS SSS SSS SSS SSS SSS SSS SSS SSS 73 SSS SSS SSS SSS SSS SSS SSS SSS SSS