Scribd
Upload
30 views2 pages

Learning Material

Integer linear programming deals with linear programming problems that require the decision variables to have integer values. There are three types of integer programming problems: pure integer where all variables are integers, mixed integer where some variables are integers, and zero-one binary integer where variables are 0 or 1. Integer programming problems can be solved using branch and bound or cutting plane methods.

Uploaded by

SHanim
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
30 views2 pages

Learning Material

Integer linear programming deals with linear programming problems that require the decision variables to have integer values. There are three types of integer programming problems: pure integer where all variables are integers, mixed integer where some variables are integers, and zero-one binary integer where variables are 0 or 1. Integer programming problems can be solved using branch and bound or cutting plane methods.

Uploaded by

SHanim
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

Integer Linear Programming

In linear Programming each decision variables might have values in fraction as well. However
there are certain real life problems in which the fractional value of the decision variables has no
significance. For example expressing the value as 2.3 persons will not make any sense . The
integer solution to a problem can however be obtained by rounding off the optimum value of
the variables to the nearest integer value. This approach can be easy in terms of economy of
effort, time and the cost that might be required to derive an integer solution. However the
solution may not satisfy all the given constraints. Also the value so obtained may not be the
optimal value. All such difficulties can be avoided if the given problem is solved by integer
programming technique where an integer solution is required.

Integer LP problems are termed as pure or mixed integer problems accordingly as some or all of
the variables are restricted to integer values. An integer programming problem has important
application in various field as Capital budgeting , Construction Scheduling, Plant location and
size, routing and shipping schedule, batch size, capacity expansion, fixed charge etc are few
problems that demonstrate the areas of application of integer programming.

Types of Integer Programming Problems

Linear Programming Problem can be categorized into three categories:

i) Pure (all) integer programming problems in which all decision variables are restricted
to integer values.
ii) Mixed integer programming problems in which some, but not all, of the decision
variables are restricted to integer values.
iii) Zero – one integer programming problems in which all decision variables are
restricted to integer values of either 0 or 1 ( Binary integer programming).

Integer Programming Problem can be solved with two different methods namely

i) Branch and Bound technique


ii) Gomory’s cutting plane method
The cutting plane method was developed by R.E. Gomory in 1956. This is based on creating a
sequence of linear inequalities called cuts. Such a cut reduces a part of the feasible region of the
given LP problem leaving out a feasible region of the integer LP problem. The hyperplane (
additional constraints) boundary of a cut is called the cutting plane. In a mixed integer
programming problem few of the decision variables require integer solutions. The binary integer
programming problem requires the decision variables to have values between zero and one. The
cutting plane method requires the use of standard LP approach between each cutting plane
application. Branch and bound method divides the feasible solution space into smaller parts by
branching. Instead of using integer programming method , directly rounding off solution values
of decision variables in an LP problem may not be acceptable because one of the reason is it
may not satisfy the constraints and it may not be the optimal solution. The Branch and Bound
technique to maximization problem, a node is terminated if node has an infeasible solution and
upper bound is less that the current that the current sub problem’s lower bound. While applying
the cutting plane method, dual simplex is used to maintain feasibility. A non- integer variable is
chosen in the optimal simplex table of the integer LP problem to construct a Gomory constraints.
The cutting plane algorithm promises optimal integer solution in a finite in a finite number of
iterations. In using the cutting Plane algorithm, the problem is first solved as an LPP by dropping
the integer requirements. Then a cutting plane is introduced by using a constraint in the optimal
solution which bears a fractional right hand side value. Cuts are introduced until all the variables
assume integer values.

You might also like