Discrete Optimization aims to make good decisions when we have many possibilities to choose from. Its applications are ubiquitous throughout our society. Its applications range from solving Sudoku puzzles to arranging seating in a wedding banquet. The same technology can schedule planes and their crews, coordinate the production of steel, and organize the transportation of iron ore from the mines to the ports. Good decisions on the use of scarce or expensive resources such as staffing and material resources also allow corporations to improve their profit by millions of dollars. Similar problems also underpin much of our daily lives and are part of determining daily delivery routes for packages, making school timetables, and delivering power to our homes. Despite their fundamental importance, these problems are a nightmare to solve using traditional undergraduate computer science methods. This course is intended for students who have completed Advanced Modelling for Discrete Optimization. In this course, you will extend your understanding of how to solve challenging discrete optimization problems by learning more about the solving technologies that are used to solve them, and how a high-level model (written in MiniZinc) is transformed into a form that is executable by these underlying solvers. By better understanding the actual solving technology, you will both improve your modeling capabilities, and be able to choose the most appropriate solving technology to use. Watch the course promotional video here: https://www.youtube.com/watch?v=-EiRsK-Rm08
3.3.3 Cutting Planes
Loading...
来自 The University of Melbourne 的课程
Solving Algorithms for Discrete Optimization
4 个评分
从本节课中
Mixed Integer Programming
This module starts by introducing linear programming and the Simplex algorithm for solving continuous linear optimization problems, before showing how the method can be incorporated into Branch and Bound search for solving Mixed Integer Programs. Learn Gomory Cuts and the Branch and Cut method to see how they can speed up solving.
与讲师见面
Prof. Jimmy Ho Man LeeProfessor
Department of Computer Science and Engineering
Prof. Peter James StuckeyProfessor
Computing and Information Systems
The new method proposed by Zhuge Liang involved large cuts to Qi shields.
Tai Shang Lao Jun warned that this might have
negative consequences and suggested using another method to help find the weakest point.
Zhuge Liang summoned the dragon of dimensions for assistance from the professors.
So, Nu Zha is ready to make a big cut through this Qi shield in order to get closer
to finding the weakest priest and he's just about to do this when Tai Shang Lao Jun says,
"Hang on, hang on, wait a minute.
So, if we cut through this shield,
we're going to let out a whole lot of hell energy,
which is going to weaken you considerably.
And if that's the case, it might be that these priests may well be able to defeat you."
So, we really want to be able to find this weakest integral point
amongst the Qi shield but we're not allowed to employ this Branch and Bound,
which requires cutting through the shield in a large way,
so basically splitting the problem into two.
So, if this is our MiniZinc model,
we can't employ Branch and Bound,
then how can we solve the same problem?
So, we can rewrite our problem this way with this initial Simplex tableau,
and notice we have done everything as normal except that we've multiplied
the second constraint here by two so that we have all integer coefficients.
And the important point about that is that now,
there's all integer coefficients here,
and we know that x, y, and z are integer vaiables,
and it's very clear that all of the slack variables, s1,
s2 and s3, will have to take integer values in any of these equations for them to hold.
Alright, so if we now solve that using our Simplex method,
we'll find this optimal objective and this point here which,
of course, is not integral,
so it doesn't correspond to one of the priests.
That was our problem. If we have a look at the final Simplex tableaux,
??> it actually spells out this solution.
We can see the objective value here and
the values of the slack variables and the other variables,
which are taking non-zero values.
So, this is the resulting Simplex tableau,
and you can see that the objective cannot be be further improved because, of course,
these are non-negatives, y, s2,
and s3, so we can only increase them,
which will just decrease the objective.
Alright, so what can we do?
Let's have a look at this second constraint row here,
which says that z, at the current point,
is taking this value, four forty divided by nine, a non-integral value.
So, we can rewrite this equation just by moving terms around.
So we can rewrite it to z plus five-ninths y plus
two-ninths s2 minus one-third s3 equals forty divided by nine.
That's just moving all of these terms here over to the other side.
Then we can sort of collect together terms.
So, we can collect together all the integer terms here,
so we take z minus s3,
so we're going to add a copy of s3,
so subtract one here and add one here so that we
end up with two-thirds s3 left over here.
We're going to take the integer part of that, which is four,
and move it over here, and leave the fractional part left over, which is four-ninths.
So you can see that 36-ninths plus four nights is forty-ninths.
And we split our problem into two parts.
Here's an integer part and here is a fractional part.
So we know that in any solution,
this thing must be an integer value.
And we know that this thing must be a positive value,
because these are all non-negative variables and we're multiplying by positive fractions.
And really, that shows us that the only way we can get
our four-ninths is to get the four-ninths out of this part here, alright?
So the four-ninths, the fractional value that's left over,
can only come out of this expression here,
because this is an integer expression.
It can't create any fractional value.
So if we think about this in more general terms,
if we have some equation which has an integer expression and a fractional expression,
which is all of strictly positive fractions,
so we cannot have some subtraction of them,
and we have this fractional value here,
which is also positive,
then it must be the case that this fractional expression here,
F is greater than or equal to f,
because it's only the F that can create this fractional value.
So, in our example,
here is the integer part,
here is the fractional part which is definitely strictly positive,
and here is the fractional part left over.
And from this, we can gather that
this four-ninths has to be created by this fractional part.
So it could be that the whole thing adds up to exactly four-ninths,
or it could be one plus four-ninths,
or two plus four-ninths, or whatever.
But it's certainly bigger than or equal to four-ninths.
So we know this constraint is a consequence of the original row that we looked at.
So, we've generated a Gomory Cut.
The Gomory Cut here said that
these fractional part had to be greater than or equal to four-ninths,
we can multiply through and get this integer form.
And in fact, we can substitute for the slack variables s2 and s3 to
just get back an equation in terms of the original variables,
2x plus y plus 2z is less than equal to 24.
Now, the important part of adding this Gomory Cut to our original problem is,
the cut certainly removes the optimal solution to the original linear relaxation,
because it's going to prevent that constraint from holding at optimality.
And all the feasible solutions of the original MIP are retained.
So, what we're adding here is a cut which can't cut off any integer solutions,
because it was just a consequence of some equation of the row,
which is already a consequence of the original problem,
and we made sure that its reasoning was correct.
It was a true consequence of that constraint so it can't get rid of any solution.
We used the integrality of the variables in order to generate this cut.
So, we've left behind all the integer solutions,
but we may have cut off some non-integer solutions, and that's the important part.
So in general, we can look for,
in a Simplex tableau,
if we see a row like this,
x_i equals b plus f,
so we've got a non-integer solution in this sol form for x_i,
and some other part.
So, the b is the integer part of the current solution for x_i,
and the f is this fractional part between zero and one.
We can rewrite this just as a form,
move all the equation onto this side.
Then we can take the floor of all of these coefficients here.
So that'll certainly be an integer.
So this is really getting the integer part of this a_i, x_i.
And since we have the floor here,
we subtract it here, so we still got the same equation.
And the key thing to notice is that this expression here,
a_i minus the floor of a_i,
is certainly a fraction or zero if a_i is already an integer,
and it's certainly positive, non-negative.
It's a fraction between zero and one.
Alright, once we've done that,
we know since this can only generate integers,
then this part has to generate the fractional part.
So we know it has to be greater than equal to f.
And that's exactly the Gomory Cut in general.
But notice also, we can build a Gomory Cut by taking any row of
the Simplex tableaux as long as this is not an integer.
Of course, if this is an integer,
then we're not going to learn anything here because this f will be zero.
And if the objective value
is not an integral as it was in our example,
we could also use that to generate a Gomory cut.
So, we can actually use Gomory cuts to completely solve an integer linear program.
So we just solve our linear program,
we add Gomory cuts from the LP basis, and we resolve.
Right. We're going to cut off part of the solution and if we
keep doing this forever and ever eventually,
in a finite amount of time,
we will actually find the LP solution is forced to be integral.
And the problem with doing this in general is that it may not converge very fast,
it might take a lot of iterations through this loop to get an integral solution,
and the other thing is that deciding which of the Gomory cuts to add is not so obvious.
So some of them will be very useful about driving us towards an integral solution and some not,
and a far the problem is that as we add
more and more Gomory cuts actually the coefficients of our constraints tend to grow,
and they grow very fast,
and then that makes it hard for actually our solvers to solve because
solving with big coefficients starts to get mathematical inaccuracies happening.
Alright. We've generated this Gomory cuts,
we can introduce that into our linear programming model by adding the Slack variable,
and then we can resolve the LP,
and then in this case we'll get to this solution and if we look at
this very nicely we've actually generated an integral solution.
So x takes value 8,
z takes value 4 and y takes value 0 and we found a solution, right?
An objective of 36, and if we look at adding that cutting,
what we've done is cut off a little bit of the polytype type,
the original polytype and if we zoom in we can see here we have
this little new facet that's come from cutting
that off and we've ended up with the simplex at this point here,
which is an optimal solution.
So it turns out that actually there are
other optimal solutions so exactly everywhere along this line is also optimal.
So we may not have been lucky.
The simplex may have ended up in this point,
as we representing this point because this is
an equally good solution from the real numbers perspective,
it's not so good for what we're looking
for because we're looking for an integer solution.
So we may end up here and may end up needing to do more cuts.
So remember the final simplex of the original LP had
another row which had a non-integral solution here for x,
we took the z row before,
we can generate a Gomory cut from that.
So we can go through exactly the same process,
we can rewrite like this way,
we can separate it into an integer part and
a fractional part equals this fraction and that would generate us
another Gomory cut in this case this one, and in
terms of the original variables if we
substitute that these slack variables we get this one instead.
If we did that, if we chose to add this Gomory cut instead,
we can resolve the LP and we get to this solution and you can see it's not integral.
So we haven't really solved our problem yet and if we
look at what's happened in our polytope,
then this cut has added another facet here,
but none of the points on this intersection were integral
so we're not going to find an integral optimal at this point.
So we were lucky in our example we picked
the right Gomory cut and in fact we are lucky also that
the simplex ended up in an optimal integral point
instead of an equally good non-integral point.
So here the simplex has ended us up here which is non-integral,
and all the other points in this case,
this is the optimal, but all of the other points are also non-integral.
So Gomory cuts is the most basic form of cutting plane,
we can extend them to mixed integer programs,
so we assume the variables are real and not integer.
And obviously that tends to generate weaker cuts
because if we have non-integral variables and we can't use this integer reasoning.
But there are other important general classes of cuts,
mixed integer rounding cuts,
a general way of building a cut for
arbitrary mixed integer programs and Lift and Project Cuts is another way.
And the most important thing though is with cuts in general is that we can combine
these cutting plane methods with branch and bound and
that obtains this method we call Branch and
Cut and the nice thing about Branch and Cut is
that if we just use pure cutting plane methods
then we typically get this explosion of coefficients,
the coefficients get bigger and bigger and bigger
and it gets harder and harder to solve the LP.
But if we combine the power of search,
branch and bound with cutting planes we can get
very useful cuts which will quickly drive us to integer solutions
and we won't just be forced to generate many many more until
we only get an optimal solution by cutting planes.
So Branch and Cut is we take our branch and bound algorithm which we've seen before,
we solve the relaxation giving some solution,
if it's integer value we're finished,
otherwise we add the cutting planes to P and
resolve and sort of go around this loop any number of times we want to,
and then we get to our branching stage where we pick a variable x_i which is integer
which takes a non-integer value and then we break
into two problems and then solve them using the same way.
So Branch and Cut is just a minor extension of branch and bound where they have
the option to add cutting planes in the middle of any of these searches.
So cutting planes are a vital component of
modern commercial MIP solvers and
there's these general cutting plane methods like Gomory cuts,
Mixed Integer Rounding Cuts, and Lift and Project cuts,
and there's other cutting plane methods which are based on
specific structures like Knapsack Cover Cuts and Clique Cuts.
And it's interesting that Gomory cuts were
the first cutting plane method ever
devised and though initially thought to be impractical,
it's sort of interesting that they could
actually be used as a way of solving the problem,
but then they saw this explosion of
coefficients and made them look impractical in general and actually now
there a very important component in MIP and part of
this reason is that if we use Gomory cuts in Branch and Cuts so we're
not just only using Gomory cuts to solve the problem then actually they can give us
very good cutting information without causing large amounts of instability.
So in summary cutting planes are an essential method for solving MIPs.
So they're used in presolving where we do a lot
of structural cuts can be applied to simplify the problem
and they are used during search where we can do
cutting methods like Gomory cuts to tighten the LP relaxation.
And so they're an essential part of how MIP solvers work,
but there's always a lot more to learn about MIP.
