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.
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback