Programación lineal mixta

Se ha mencionado en la clase que hay un algoritmo muy eficiente para resolver problemas de optimización donde las restricciones son lineales. Resulta que muchos problemas combinatorios pueden ser traducidos a estos problemas de optimización.

Puede utilizar Sage para resolver problemas de optimización lineales con coeficientes enteros. La clase principal que necesita utilizar se llama MixedIntegerLinearProgram. Aqui hay un pequeño ejemplo para ver como utilizarla.



In [10]:

    
P = MixedIntegerLinearProgram() # we create an instance to solve our new problem



In [11]:

    
x = P.new_variable(real = True, nonnegative = True) # we create new variables



In [12]:

    
P.set_objective(x[1] + x[2] + 3*x[3]) # this is the function we want to maximize



In [13]:

    
P.add_constraint(x[1]+ 2*x[2] <= 4) # the constraints
P.add_constraint(5*x[3] - x[2] <= 8)



In [14]:

    
P



In [15]:

    
P.solve() # let's optimize it



In [16]:

    
P.get_values(x[1])



In [17]:

    
P.get_values(x[2])



In [18]:

    
P.get_values(x[3])

En este ejemplo, hemos calculado el valor máximo de la función

$$x_1 + x_2 + 3x_3$$

bajo las restricciones

$$x_1 + 2x_2 \leq 4,$$$$5x_3 - x_2 \leq 8.$$

Hemos encontrado que el valor máximo es $4$ con $x_1 = 4$, $x_2 = 0$ y $x_3 = 1.6$.

By default, Sage is using the GLPK solver from GNU. This is an open source solver. It also has other solver installed and you can choose which one to use depending on your use. Besides, you can also install some non-open-source solver which are supported by Sage. To know more, read the Linear Programming tutorial on the Sage website.

Combinatorial y programación lineal

Durante la sesión de ejercicios, hemos resuelto algunos problemas de teoria de grafos utilizando optimización. Las soluciones que hemos encontrado no son lineales. Sin embargo, al trasladar algunas de las restricciones al nivel de variables en Sage, podemos expresar estos problemas de una manera lineal. Considere el siguiente ejemplo.



In [19]:

    
G = graphs.PetersenGraph() # para varios de nuestros ejemplso vamos a utilizr el grafo Petersen G

Encontremos el conjunto mas grande de vertices compatibles. (Recordemos que dos vértices son compatibles si no comparten ninguna arista).



In [20]:

    
P = MixedIntegerLinearProgram()
x = P.new_variable(binary = True)

Al añadir la palabra clave binary = True, le pedimos a Sage que cada variable sea 1 ó 0. Esto evita añadir la restricción cuadrática $x_i(1 - x_i) = 0$.



In [21]:

    
P.set_objective(sum(x[i] for i in G)) # the objective is the sum of all variable, aka the size of the set



In [22]:

    
for e in G.edges(): # we go through all edges
    i,j = e[0], e[1] 
    P.add_constraint(x[i] + x[j] <= 1)

Note que hemos cambiado la restricción que vimos en la sesión de ejercicios. ¡ La restricción original $x_i x_j = 0$ es cuadrática ! Nuestra nueva restricción tambien funciona y es lineal.



In [23]:

    
P.solve()

El conjunto máximo tiene 4 vértices, que son:



In [24]:

    
E = {i for i in G if P.get_values(x[i]) == 1}
E

Todos los siguientes ejercicios son de la página pagina personal de Nathann Cohen encontrará soluciones y mas ejercicios (en ingles).

Exercisio : corte maximo

Resuelva el ejercicio 2 del Taller 1: encuentre el conjunto $A \subset G$ tal que el número de aristas saliendo de $A$ a $G \setminus A$ es máximo.



In [27]:

    
G = graphs.PetersenGraph()
G



In [25]:



In [29]:

debe encontrar un máximo de 8 aristas

Exercisio : Conjunto dominante

Encuentre el conjunto mínimo de vertices tal que cada vertice $i$ es en el conjunto o es un vecino de un elemento en el conjunto.



In [30]:

    
G = graphs.PetersenGraph()
G



In [34]:

    
P = MixedIntegerLinearProgram(maximization = False) # this is how we do minimal except of maximal



In [35]:

debe encontrar un conjunto de tamaño 3. Por ejemplo $\lbrace 0,2,6 \rbrace$.

Exercisio : Cobertura de vértices mínimo

Encuentre el conjunto minimo de vertices tal que cada arista contiene al menos uno de los vertices del conjunto.



In [36]:

    
G = graphs.PetersenGraph()
G



In [38]:



In [40]:

Debe encontrar un conjunto de tamaño 6.

Exercisio : Conjunto bipartito

Encuentre un conjunto $A$ tal que cada arista tiene exactamente un vértice en $A$.



In [46]:

    
G = graphs.CompleteBipartiteGraph(3,3)
G



In [47]:



In [49]:

Exercisio : distancia

Calcule la distancia de un vértice 8 a cualquier otro.



In [50]:

    
G = graphs.PetersenGraph()
G



In [53]:



In [ ]: