<jupyter_start><jupyter_text>Programación lineal mixtaSe 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.<jupyter_code>P = MixedIntegerLinearProgram() # we create an instance to solve our new problem
x = P.new_variable(real = True, nonnegative = True) # we create new variables
P.set_objective(x[1] + x[2] + 3*x[3]) # this is the function we want to maximize
P.add_constraint(x[1]+ 2*x[2] <= 4) # the constraints
P.add_constraint(5*x[3] - x[2] <= 8)
P
P.solve() # let's optimize it
P.get_values(x[1])
P.get_values(x[2])
P.get_values(x[3])<jupyter_output><empty_output><jupyter_text>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](http://www.gnu.org/software/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](http://doc.sagemath.org/html/en/thematic_tutorials/linear_programming.html) on the Sage website.  Combinatorial y programación linealDurante 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.<jupyter_code>G = graphs.PetersenGraph() # para varios de nuestros ejemplso vamos a utilizr el grafo Petersen G<jupyter_output><empty_output><jupyter_text>Encontremos el conjunto mas grande de vertices compatibles. (Recordemos que dos vértices son compatibles si no comparten ninguna arista).<jupyter_code>P = MixedIntegerLinearProgram()
x = P.new_variable(binary = True)<jupyter_output><empty_output><jupyter_text>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$.<jupyter_code>P.set_objective(sum(x[i] for i in G)) # the objective is the sum of all variable, aka the size of the set
for e in G.edges(): # we go through all edges
    i,j = e[0], e[1] 
    P.add_constraint(x[i] + x[j] <= 1)<jupyter_output><empty_output><jupyter_text>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.<jupyter_code>P.solve()<jupyter_output><empty_output><jupyter_text>El conjunto máximo tiene 4 vértices, que son:<jupyter_code>E = {i for i in G if P.get_values(x[i]) == 1}
E<jupyter_output><empty_output><jupyter_text>**Todos los siguientes ejercicios son de la página [pagina personal de Nathann Cohen](https://www.steinertriples.fr/ncohen/tut/LP_examples/) encontrará soluciones y mas ejercicios (en ingles).**  Exercisio : corte maximoResuelva 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.<jupyter_code>G = graphs.PetersenGraph()
G<jupyter_output><empty_output><jupyter_text>** debe encontrar un máximo de 8 aristas**  Exercisio : Conjunto dominanteEncuentre 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.<jupyter_code>G = graphs.PetersenGraph()
G
P = MixedIntegerLinearProgram(maximization = False) # this is how we do minimal except of maximal<jupyter_output><empty_output><jupyter_text>**debe encontrar un conjunto de tamaño 3. Por ejemplo $\lbrace 0,2,6 \rbrace$.**  Exercisio : Cobertura de vértices mínimoEncuentre el conjunto *minimo* de vertices tal que cada arista contiene al menos uno de los vertices del conjunto.<jupyter_code>G = graphs.PetersenGraph()
G<jupyter_output><empty_output><jupyter_text>**Debe encontrar un conjunto de tamaño 6**.  Exercisio : Conjunto bipartitoEncuentre un conjunto $A$ tal que cada arista tiene exactamente un vértice en $A$.<jupyter_code>G = graphs.CompleteBipartiteGraph(3,3)
G<jupyter_output><empty_output><jupyter_text>Exercisio : distanciaCalcule la distancia de un vértice 8 a cualquier otro.<jupyter_code>G = graphs.PetersenGraph()
G<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08653648509763617, 'fraction_numerical': 0.011510791366906475, 'mean_word_length': 5.748959778085991, 'pattern_counts': {'":': 0, '<': 48, '<?xml version=': 0, '>': 45, 'https://': 1, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '11', 'dir': 'jupyter-structured-clean-dedup', 'id': '435175', 'license': 'MIT', 'n_tokens_mistral': 1716, 'n_tokens_neox': 1669, 'n_words': 568, 'path': 'minicourses/pons/LinearProgrammingEsp.ipynb', 'repo_name': 'rafaeldleon/ecco18.github.io', 'size': '4865'}