## Welcome to the world of Optimizations

In this blog concepts of conventional and unconventional optimization techniques are discussed.

## Wednesday, December 8, 2010

### Binary integer programming.

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.
min f'*X
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.
Example
Minimize -9x1-5x2-6x3-4x4
Subject to
6x1+3x2+5x3+2x4<9
x3+x4  <1
-x1+x3   <   0
-x2 +  x4<  0

Program
Clear;
clc;
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]';
[X1 F1]=linprog(f,A,b,[],[],l,u)
Results
Binary integer programming
X =

1
1
0
0
F =  -14
Linear programming
X1 =
0.6667
1.0000
0.0000
1.0000
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.