7.2.2 Integer programming

1. Definition: If some or all of the variables in the planning are defined as integers, it is called integer planning.

2. Classification: pure integer programming and mixed integer programming.

3. Features:

(1) The original linear programming has an optimal solution, when the independent variables are restricted to integers:

a. If the original optimal solution is all integers, then the optimal solution still holds

b. There is no feasible solution to integer programming

c. There is a feasible solution, but it is not the original optimal solution.

4. Classification of solution methods

(1) Branch and bound method

(2) Cutting plane method

(3) Implicit enumeration method

(4) Hungarian law

(5) Monte Carlo method

branch and bound

1. The algorithm is as follows (solve the integer programming maximization problem)

Figure 1 Integer programming

MATLAB implementation

function r=checkint(x)
% Determine whether x(i) is an integer. If yes, r(i) returns 1, if not, returns 0 %Input parameters: x X vector
%Output parameters: r R vector for i=1:length(x) if(min(abs(x(i)-floor(x(i))),abs(x(i)-ceil(x(i))))<1e-3) r(i)=1; else r(i)=0; end
end

function val=isrowinmat(arow,mat)
% is used to determine whether mat contains the same vector as arow %Input variable: arrow vector
% mat matrix
%Output variable: val 1 means yes, 0 means no
val=0;
rows=size(mat,1);
for i=1:rows temp=(mat(i,:)==arow); if length(find(temp==0))==0 val=1; return; else val=0; end;
end

function [x,fval,exitflag,output,lambda]=linprogdis(ifint,f,A,b,Aeq,beq,lb,ub,x0,options)
% Usage
% [x,fval,exitflag,output,lambda]=lpint(ifint.f,A,b,Aeq,beq)
% [x,fval,exitflag,output,lambda]=lpint(ifint,f,A,b,Aeq,beq,lb)
% [x,fval,exitflag,output,lambda]=lpint(ifint,f,A,b,Aeq,beq,lb,ub)
% [x,fval,exitflag,output,lambda]=lpint(ifint,f,A,b,Aeq,beq,lb,ub,x0)
% [x,fval,exitflag,output,lambda]=lpint(ifint,f,A,b,Aeq,beq,lb,ub,x0,options) if nargin<10, options=[]; end
if nargin<9, x0=[]; end
if nargin<8, ub=inf*ones(size(f)); end
if nargin<7, lb=zeros(size(f)); end [x,fval,exitflag,output,lambda]=linprog(f,A,b,Aeq,beq,lb,ub,x0,options); if exitflag<=0 % means that linear programming has no optimal solution return
end v1=find(ifint==1); %Find the subscript of the variable that requires integer programming temp=x(v1);% can be returned if integer programming is not required.
if isempty(temp) return
end v2=find(checkint(temp)==0);
if isempty(v2) % are all integers, get the most popular solution return
end k=v1(v2(1)); temp1=zeros(1,length(f));
temp1(k)=1;
low=floor(x(k));
if isrowinmat([temp1,low],[A,b])==1 thisA=A; thisb=b;
else thisA=[A;temp1]; thisb=b; thisb(end+1)=low;
end [x1,fval1,exitflag1,output1,lambda1]=linprogdis(ifint,f,thisA,thisb,Aeq,beq,lb,ub,x0,options); temp2=zeros(1,length(f));
temp2(k)=-1;
high=-ceil(x(k));
if isrowinmat([temp2,high],[A,b])==1 thisA=A; thisb=b;
else thisA=[A;temp2]; thisb=b; thisb(end+1)=high;
end [x2,fval2,exitflag2,output2,lambda2]=linprogdis(ifint,f,thisA,thisb,Aeq,beq,lb,ub,x0,options); if (isempty(v2) && ((exitflag1>0 && exitflag2<=0 && fval<=fval)||(exitflag2>0 && exitflag1<=0 && fval<=fval2)||(exitflag1>0 && exitflag2>0 && fval<=fval1 && fval<=fval2))) disp('error call'); return ; % means they are all integers
end if exitflag1>0&&exitflag2<=0 x=x1; fval=fval1; exitflag=exitflag1; output=output1; lambda=lambda1;
elseif exitflag1<=0&&exitflag2>0 x=x2; fval=fval2; exitflag=exitflag2; output=output2; lambda=lambda2;
elseif exitflag1>0 && exitflag2>0 if fval1<fval2 x=x1; fval=fval1; exitflag=exitflag1; output=output1; lambda=lambda1; else x=x2; fval=fval2; exitflag=exitflag2; output=output2; lambda=lambda2; end
end

3. 0-1 type integer programming

1. Definition: The value of a variable can only be 0-1. In this case, we can actually convert different integer programs into 0-1 programs.

2. Practical issues:

Figure 2 Integer programming

Here we can directly list an equation that is a 0-1 planning. Assume the variable xi, "1" means it is selected, and "0" means it is not selected.

3. Mutually exclusive constraints can be transformed into the same type.

Figure 3 Integer programming

4. Three methods for solving integer programming

(1) Exhaustive method, this method is relatively simple = =, but the most effective, and in some cases it can only be done exhaustively.

(2) Transitional implicit enumeration method

a. First tentatively find a feasible solution X (arbitrarily bring it into the evaluation)

b. Then depending on whether you are seeking a maximum value or a minimum value, if you are seeking a maximum value, then any solution with a target value <

c. Improve new filtering conditions

d. Then verify the target value and finally obtain it.

PS: How should I put it? This method is a disguised exhaustion. If you are unlucky, it will become an exhaustion. However, because the target value is compared first, the amount of calculation can be reduced, so it is still effective (but be careful not to make the mistake of repeated testing).

(3) Monte Carlo method (random sampling method)

It means choosing not to enumerate all points, but to randomly select samples to estimate the whole. If the sample is large enough, the credibility will be very high.

For example, to solve this problem:

Figure 4 Integer programming

MATLAB programming solution:

function [ f,g ] = mengte( x )
%MENGTE Type objective function and constraints for integer linear programming
% f: refers to the objective function vector
% g: refers to the constraint vector f=x(1)^2+x(2)^2+3*x(3)^2+4*x(4)^2+2*x(5)^2-8*x(1)-2*x(2)-3*x(3)-x(4)-2*x(5); g=[sum(x)-400 x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800 2*x(1)+x(2)+6*x(3)-200 x(3)+x(4)+5*x(5)-200]; end

rand('state',sum(clock));
p0=0;
tic
for i=1:10^6 x=99*rand(5,1); x1=floor(x);x2=ceil(x); [f,g]=mengte(x1); if sum(g<=0)==4 if p0<=f x0=x1;p0=f; end end [f,g]=mengte(x2); if sum(g<=0)==4 if p0<=f x0=x2;p0=f; end end
end x0,p0

5. Solution of 0-1 integer programming

For example, solve this assignment problem.

Figure 5 Assignment problem

Since there are encapsulated functions in MATLAB - -, I don't need to write it in C++. . However, this question is still easy to write, and some competition questions will also appear.

c=[3,8,2,10,3; 8,7,2,9,7; 6,4,2,7,5; 8,4,2,3,5; 9,10,6,9,10] c=c(:);% becomes a column vector (method of extracting matrix)
a=zeros(10,25);
for i=1:5 a(i,(i-1)*5+1:1:5*i)=1; a(5+i,i:5:25)=1;
end
b=ones(10,1);
[x,y]=bintprog(c,[],[],a,b);
x=reshape(x,[5,5]),y