IntegerProgramming < OpsRes

---+ 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.

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._

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 of a branch-and-bound tree*

<img width="566" alt="bandb.jpg" src="%ATTACHURLPATH%/bandb.jpg" height="379" />

---++ Integer Programming Topics
   * [[LPRelaxation][Linear Programming (LP) Relaxation]]
   * [[MasterSlaveConstraints][Master-Slave Constraints]]

---++ Integer Programming with OR Software ??? Note to Mike -> parent these from the guides to the OR Software ???
   * [[IPWithAMPL][Integer Programming with AMPL/CPLEX]]
   * [[IPWithBcp][Integer Programming with Bcp]]

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

%SEARCH{search="IntegerProgramming +\"Case Study:\"" type="keyword" casesensitive="on" nosearch="on" nosummary="on" excludetopic="%TOPIC%"}%

-- Main.TWikiAdminGroup - 20 Feb 2008
Attachments
Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
jpg	bandb.jpg	r2 r1	manage	78.5 K	2008-02-20 - 12:27	TWikiAdminUser	Example of a branch-and-bound tree
This topic: OpsRes > WebHome > MathematicalProgramming > IntegerProgramming
Topic revision: r5 - 2008-02-20 - MichaelOSullivan