Integer programming is one of the important branch of optimization where some of the variables are bound to be integers.
The integer linear programming is described as follows.
Subject to: A*X <= b,
Aeq*X = beq,
Where the elements of X are integers.
There are two types of integer programming problems.
1. Binary integer programming.
2. Mixed integer Programming
The mixed integer programming can be modeled as binary integer programming by making some simplifications.
Solving a binary integer programming problem.
To solve binary integer programming problem in Matlab the routine “bintprog” is used
[X FVAL] = bintprog(f,A,b,Aeq,beq,X0) sets the starting point to X0. The starting point X0 must be binary integer and feasible, or it will be ignored.
This routine returns the value of the objective function at
FVAL = f'*X.
-x1+x3 < 0
-x2 + x4< 0
f = [-9; -5; -6; -4];
A = [6 3 5 2; 0 0 1 1; -1 0 1 0; 0 -1 0 1];
b = [9; 1; 0; 0];
[X F] = bintprog(f,A,b)
l=[0 0 0 0]';
u=[1 1 1 1]';
Binary integer programming
F = -14
F1 = -15.0000
It can be observed that function value in integer programming is little more.
Rounding off the linear programming results does not yield the integer programming results.