Difference: IntegerProgramming (21 vs. 22)

Revision 222009-10-09 - MichaelOSullivan

Line: 1 to 1

META TOPICPARENT	name="MathematicalProgramming"

<-- Ready to Review - done - Lauren-->

Line: 14 to 14

This branching process results in the formation of a branch-and-bound tree (we will discuss the bounding next). Each node in this tree represents a linear programme consisting of the original linear programme and the extra branches added. Eventually all the leaf nodes in the tree will contain solutions where all the integer variables have integer values (an integer solution) and no further branching is needed. All these values can be compared and the best one is the solution to the original integer programme.

Changed:

<
<

Note For mixed integer programmes of any reasonable size this tree could be huge, in fact it grows exponentially as the number of integer variables increases.

>
>

Note For mixed integer programmes of any reasonable size this tree could be huge; in fact it grows exponentially as the number of integer variables increases.

The bounding process allows sections of the branch-and-bound tree to be removed from consideration before all the leaf nodes have integer solutions. It relies on the following optimisation principle: Adding constraints to a mathematical programme will result in a deterioration of the optimal objective value.

View topic | History: r23 < r22 < r21 < r20 | More topic actions...