Supplement - example of integer programming

1. Will be nonlinear 0-1 The problem becomes linear 0-1 problem

• Example 1
  

First do variable replacement , hold y=x(1)x(2), Has the following relation ：

x(1) + x(2) - 1 ≤ y ≤ x(1)
x(1) + x(2) - 1 ≤ y ≤ x(2)

So there is linearity 0-1 Planned as ：

max z = x(1) + y - x(3)
s.t.:
     -2x(1) + 3x(2) + x(3) ≤ 3,
      x(1) + x(2) - 1 ≤ y ≤  x(1),
      x(1) + x(2) - 1 ≤ y ≤  x(2),
      x(j) = 0  or  1, j = 1:3
      y = 0  or  1 
     

2. Assignment problem

• Example 2
  One fleet has 8 Vehicles this 8 Cars are stored in different places , Captain wants Send one of them 5 Cars arrive at 5 Different construction sites to transport goods . Each car is stored The cost of transferring to the loading place is listed in the table 2 5, Ask which one to choose 5 Car transfer Where to ship the goods , In order to minimize the total cost of transferring each vehicle from the location to the loading location ？
  
  remember c(i)(j) It means the first one j Car No. 1 is transferred to the loading place i The cost . introduce 0-1 Variable ：
  x(i)(j) = 1 It means the first one j Car No. 1 is transferred to the loading place i , conversely x(i)(j) = 0 It means the first one j Car No. 1 was not transferred to the loading place i.
  establish 0-1 Integer programming model ：
  

%  Put two-dimensional decision variables Xij(i=1:5,j=1:8) Become a one-dimensional decision variable yk(k=1:40)
clc,clear
c = [30,25,18,32,27,19,22,26
     29,31,19,18,21,20,30,19
     28,29,30,19,19,22,23,26
     29,30,19,24,25,19,18,21
     21,20,18,17,16,14,16,18];
c=c(:);
a=zeros(8,40); % 8 That's ok 40 Zero matrix of columns 
intcon=1:40; %  One dimensional decision variables k The value of 
for j=1:8 %  Opposite operation 
    a(j,(j-1)*5+1:j*5) = 1;
end
b=ones(8,1); % 8 That's ok 1 Column is 1 matrix 
Aeq=zeros(5,40);
for i=1:5 %  Column operation 
    Aeq(i,i:5:40) = 1;
end
beq=ones(5,1);
lb=zeros(40,1);
ub=ones(40,1);
[x,y] = intlinprog(c,intcon,a,b,Aeq,beq,lb,ub);
x = reshape(x,[5,8]),y % reshape It's output 5 That's ok 8 Column matrices 

Output is

x =

     0     0     1     0     0     0     0     0
     0     0     0     1     0     0     0     0
     0     0     0     0     1     0     0     0
     0     0     0     0     0     0     1     0
     0     0     0     0     0     1     0     0

 The minimum total cost is  y = 87