It has been mentioned in class that we have very efficient algorithms to solve optimization problems where the constraints are linear. It turns out that many combinatoial problems can be translated in such optimization problems.
You can use Sage to solve linear optimization problem with integer coefficient. The main class you need is called MixedIntegerLinearProgram. Here is a small example for you to see how to use it.
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])
In this example, we have computed the maximal value of the function
$$x_1 + x_2 + 3x_3$$under the constraints that
$$x_1 + 2x_2 \leq 4,$$$$5x_3 - x_2 \leq 8.$$We have found that the max value is $4$ with $x_1 = 4$, $x_2 = 0$ and $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.
During the exercise sessions, we have solved some graph theory problems using optimization. The solutions we found were not linear ! Nevertheless, by moving some of the constraint to the variable level in Sage, we can actually express those problems in a linear way. Obsever the following example.
In [19]:
G = graphs.PetersenGraph() # for many of our examples, we will use the Peterson Graph
G
Let us find the biggest set of compatible vertices. (Reminder: two vertices are compatibe if they don't share an edge).
In [20]:
P = MixedIntegerLinearProgram()
x = P.new_variable(binary = True)
By adding the keyword binary = True, we request that each variable is either 1 or 0. This avoids adding the constraint $x_i(1 - x_i) = 0$ which is quadratic.
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 that we have changed the contraint from what we found during the exercise session. Indeed, the original constraint $x_i x_j = 0$ is quadratic ! Our new constraint also wors and is linear.
In [23]:
P.solve()
The maximal set has 4 vertices, which are:
In [24]:
E = {i for i in G if P.get_values(x[i]) == 1}
E
All of the following exercises come from Nathann's Cohen webpage where you will find solutions and even more exercises.
In [27]:
G = graphs.PetersenGraph()
G
In [25]:
In [29]:
you should find a maximum of 8 edges
In [30]:
G = graphs.PetersenGraph()
G
In [34]:
P = MixedIntegerLinearProgram(maximization = False) # this is how we do minimal except of maximal
In [35]:
you should find a set of size 3. For example $\lbrace 0,2,6 \rbrace$.
In [36]:
G = graphs.PetersenGraph()
G
In [38]:
In [40]:
You should find a set of size 6.
In [46]:
G = graphs.CompleteBipartiteGraph(3,3)
G
In [47]:
In [49]:
In [50]:
G = graphs.PetersenGraph()
G
In [53]:
In [ ]: