| |
| META TOPICPARENT |
name="MathematicalProgramming" |
<-- 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. |
>
> | 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;
|
| |
- 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 |
|
<
< |  |
>
> |  |
| |
Integer Programming Topics |
Copyright © 2008-2025 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.