solving binary optimization problem

hey all

I am trying to solve below binary optimization problem , but i could not

max  1^T .z           
s.t. Bx >= z,        
and  Ax <= 1  
and  x∈{0,1} , z∈{0,1}  binary

where: :B is Known matrix with dimension [441*263], :A is known matrix with dimension [111*263], :x vector dimension [263*1], :z vector dimension [441*1]

thanks :)

[rahul shankar]

my optimisation function is of type,i dont know how to solve it min (x1+x2+x3+x4+x5+x6+x7) st: x2+2*x3+2*x4+x5+x6+x7>=1 2*x2+2*x3+x4+2*x6>=1 x3+2*x4+2*x5+x7>=1 x2+x3+2*x4+x5+2*x7>=1 all xi={0,1} please any one help me.

Answer 1

[Alan Weiss]

I think you have not yet translated your code into the form that bintprog expects. You are doing a maximization problem. bintprog solves minimization problems. So you have to take the negative of your objective vector:

 f_to_be_optimized = -1*ones(704,1);

And are you aure that you want all 704 components equal to -1? I thought that you just wanted the "z" components to equal -1.

 f_to_be_optimized(442:end) = 0;

And you can be more efficient in your generation of b_in_optimization_problem:

 b_in_optimization_problem = zeros(441,1);

Alan Weiss

MATLAB mathematical toolbox documentation

[Ayham]

Thanks a lot Alan for your replay actually the t vector still zeros, i am not sure why, please see below full code:

if true
B=round(rand(441,263));
Iz=eye(441); % Iz identity matrix refer to z part
BB=[B,Iz] ;
f_to_be_optimized = -1*ones(704,1); %-1 because of maximization
f_to_be_optimized(442:end) = 0;
b_in_optimization_problem = zeros(441,1);
t = bintprog(f_to_be_optimized,BB,b_in_optimization_problem)
  % code
end

please help

[Ayham]

hi Alan

please could u help here

[Alan Weiss]

Please check your problem formulation.

• Do you have a consistent representation of the t vector? I suspect not, because it seems you want the "z" components to be in the "f" vector, but you have the first components (the "x" components) multiply the B matrix.
• Did you translate your constraints to the BB matrix properly? I suspect not, because the multiplier BB of t should be [I,-B], and I do not see a negative sign in your BB matrix

Alan Weiss

MATLAB mathematical toolbox documentation

Answer 2

[Alan Weiss]

I am not sure that I understand your problem setup. Is x a binary variable, or is it continuous?

If x is binary, then I believe that you can transform your problem into one that the Optimization Toolbox solver bintprog can address. Set your vector of unknowns as

 t = [x;z];

and reformulate your problem to solver for the t variable. See this example.

Alan Weiss

MATLAB mathematical toolbox documentation

[Ayham]

thanks Alan

yes x and z are binary vectors

its good hint to transform x and z to > t = [x;z];

but the problem here still i have 2 linear inequalities constraint not one: s.t. Bx >= z, and Ax <= 1

[Alan Weiss]

You have to rewrite your problem in the form that bintprog accepts. For example,

 Bx >= z

can be rewritten

 z - Bx <= 0

This is in the form that bintprog accepts. Of course, you have to write it as an inequality in the t variable, something like

 BB t <= 0

where you make BB out of the B matrix for the x part and an identity matrix for the z part.

Alan Weiss

MATLAB mathematical toolbox documentation

[Ayham]

Thanks Alan

your replay was so helpful

actually i did as you mentioned, but i get t vector will all zeros so i think there is something missing, below the code which i ran:

Iz=eye(441); % Iz identity matrix refer to z part
BB=[B,Iz] ; % B is binary matrix with [441*263] dimension 

for i=1:704

      f_to_be_optimized(i)=1;
  end

for i=1:441      

      b_in_optimization_problem(i)=0;
  end

b_in_optimization_problem=b_in_optimization_problem';

t = bintprog(-f_to_be_optimized,BB,b_in_optimization_problem)

thanks for your help