solving binary optimization problem
7 views (last 30 days)
Show older comments
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
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.
Accepted Answer
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
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
More Answers (1)
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];
Alan Weiss
MATLAB mathematical toolbox documentation
3 Comments
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
See Also
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!