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.