Can I apply branch and bound and use linprog function to minimize a function? if there is an example please share it

I have to use linprog For branch and

bound optimization

[Matt J]

Not linprog. You would want intlinprog (which does use branch-and-bound).

[Torsten]

Well, you do not expect that we code branch-and-bound in combination with linprog for you, do you ?

Answer 1

[Matt J]

Add additional binary variables b1,b2 and equality constraints as below. Then it becomes a straightforward application of intlinprog.

x=optimvar('x',7);

b1=optimvar('b',[2,4],'Type','integer','Lower',0,'Upper',1);
b2=optimvar('c',[2,3],'Type','integer','Lower',0,'Upper',1);

Constraints.x1x2= [x(1);x(2)]==b1*[2,5,7,8]';
Constraints.x3x4= [x(3);x(4)]==b2*[3,4,6]';
Constraints.b1= sum(b1,2)==1;
Constraints.b2= sum(b2,2)==1;
...
other constraints
...

prob=optimproblem('Objective',___,'Constraints', Constraints);

sol=solve(prob,'Solver','intlinprog')

[Matt J]

If you are not familiar with the problem-based optimization framework, then you will find a starter example here,

https://www.mathworks.com/help/optim/ug/problem-based-workflow.html