solving binary optimization problem

7 views (last 30 days)
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 :)
  1 Comment
rahul shankar
rahul shankar on 30 Oct 2015
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.

Sign in to comment.

Accepted Answer

Alan Weiss
Alan Weiss on 9 May 2013
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
  3 Comments
Ayham
Ayham on 10 May 2013
hi Alan
please could u help here
Alan Weiss
Alan Weiss on 10 May 2013
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

Sign in to comment.

More Answers (1)

Alan Weiss
Alan Weiss on 9 May 2013
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
  3 Comments
Alan Weiss
Alan Weiss on 9 May 2013
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
Ayham on 9 May 2013
Edited: Ayham on 9 May 2013
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

Sign in to comment.

Categories

Find more on Solver-Based Optimization Problem Setup in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!