[integer programming]

Definition of integer programming

Variables in mathematical programming （ In part or in whole ） When restricted to integers , It's called integer programming . If in the linear programming model , Variables are limited to integers , It is called integer linear programming .

A method for solving integer linear programming

Branch and bound —— Computable pure or mixed integer linear programming .

Cutting plane method —— Computable pure or mixed integer linear programming .

Implicit enumeration —— solve “0-1” Integer programming

1. Filter implicit enumeration .
2. Branch implicit enumeration .

Hungarian law —— Solve assignment problems （0-1 Planning special situations ）

Monte Carlo method —— Solve various types of programming .

Use matlab

clc,clear
x=unifrnd(0,12,[1,10000000]);
y=unifrnd(0,9,[1,10000000]);
pinshu=sum(y<x.^2&x<=3)+sum(y<12-x&x>=3);
area_appr=12*9*pinshu/10^7

function[f,g]=mengte(x);
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];

rand('state',sum(clock))% Initialize the random number generator 
p0=0;
tic% Timing begins 
for i=1:10^6
    x=randi([0,99],1,5);
    [f,g]=mengte(x);
    if all(g<=0)
        if p0<f
            x0=x;p0=f;% Record the current better solution 
        end
    end
end
x0,p0
toc

Use lingo

Locally optimal solution

The book says that you can directly find the exact global optimal solution , But when I type in the code and run it, the result is a local optimal solution , Also make changes to its rows and columns , Discovery or local optimal solution , Not the global optimal solution .

Global optimal solution

lingo->options->Global Solver
On the hook Use Global Options, application