Difference: IntegerProgramming (1 vs. 23)

Revision 232018-11-23 - TWikiAdminUser

Line: 1 to 1
 
META TOPICPARENT name="MathematicalProgramming"
<-- Ready to Review - done - Lauren-->
Line: 53 to 53
  -- TWikiAdminGroup - 20 Feb 2008
Deleted:
<
<
META FILEATTACHMENT attachment="latex712a2fd94977f096fb3cae2a1886e3a3.png" attr="h" comment="" date="1203509758" name="latex712a2fd94977f096fb3cae2a1886e3a3.png" stream="GLOB(0xa5a2624)" tmpFilename="latex712a2fd94977f096fb3cae2a1886e3a3.png" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="latexf9f9f812d84e21ff638d258ecdc983fc.png" attr="h" comment="" date="1203509758" name="latexf9f9f812d84e21ff638d258ecdc983fc.png" stream="GLOB(0xa5a2600)" tmpFilename="latexf9f9f812d84e21ff638d258ecdc983fc.png" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="latexe1af37b390435b0910054a0b0835cffe.png" attr="h" comment="" date="1203509758" name="latexe1af37b390435b0910054a0b0835cffe.png" stream="GLOB(0xa5a260c)" tmpFilename="latexe1af37b390435b0910054a0b0835cffe.png" user="BaseUserMapping_333" version="1"
 
META FILEATTACHMENT attachment="bandb.jpg" attr="h" comment="Example of a branch-and-bound tree" date="1203510457" name="bandb.jpg" path="bandb.jpg" size="80351" stream="bandb.jpg" tmpFilename="" user="BaseUserMapping_333" version="2"
Added:
>
>
META FILEATTACHMENT attachment="latex9330d1e6aaec3ee6689d6bca4f64ce5d.png" attr="h" comment="" date="1542935603" name="latex9330d1e6aaec3ee6689d6bca4f64ce5d.png" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="latexcd2df390d0f811577d0143b38426baa6.png" attr="h" comment="" date="1542935603" name="latexcd2df390d0f811577d0143b38426baa6.png" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="latex5af87d2b3f135486d1bb7f8e21475b6e.png" attr="h" comment="" date="1542935603" name="latex5af87d2b3f135486d1bb7f8e21475b6e.png" user="BaseUserMapping_333" version="1"

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.

Revision 212008-05-07 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="MathematicalProgramming"
<-- Ready to Review - done - Lauren-->
Line: 36 to 36
 
Changed:
<
<
>
>
 

Integer Programming with OR Software

Revision 202008-05-07 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="MathematicalProgramming"
<-- Ready to Review - done - Lauren-->
Line: 36 to 36
 
Added:
>
>
 

Integer Programming with OR Software

Revision 192008-04-23 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="MathematicalProgramming"
<-- Ready to Review - done - Lauren-->
Line: 38 to 38
 

Integer Programming with OR Software

Changed:
<
<
>
>
 

To see integer programming in action, check out some of the integer programming case studies:

Revision 182008-04-23 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="MathematicalProgramming"
<-- Ready to Review - done - Lauren-->
Line: 33 to 33
 bandb.jpg

Integer Programming Topics

Changed:
<
<
>
>
 

Integer Programming with OR Software

Revision 172008-04-22 - TWikiAdminUser

Line: 1 to 1
 
META TOPICPARENT name="MathematicalProgramming"
<-- Ready to Review - done - Lauren-->
Line: 35 to 35
 

Integer Programming Topics

Added:
>
>
 

Integer Programming with OR Software

Revision 162008-03-20 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="MathematicalProgramming"
<-- Ready to Review - done - Lauren-->

Integer Programming

Changed:
<
<
Integer programmes are almost identical to linear programmes with one very important exception. Some of the decision variables in integer programmes can only have integer values. The variables are known as integer variables. Since most integer programmes contain a mix of real variables (i.e., that can have any real value) and integer variables they are often known as mixed integer programmes. While the change from a linear programming formulation is a minor one, the effect on the solution process is enormous. Integer programmes can be very difficult problems to solve and currently a lot of research is focussing on finding "good"... - Lauren there is a lot of current research finding "good" ways to solve integer programmes.
>
>
Integer programmes are almost identical to linear programmes with one very important exception. Some of the decision variables in integer programmes can only have integer values. The variables are known as integer variables. Since most integer programmes contain a mix of real variables (i.e., that can have any real value) and integer variables they are often known as mixed integer programmes. While the change from a linear programming formulation is a minor one, the effect on the solution process is enormous. Integer programmes can be very difficult problems to solve and currently a lot of research is focussing on finding "good" ways to solve integer programmes.
  Integer programming, the process of solving a (mixed) integer programme, was originally done using the branch-and-bound process. The branch part of the process eliminated non-integer values for integer variables in the following way:
  • Initially, all variables are left as real variables. The problem is solved using linear programming;
Line: 23 to 23
 The current best integer solution is called the incumbent. After solving a linear programme at a leaf node of the branch-and-bound tree one of the following conditions holds:
  • The linear programme is infeasible (no more branching is possible);
  • The linear programme solution is an integer solution with a better objective value than the incumbent. The incumbent is replaced with this new solution;
Changed:
<
<
  • The linear programme solution has a worse objective than the incumbent. Any nodes created from this node will also have a worse objective than the incumbent. This node is bounded by the incumbent objective;
>
>
  • The linear programme solution has an equal or worse objective than the incumbent. Any nodes created from this node will also have an equal or worse objective than the incumbent. This node is bounded by the incumbent objective;
 
  • The linear programme solution is fractional and has a better objective value than the incumbent. Further branching from this node is necessary to ensure an optimal solution is found.
Deleted:
<
<
  • A Tie? - Cam
  Only the last condition requires more branching, all the other conditions result in the node becoming fathomed and no more branching is required from that node.
Line: 34 to 33
 bandb.jpg

Integer Programming Topics

Changed:
<
<
>
>
 

Integer Programming with OR Software

Changed:
<
<
>
>
  To see integer programming in action, check out some of the integer programming case studies:

Revision 152008-03-09 - LaurenJackson

Line: 1 to 1
 
META TOPICPARENT name="MathematicalProgramming"
Changed:
<
<
<-- Ready to Review -->
>
>
<-- Ready to Review - done - Lauren-->
 

Integer Programming

Revision 142008-03-09 - LaurenJackson

Line: 1 to 1
 
META TOPICPARENT name="MathematicalProgramming"
<-- Ready to Review -->
Line: 16 to 16
  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.
Changed:
<
<
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 optimization principle: Adding constraints to a mathematical programming will result in a deterioration of the optimal objective value.
>
>
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 means that adding the branching constraints to the linear programmes at the branch-and-bound tree nodes will mean the resulting nodes will have an optimal objective function value that is equal to or worse than the optimal objective function value of the original linear programme. Thus the objective function values get worse the deeper into the tree you look. Since we are finding the integer solution in the branch-and-bound tree with the best objective value, we can use any integer solutions to bound the tree.
Line: 34 to 34
 bandb.jpg

Integer Programming Topics

Changed:
<
<
>
>
 

Integer Programming with OR Software

Changed:
<
<
>
>
  To see integer programming in action, check out some of the integer programming case studies:

Revision 132008-03-09 - LaurenJackson

Line: 1 to 1
 
META TOPICPARENT name="MathematicalProgramming"
<-- Ready to Review -->

Integer Programming

Changed:
<
<
Integer programmes are almost identical to linear programmes with one very important exception. Some of the decision variables in integer programmes can only have integer values. The variables are known as integer variables. Since most integer programmes contain a mix of real variables (i.e., that can have any real value) and integer variables they are often known as mixed integer programmes. While the change from a linear programming formulation is a minor one, the effect on the solution process is enormous. Integer programmes can be very difficult problems to solve and there is a lot of current research finding "good" ways to solve integer programmes.
>
>
Integer programmes are almost identical to linear programmes with one very important exception. Some of the decision variables in integer programmes can only have integer values. The variables are known as integer variables. Since most integer programmes contain a mix of real variables (i.e., that can have any real value) and integer variables they are often known as mixed integer programmes. While the change from a linear programming formulation is a minor one, the effect on the solution process is enormous. Integer programmes can be very difficult problems to solve and currently a lot of research is focussing on finding "good"... - Lauren there is a lot of current research finding "good" ways to solve integer programmes.
  Integer programming, the process of solving a (mixed) integer programme, was originally done using the branch-and-bound process. The branch part of the process eliminated non-integer values for integer variables in the following way:
  • Initially, all variables are left as real variables. The problem is solved using linear programming;
Line: 25 to 25
 
  • The linear programme solution is an integer solution with a better objective value than the incumbent. The incumbent is replaced with this new solution;
  • The linear programme solution has a worse objective than the incumbent. Any nodes created from this node will also have a worse objective than the incumbent. This node is bounded by the incumbent objective;
  • The linear programme solution is fractional and has a better objective value than the incumbent. Further branching from this node is necessary to ensure an optimal solution is found.
Changed:
<
<
  • A Tie? - Cam
>
>
  • A Tie? - Cam
  Only the last condition requires more branching, all the other conditions result in the node becoming fathomed and no more branching is required from that node.

Example of a branch-and-bound tree

Changed:
<
<
bandb.jpg
>
>
bandb.jpg
 

Integer Programming Topics

Revision 122008-02-29 - TWikiAdminUser

Line: 1 to 1
 
META TOPICPARENT name="MathematicalProgramming"
<-- Ready to Review -->
Line: 43 to 43
  To see integer programming in action, check out some of the integer programming case studies:
Changed:
<
<

Results from OpsRes web retrieved at 01:55 (GMT)

<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
Number of topics: 10
<--/patternSearchResultCount-->
>
>

Results from OpsRes web retrieved at 01:55 (GMT)

<--/twikiTopRow-->
\usepackage{amsmath} Case Study: Submitted: Operations Research Topics: Application Areas: Contents Problem Description Problem Description Return...
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
\usepackage{amsmath} Case Study: Submitted: Operations Research Topics: Application Areas: Contents Problem Description Problem Description Return...
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
\usepackage{amsmath} Case Study: Submitted: Operations Research Topics: Application Areas: Contents Problem Description Problem Description Return...
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
\usepackage{amsmath} Case Study: Submitted: Operations Research Topics: Application Areas: Contents Problem Description Problem Description Return...
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
\usepackage{amsmath} Case Study: Submitted: Operations Research Topics: Application Areas: Contents Problem Description Problem Description Return...
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
\usepackage{amsmath} Case Study: Submitted: Operations Research Topics: Application Areas: Contents Problem Description Problem Description Return...
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
\usepackage{amsmath} Case Study: Submitted: Operations Research Topics: Application Areas: Contents Problem Description Problem Description Return...
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
\usepackage{amsmath} Case Study: Submitted: Operations Research Topics: Application Areas: Contents Problem Description Problem Description Return...
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
\usepackage{amsmath} Case Study: Submitted: Operations Research Topics: Application Areas: Contents Problem Description Problem Description Return...
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
\usepackage{amsmath} Case Study: Submitted: Operations Research Topics: Application Areas: Contents Problem Description Problem Description Return...
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
Number of topics: 10
<--/patternSearchResultCount-->
  -- TWikiAdminGroup - 20 Feb 2008

META FILEATTACHMENT attachment="latex712a2fd94977f096fb3cae2a1886e3a3.png" attr="h" comment="" date="1203509758" name="latex712a2fd94977f096fb3cae2a1886e3a3.png" stream="GLOB(0xa5a2624)" tmpFilename="latex712a2fd94977f096fb3cae2a1886e3a3.png" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="latexf9f9f812d84e21ff638d258ecdc983fc.png" attr="h" comment="" date="1203509758" name="latexf9f9f812d84e21ff638d258ecdc983fc.png" stream="GLOB(0xa5a2600)" tmpFilename="latexf9f9f812d84e21ff638d258ecdc983fc.png" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="latexe1af37b390435b0910054a0b0835cffe.png" attr="h" comment="" date="1203509758" name="latexe1af37b390435b0910054a0b0835cffe.png" stream="GLOB(0xa5a260c)" tmpFilename="latexe1af37b390435b0910054a0b0835cffe.png" user="BaseUserMapping_333" version="1"
Changed:
<
<
META FILEATTACHMENT attachment="bandb.jpg" attr="" comment="Example of a branch-and-bound tree" date="1203510457" name="bandb.jpg" path="bandb.jpg" size="80351" stream="bandb.jpg" tmpFilename="" user="BaseUserMapping_333" version="2"
>
>
META FILEATTACHMENT attachment="bandb.jpg" attr="h" comment="Example of a branch-and-bound tree" date="1203510457" name="bandb.jpg" path="bandb.jpg" size="80351" stream="bandb.jpg" tmpFilename="" user="BaseUserMapping_333" version="2"

Revision 112008-02-25 - TWikiAdminUser

Line: 1 to 1
 
META TOPICPARENT name="MathematicalProgramming"
<-- Ready to Review -->
Line: 25 to 25
 
  • The linear programme solution is an integer solution with a better objective value than the incumbent. The incumbent is replaced with this new solution;
  • The linear programme solution has a worse objective than the incumbent. Any nodes created from this node will also have a worse objective than the incumbent. This node is bounded by the incumbent objective;
  • The linear programme solution is fractional and has a better objective value than the incumbent. Further branching from this node is necessary to ensure an optimal solution is found.
Added:
>
>
  • A Tie? - Cam
  Only the last condition requires more branching, all the other conditions result in the node becoming fathomed and no more branching is required from that node.

Revision 102008-02-24 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="MathematicalProgramming"
<-- Ready to Review -->
Deleted:
<
<
<-- Under Construction -->
 

Integer Programming

Integer programmes are almost identical to linear programmes with one very important exception. Some of the decision variables in integer programmes can only have integer values. The variables are known as integer variables. Since most integer programmes contain a mix of real variables (i.e., that can have any real value) and integer variables they are often known as mixed integer programmes. While the change from a linear programming formulation is a minor one, the effect on the solution process is enormous. Integer programmes can be very difficult problems to solve and there is a lot of current research finding "good" ways to solve integer programmes.

Revision 92008-02-24 - TWikiAdminUser

Line: 1 to 1
 
META TOPICPARENT name="MathematicalProgramming"
<-- Ready to Review -->
Line: 38 to 38
 

Integer Programming with OR Software

Changed:
<
<
>
>
  To see integer programming in action, check out some of the integer programming case studies:

Revision 82008-02-24 - TWikiAdminUser

Line: 1 to 1
 
META TOPICPARENT name="MathematicalProgramming"
<-- Ready to Review -->
Line: 37 to 37
 
Changed:
<
<

Integer Programming with OR Software ??? Note to Mike -> parent these from the guides to the OR Software ???

>
>

Integer Programming with OR Software

 

Revision 72008-02-23 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="MathematicalProgramming"
<-- Ready to Review -->
Added:
>
>
<-- Under Construction -->
 

Integer Programming

Integer programmes are almost identical to linear programmes with one very important exception. Some of the decision variables in integer programmes can only have integer values. The variables are known as integer variables. Since most integer programmes contain a mix of real variables (i.e., that can have any real value) and integer variables they are often known as mixed integer programmes. While the change from a linear programming formulation is a minor one, the effect on the solution process is enormous. Integer programmes can be very difficult problems to solve and there is a lot of current research finding "good" ways to solve integer programmes.

Revision 62008-02-21 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="MathematicalProgramming"
Added:
>
>
<-- Ready to Review -->
 

Integer Programming

Integer programmes are almost identical to linear programmes with one very important exception. Some of the decision variables in integer programmes can only have integer values. The variables are known as integer variables. Since most integer programmes contain a mix of real variables (i.e., that can have any real value) and integer variables they are often known as mixed integer programmes. While the change from a linear programming formulation is a minor one, the effect on the solution process is enormous. Integer programmes can be very difficult problems to solve and there is a lot of current research finding "good" ways to solve integer programmes.

Revision 52008-02-20 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="MathematicalProgramming"

Integer Programming

Line: 30 to 30
  bandb.jpg
Changed:
<
<

Advanced Integer Programming Topics

>
>

Integer Programming Topics

 

Revision 42008-02-20 - TWikiAdminUser

Line: 1 to 1
 
META TOPICPARENT name="MathematicalProgramming"

Integer Programming

Line: 34 to 34
 
Changed:
<
<

Integer Programming with OR Software

>
>

Integer Programming with OR Software ??? Note to Mike -> parent these from the guides to the OR Software ???

 

To see integer programming in action, check out some of the integer programming case studies:

Revision 32008-02-20 - TWikiAdminUser

Line: 1 to 1
 
META TOPICPARENT name="MathematicalProgramming"

Integer Programming

Changed:
<
<
Integer programmes are almost identical to linear programmes with one very important exception. Some of the decision variables in integer programmes may need to have only integer values. The variables are known as integer variables. Since most integer programmes contain a mix of real variables and integer variables they are often known as mixed integer programmes. While the change from linear programming is a minor one, the effect on the solution process is enormous. Integer programmes can be very difficult problems to solve and there is a lot of current research finding “good” ways to solve integer programmes.
>
>
Integer programmes are almost identical to linear programmes with one very important exception. Some of the decision variables in integer programmes can only have integer values. The variables are known as integer variables. Since most integer programmes contain a mix of real variables (i.e., that can have any real value) and integer variables they are often known as mixed integer programmes. While the change from a linear programming formulation is a minor one, the effect on the solution process is enormous. Integer programmes can be very difficult problems to solve and there is a lot of current research finding "good" ways to solve integer programmes.

Integer programming, the process of solving a (mixed) integer programme, was originally done using the branch-and-bound process. The branch part of the process eliminated non-integer values for integer variables in the following way:

  • Initially, all variables are left as real variables. The problem is solved using linear programming;
  • If one of the integer variables in the linear programming solution has a fractional value, e.g., $x_i = 4.5$, then the linear programme is split in two and the fractional region eliminated. This is done by branching on the variable value to get two new linear programmes, e.g., adding the constraint $x_i \leq 4$ to form one linear programme and $x_i \geq 5$ to form the other.
  • By finding the optimal solution in each of these new linear programmes and comparing we can find the optimal solution for the original problem;
  • If either of the new linear programmes has a fractional value for an integer variable then a new branch is needed.

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.

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 optimization principle: Adding constraints to a mathematical programming will result in a deterioration of the optimal objective value.

 
Deleted:
<
<
Integer programming (the process of solving a (mixed) integer programme) was originally done using the branch-and-bound process. The branch part of the process eliminated non-integer values for integer variables in the following way:
  • Initially, all variables are left as real variables. The problem is solved using linear programming;
  • If one of the integer variables in the linear programming solution has a fractional value, e.g., $x_i = 4.5$, then the linear programme is split in two and the fractional region eliminated. This is done by branching on the variable value, e.g., adding the constraint $x_i \leq 4$ to form one linear programme and $x_i \geq 5$ to form the other.
  • By finding the optimal solution in each of these new linear programmes and comparing we can find the optimal solution for the original problem.
  • If either of the new linear programmes has a fractional value for an integer variable then a new branch is needed.

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 and no further branching is needed. All these values can be compared and the best one is the solution to the original integer programme.
*Note* For MIPs 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 optimization principle:

Adding constraints to a mathematical programming will result in a deterioration of the optimal objective value.

 This means that adding the branching constraints to the linear programmes at the branch-and-bound tree nodes will mean the resulting nodes will have an optimal objective function value that is equal to or worse than the optimal objective function value of the original linear programme. Thus the objective function values get worse the deeper into the tree you look. Since we are finding the integer solution in the branch-and-bound tree with the best objective value, we can use any integer solutions to bound the tree.
Changed:
<
<
The current best integer solution is called the incumbent. After solving a linear programme at a leaf node of the branch-and-bound tree one of the following conditions holds:
  • The linear programme is infeasible (no more branching is possible);
  • The linear programme solution is an integer solution with a better objective value than the incumbent. The incumbent is replaced with this new solution;
  • The linear programme solution has a worse objective than the incumbent. Any nodes created from this node will also have a worse objective than the incumbent. This node is bounded by the incumbent objective;
  • The linear programme solution is fractional and has a better objective value than the incumbent. Further branching from this node is necessary to ensure an optimal solution is found.
>
>
The current best integer solution is called the incumbent. After solving a linear programme at a leaf node of the branch-and-bound tree one of the following conditions holds:
  • The linear programme is infeasible (no more branching is possible);
  • The linear programme solution is an integer solution with a better objective value than the incumbent. The incumbent is replaced with this new solution;
  • The linear programme solution has a worse objective than the incumbent. Any nodes created from this node will also have a worse objective than the incumbent. This node is bounded by the incumbent objective;
  • The linear programme solution is fractional and has a better objective value than the incumbent. Further branching from this node is necessary to ensure an optimal solution is found.

Only the last condition requires more branching, all the other conditions result in the node becoming fathomed and no more branching is required from that node.

 
Changed:
<
<
Only the last condition requires more branching, all the other conditions result in the node becoming fathomed and no more branching is required from that node.
>
>
Example of a branch-and-bound tree
 
Changed:
<
<

Example

>
>
bandb.jpg

Advanced Integer Programming Topics

Integer Programming with OR Software

To see integer programming in action, check out some of the integer programming case studies:

 

Results from OpsRes web retrieved at 01:55 (GMT)

<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
Number of topics: 10
<--/patternSearchResultCount-->

-- TWikiAdminGroup - 20 Feb 2008

Added:
>
>
META FILEATTACHMENT attachment="latex712a2fd94977f096fb3cae2a1886e3a3.png" attr="h" comment="" date="1203509758" name="latex712a2fd94977f096fb3cae2a1886e3a3.png" stream="GLOB(0xa5a2624)" tmpFilename="latex712a2fd94977f096fb3cae2a1886e3a3.png" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="latexf9f9f812d84e21ff638d258ecdc983fc.png" attr="h" comment="" date="1203509758" name="latexf9f9f812d84e21ff638d258ecdc983fc.png" stream="GLOB(0xa5a2600)" tmpFilename="latexf9f9f812d84e21ff638d258ecdc983fc.png" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="latexe1af37b390435b0910054a0b0835cffe.png" attr="h" comment="" date="1203509758" name="latexe1af37b390435b0910054a0b0835cffe.png" stream="GLOB(0xa5a260c)" tmpFilename="latexe1af37b390435b0910054a0b0835cffe.png" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="bandb.jpg" attr="" comment="Example of a branch-and-bound tree" date="1203510457" name="bandb.jpg" path="bandb.jpg" size="80351" stream="bandb.jpg" tmpFilename="" user="BaseUserMapping_333" version="2"

Revision 22008-02-20 - TWikiAdminUser

Line: 1 to 1
 
META TOPICPARENT name="MathematicalProgramming"
Added:
>
>

Integer Programming

Integer programmes are almost identical to linear programmes with one very important exception. Some of the decision variables in integer programmes may need to have only integer values. The variables are known as integer variables. Since most integer programmes contain a mix of real variables and integer variables they are often known as mixed integer programmes. While the change from linear programming is a minor one, the effect on the solution process is enormous. Integer programmes can be very difficult problems to solve and there is a lot of current research finding “good” ways to solve integer programmes.

Integer programming (the process of solving a (mixed) integer programme) was originally done using the branch-and-bound process. The branch part of the process eliminated non-integer values for integer variables in the following way:

  • Initially, all variables are left as real variables. The problem is solved using linear programming;
  • If one of the integer variables in the linear programming solution has a fractional value, e.g., $x_i = 4.5$, then the linear programme is split in two and the fractional region eliminated. This is done by branching on the variable value, e.g., adding the constraint $x_i \leq 4$ to form one linear programme and $x_i \geq 5$ to form the other.
  • By finding the optimal solution in each of these new linear programmes and comparing we can find the optimal solution for the original problem.
  • If either of the new linear programmes has a fractional value for an integer variable then a new branch is needed.

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 and no further branching is needed. All these values can be compared and the best one is the solution to the original integer programme.
*Note* For MIPs 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 optimization principle:

Adding constraints to a mathematical programming will result in a deterioration of the optimal objective value.

This means that adding the branching constraints to the linear programmes at the branch-and-bound tree nodes will mean the resulting nodes will have an optimal objective function value that is equal to or worse than the optimal objective function value of the original linear programme. Thus the objective function values get worse the deeper into the tree you look. Since we are finding the integer solution in the branch-and-bound tree with the best objective value, we can use any integer solutions to bound the tree.

The current best integer solution is called the incumbent. After solving a linear programme at a leaf node of the branch-and-bound tree one of the following conditions holds:

  • The linear programme is infeasible (no more branching is possible);
  • The linear programme solution is an integer solution with a better objective value than the incumbent. The incumbent is replaced with this new solution;
  • The linear programme solution has a worse objective than the incumbent. Any nodes created from this node will also have a worse objective than the incumbent. This node is bounded by the incumbent objective;
  • The linear programme solution is fractional and has a better objective value than the incumbent. Further branching from this node is necessary to ensure an optimal solution is found.

Only the last condition requires more branching, all the other conditions result in the node becoming fathomed and no more branching is required from that node.

Example

Results from OpsRes web retrieved at 01:55 (GMT)

<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
<--/twikiTopRow-->
<--/twikiSummary-->
<--/twikiBottomRow-->
<--/patternSearchResult-->
Number of topics: 10
<--/patternSearchResultCount-->
 -- TWikiAdminGroup - 20 Feb 2008 \ No newline at end of file

Revision 12008-02-20 - TWikiAdminUser

Line: 1 to 1
Added:
>
>
META TOPICPARENT name="MathematicalProgramming"
-- TWikiAdminGroup - 20 Feb 2008
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback