0:00

Okay, so welcome back. This is Discrete Optimization: Mixed

Integer programming part 4, and this is going to be quite exciting.

So, what we going to see today some really beautiful mathematics with very

interesting computational results. Okay.

So we going to talk about polyhedral cuts.

Okay. Very different from the cuts that you

have seen before; talk about warehouse location and node covering.

Okay. So this is, this is the motivation; so we

are going to talk about the convex hull. Right?

So this is the linear relaxation that we saw last time of one of, one of very

simple mixed integer program. Okay?

Now, in practice what we are really interested in, are these interger points

that you see. Okay?

And one of the things that we going to look at is the convex hull of these

particular points, that you see on the screen at this point, okay?

So this is 2D, okay? This is a larger 2D example.

Once again, this is the linear relaxation of a MIP.

These are all the integer solutions that you see there.

That's the real thing we are interested in, right?

And this is the convex sort of disguise/g, the convex envelope.

That means you know, you take all these points, and this is essentially the

convex, the smallest convex set, which include all these points.

Okay? So this is 3D, so this is a 3D linear

relaxation. You see all the integer points inside,

okay? Once again, you could take the convex

cell, that's you know, this polyhedral that you see there.

And that 's the convex set of all the integer points.

Okay? Now, why am I talking about this?

Okay? Assume that you have this beautiful

convex hull. You have this rigid, this polyhedra

there. Okay?

What could you do? Okay?

Think about it, what could you do? Well, one of the things you can do is

say, [SOUND] I'm going to use an LP here, optimize my objective function.

And by now you know that if you optimize this finger, you [UNKNOWN] it a vertex

right? What is that vertex?

It's going to be an integer solution, and that's going to be the optimal solution

to your MIP. So if I had this convex solved, okay, I

could use linear programming and I would get the optimal solution immediately.

Isn't that beautiful, right? So, in a sense, this is what we are

going to talk about. We're going to talk about these

polyhedral cuts, which are essentially these facets of the convex hull, okay?

If get all of them, we would just use linear programming and we would be very

happy, okay? Now, these cuts, okay.

They're valid, okay. They don't remove any solution.

I took the convex envelope of all the interger points.

I'm not removing any of them. They are all included, right?

And then they are also as strong as possible, right?

And so, if I have all of them, I could just use linear programming and I would

find the optimal solution you know, using the linear program.

Okay? So, so, why are these you know,

polyhedral cuts very interesting? Because they are exploiting the problem

structure. In that sense, they are completely

octagonal to the syntactic cut that we saw in the last lecture, which were based

on the tableau. Okay?

So, basically what we're going to do here is look at specific constraints or

specific properties of the problem, and then generate these polyhedral cuts.

Okay? Now they share of course the same spirit

as the syntactic cuts. Right?

So they are valid, they don't remove any solutions.

Okay? They're always valid, they're just

strengthening the, the formulation of the MIP.

They are also cutting; we want to generate those that are cutting the

optimal solution of the linear relaxation.

Right? So such that you know, we actually you

know, get closer and closer to the, the integer solution.

Okay? And of course we don't need to generate

all of them, we can generate enough such that we can solve the problem

effectively. Okay?

Now a particle in a, in a particle context, an application may use many of

them. It's like you know, global constraints in

constraint programming. You may look at very different classes of

code and generate these cuts. Okay?

They will exploit different sub-structure of the application.

Okay, so why is a facet of this convex hull [UNKNOWN]?

That is a critical thing that we're left to actually define.

And so, what your going to see is that the mathematics behind it is easy.

Of course, you know, what the, the whole creativity is going to be finding this

facet and then proving this simple proof. Okay?

So, this simple technique. So, to find a facet, what you need to do

is essentially find f you know, n, a finally independent solution, so point

which satisfy the facet at the equality. They have to be on that facet, these

points. Okay?

And so a final independence is, is, is a simple thing to show.

What you need to do is that, if you have a set of n points, they're going to be a

finely independent, if when you extend with one more coordinate, then put a 1

for that coordinate for every one of them, then you can show that they are

linearly independent. And of course linearly independence you

know what this is. It's simp, simply saying that, if you

have a, a combinations of all these points using alpha 1 alpha n, okay, for

these end points. And if that is equal to 0, then all these

alphas have to be 0. So, in a sense, you know, showing that a

facet is that, that, that's, that's something, so many quality is a facet is

basically going to be trying to find these points and showing that they are

finely independent. Okay?

So, let's look at the particular example that we saw before.

Okay, so this is warehouse location. Remember, we had to open or close these

warehouses, okay? And once they are open, they can serve

customers. The goal was to minimize the cost of

opening this warehouse and then serving the customers.

Okay? So we had this beautiful MIP model.

We have a very strong relaxation here, which was basically using this very

simple constraint, right? Simple inequalities, two variables,

stating that you know, you can only serve a customer C with warehouse is W, if

warehouse W is open. You know, warehouse W is open means xw is

equal to 1. And then obviously, and then obviously,

and then obviously what you need to have is, you need to have you know, ywc, small

or equal to the value of xw. That's what you see over here.

Okay? So in a sense, what you can wonder is how

these inequalities facets of the convex hull?

Okay? So these simple inequalities are the

facets. And so, what you need to do is you need

to look at these constraints, okay, at equalities, instead of in, an ine,

inequalities, and find n points okay, such that you know, they are, find n

points which are finely independent. Okay?

So I'm going to cheat a little bit here, I'm going to assume that we have only one

warehouse. Okay?

And then you can generate these points here which satisfy these constraints and

inequality. Okay?

And so, what we are looking here is we're looking at warehouse w, and we are

looking at customer one. Right?

And we are looking at this very simple constraint, and what you see at the end

points is that we're going to assume that you know, xw is zero.

Okay? if xw is zero, then y1w, has to be 1w1,

yw1 has to be zero and that's the first point that you see there.

And all the other customers, we put them to zero as well.

Okay, so we satisfy that constraints of the equality.

Now, when this guy is 1, okay. So when xw is 1, okay.

So then, to satisfy the constraints of the equality, we have to serve the

customers by, with that particular warehouse.

And there's a second point that you see. And then the other point that you see

that will simply be saying, ooh, but I can take these other customers, and say

that he's using that warehouse as well. It doesn't impact that var, that

constraint, but we, we can find different points, knowing they're going to be

finely independent. Of course you can generalize that if you

have many warehouses by you know, finding the right values for these different

warehouses. Okay?

So, putting a one for every one of them in every one of these points.

Okay? Well, to, to get essentially n points.

Okay? So, in a sense, this is the kind of ways

you prove that something is a facet. You look for these points.

Okay? And you are trying to show that they

satisfy the constraints of the inequality and they are independent of each other,

of each other. Okay?

So, let me look at another example now, because this was kind of too easy.

Right? So, the formulation that we had, had

already some of the facets. So, we're going to look at another

problem where it's not so obvious. And this problem is called node packing.

Okay? And the key idea is once again, you have

a graph you know, with a variety of vertices and then you have edges between

these vertices. And what you want to do is to find the

largest number of nodes such that any two of them is not connected by an edge.

Okay? So we want to pack as many, that's why

its called node packing right? You want to pack as many vertices as you

can, but they can't be connected by an edge.

Okay? So this is a packing you know, this is a

beautiful packing with one vertex. Okay?

And of course as soon as I take you know, vertex 1, I can't take anything else

because they are all connected to it. Okay?

So this is not a packing which has two nodes.

Okay, okay? So, it has nodes four and nodes six.

Okay? So these two guys are not connected with

each other, and therefore this is a packing.

Okay? Now, a question that you may ask is that,

is there a better packing? Is there a packing where I can actually

pack three nodes? Okay?

So look at this graph and try to think, and you see this mapping with three

nodes? Okay?

So, we're going to come back to that. Okay?

But what we're going to first do is to look at node packing and see if we can

express it as a MIP. Okay?

And once again, it's always the same story.

Right? What are going to be the decision

variables, and what are going to be the constraints.

Okay? So in this particular case, the decision

variables are easy. We're going to decide, if a particular

node is actually inside the packing or not.

Okay? So a particular vertex is inside the

node, and then we leave constraints forl you know, linking two nodes.

And what we know is that if we take this node, any node which is adjacent to it,

which means that there is an edge between them, cannot be inside a packing.

So, we'll put this linear inequality to tell you know, to tell the MIP that you

know, this node and that node, because they are linked by an edge, cannot be

inside a packing at the same time. Okay?

And this is the formula that you see here.

Okay? So, you see that the you know, x1 to x6

are basically asso, are variable which are associated with every one of the

vertices. Okay?

They're basically telling you if that particular vertex is in the packing.

And then you see this very simple inequalities that are basically telling

you, ooh you know, node x1 and node x2 cannot be packed you know, at the same

time because they are linked by an edge. So, essentially for every one of the

edges you have these simple inequalities. And obviously every one of these

variables has to be zero and one, and the linear relaxation here is basically

going to relax this, ins by, by saying that they are between zero and one.

Okay? So, this is the linearly relaxation of

the problem. Okay?

So when you look at this, you can think ooh, but what is the linear relaxation

going to to do? And what I told you last time is that the

linear relaxation is going to be evil, it's never going to do what you want.

Right? It's always going to try to maximize in

this particular case, you maximize the largest path of the packing here.

Okay? So, it's going to try always to do to do

better. Okay?

And in this particular case. Okay?

The linear relaxation. Okay?

Is basically going to assign one half to everyone of the decision variables.

And then for value of the objective function is going to be six time one half

which is three. So, it's basically telling you that the

maximum you will ever be able to do is to pack three nodes on this simple example.

Okay? But of course this is terrible.

Right? So this, this is [UNKNOWN] fraction, in

the worst fractional way. Right?

So can we do better than that? Okay?

So now we have to think. You know, you look at these problem

[INAUDIBLE] and, and you're asking yourself, is there any kind of properties

of the solution that would strengthen my relaxation?

Okay? So, we want to find you know, a property

of the solution. So essentially of, constraints which is

going to satisfy by all of the integer solutions.

Okay? And this particular case, there is a very

useful concept that we find everywhere in optimization, which is cliques, the

concept of cliques. Okay?

So when you look at this thing here. Okay?

So, you see this you know, you see basically two cliques.

Okay? And so, when you see a clique like that

with four vertices, and all the vertices in a clique are connected to all the

other ones, how many vertices can you actually you know, select in a packet?

Well, at most one, because that par, if you select one, it's connected to

everything else. So you can basically now select any of

the other vertices. Okay.

So as soon as you find a clique, you know exactly that you can at most, that you

can select at most one of the vertices in that clique.

Okay? So what are we going to do, is take the

formulation and add all the clique constraints that were present in the

instances that we looked at. Okay?

So this is and so we can do actually better than that, we're going to look at

the maximal clique. And what is the maximal clique?

It's the largest clique that we can find. Okay?

So, it's a clique that essentially cannot be extended further.

Okay? So, when you see, when you see this click

here, you can say oh, but there is a clique with three vertices.

Okay? But that click can extended, so we won't

state that popular clique. We're going to take the clique with four

vertices instead, because it's larger and therefore it's more constraining.

Okay? So we're going to take this maximal

clique for every one of these, well, for every you know, collections of vertices.

Okay? So, as soon as you have a maximal clique.

Okay? Let's say for node one to five, you can

state the constraint which says that most one of these nodes can be selected inside

inside, in, in the solution. Okay?

So, in this particular case, we said that the sum of x1 to x5 has to smaller or

equal to one. Okay?

So now, note what we can show actually, we can show that actually a, a maximal

clique is a facet. Okay?

And if you want to actually know what the proof is doing, is the kind of, the kind

of reasoning for finding all these finely independent points that you will have to

do is to say ooh, but if I have clique like this, and if I ever note a vertex.

Okay? We know that since this clique is

going to be maximal, that it cannot be, there is at least one edge with one of

these vertices that, that is not there. Okay?

So, it's missing at least one edge with one of these vertices.

And that's how you will be able to find this finely independent point.

Okay? So, t?his is essentially the MIP node

with this, with this, with all this constraints.

Okay? So, we remove all the other ones, because

they were basically subsumed by the clique constraints.

Okay? They were smaller than the clique

constraints, so the fact that x1 and x2 could not be assigned the same value here

is subsumed by the fact that we know that there is a clique between x1, x2, and x3.

And therefore you know, it subsumed the other one.

So we basically have all the clique constraints here.

Okay? And that's the new, that's the new linear

relaxation steps we are going to use. Okay?

Now, once again, you know, this linear relaxation is really clever.

What is it going to do? Well, one of the things that it's

going to notice of course is that x1 is very, is, is all over the place.

So to, so to, so if we give a value to x1 essentially, it's goning take you know,

some value for every one of these constraints.

So, what it's going to do is basically ignore x1, put x1 to 0 and then once

again you will have a completely fractional value for all of the other

constraints. Okay?

So when you do this, you know, what is the, what is the linear relaxation giving

you? It's giving you five times 1 half.

Okay? Which is what?

Which is 2.5. So we know already that the best packing

we will ever be able to do is two. Okay?

So that's, that's essentially tell, it's, it's actually a strong relaxation in this

part here in the case. Okay?

but one of the things you have to remember here, okay, is that we don't

have the convexal of the node parking you know, the node parking port, you know,

solution points. Right?

Because this solution is [UNKNOWN] fractional.

So what that means is that, these clique constraints are not completely

characterizing the problem, you will need all the kinds of cuts.

Okay? And they're so beautiful cuts that you

can generate, as well for doing this. But you know, this was just illustrating

some of the cuts. You improve the linear relaxation you

know, nicely, but they are not necessarily capturing all the [UNKNOWN].

Okay? So, let me show, let me talk a lot about

a bit another example that we saw before. Okay?

So, this was graph coloring. Okay?

So, we saw that you know, what, so what we were looking for is how many colors do

we to actually need to color this map of Europe.

Okay? Well, a subse a small subset of Europe.

Okay? And so one of the things that we have is

having this linear you know, this MIP representation, where we would assign you

know, decision variable zero one variable for to, to decide whether a particular

vertex 'v' was assigned color C. Okay?

So, so when you look at this relaxation, what we had was the fact that you know,

the objective function had to be greater, greater than all the possible colors.

That you know, every, every, every country had to be assigned to exactly one

color. And that you know, adjacent country could

not be assigned to the same color. That's what we had.

Okay? So, the, the, this linear relaxation was

actually pretty terrible, so we, we, the only thing that we had was we need at

least two colors. Okay?

Which is kind of obvious. Right?

So, if two countries are adjacent, you need two colors.

Okay? So can we do better?

Can we actually find you know, some new constraints that can actually strengthen

this linear relaxation. Okay?

And so what we saw you know, what we just saw is the concept of clique.

Right? So, can you actually you know, use that

concept in this particular case as well. Okay?

So, let's, let's look at this graph coloring problem in the sense of the

graph. Okay?

So you see basically you know, basically you have an edge between, you have

basically a vertex for everyone of the country and then a link as soon as they

are adjacent. And what you see now is that there are a

bunch of cliques. So this is a clique of size three, this

is a clique of size four. Okay?

So you see that there are basically plenty of cliques there.

And once again, once you have that, you, you can do some kind of reasoning about

the number of colors that you need in a clique.

Okay? So if you have a clique of size three.

Okay? How many colors do you need?

Well, all these vertices are adjacent to each other, so you need at least three

colors. If you have four you know, how many

colors do you need? Okay?

So in a sense, what you can do is add these clique constraints, and these are

some of the constraints that you can use. Okay?

So here this is adding a, a, a three clique, a three clique.

Okay? And what this is basically telling you is

that if you look at the value of these vertices that are in a clique, and if you

sum the value that they have, they have to be greater or equal to three.

Why three? Because we have color zero, we have color

one, we have color two, that's the smallest thing we can have with three

colors. And that's three.

Okay? If we have a four clique, we can do

exactly the same thing, but now it's zero, one, two, and three, which is 6.

So we're basically sticking all these four vertices.

Okay? And we are basically saying that the sum

of these colors that they have okay, has to be at least six.

Okay? So we can put these constraints in there,

once again clique constraints, and we can see what the relaxation is going to do.

In this particular case, what you can see is that you know, for the part for, for,

when you add these three you know, these three clique constraints the number nodes

becomes.. You know, the, you know, the optimal

solution takes nine node, to find the optimal solution you need nine nodes and

the proof of optimality require 41 nodes. When you use this four cliques.

Okay? So you get five nodes, and you get four

for finding the optimal solution and nine nodes for proving optimality.

Okay? So, what is nice is that you need at

least three you know, you, you basically can add these constraints, the strength

from the relaxation, they shorten the proof of optimality and finding the

optimal solution. Okay?

So, this is basically giving you the concept of polyhedral cut.

Okay? So the way to think about it is that we

are looking at constraints, okay, that are actually going to tighten the

relaxation by using the structure of your problem.

Okay? You can show that they are facet of the

convex hull, that's really the best thing you can do, because this catalyst is

strong as possible in the sense. If you had all of them, you would just

use linear programming. Okay?

So what will do, what we'll do next time is look at more interesting ways of

generating these polyhedral cuts, and we'll look at them for you know, also

[UNKNOWN] the traveling sales man plan. Thank you.