Looking for a code in Matlab optimization
显示 更早的评论
Dear All,
I do not know if a code exists in Matlab optimization for the following integer linear programming.
Min ||A*x - b||_1
S.T. x is an integer variable, x>= 0 and x <= 1. A is a 1 x n row vector, and b is a scalar.
Thanks a lot.
Benson
采纳的回答
John D'Errico
2019-10-30
编辑：John D'Errico
2019-10-30
2 个投票
No. There is no direct code to do so, at least not that I know of. Should I write it? sigh.
But if you spend some time reading, you will find this is just a binary integer linear programming problem. That is...
A 1-norm minimization of that form can be converted into a standard LP problem using slack variables. (Its been many years since I wrote code for that, but I recall doing so.) At that point, it becomes a simple call to intlinprog.
A quick search shows the way...
10 个评论
Benson Gou
2019-10-30
John D'Errico
2019-10-30
编辑：John D'Errico
2019-10-30
I understand. But you apparently do not. The difference is trivial. I never said that I thought you wanted to constrain A*x==b.
You will still create a set of slack variables, call them s_i, one for each element of the vector A*x - b. So you will have
A(1,:)*x - b(1) <= s_1
AND
-(A(1,:)*x - b(1)) <= s_1
Do the same for each row of A, so if A has n rows, then you will create 2*n such linear inequality constraints.
We have now a problem with a vector of unknowns x AND a vector of unknowns s. The LP solver will see only one vector of course, but you need to create the problem with the two vectors of unknowns combined into one vector.
The problem is larger, because of the slack variables, and only the vector x is held to be binary [0,1] integer. The vector s is constrained to have a lower bound of all zeros, with no upper bound.
So if the matrix A is of size n by m, then the new problem has n+m unknowns.
The objective function for the LP is simply to minimize the sum of the vector s.
When the LP solver (intlinprog is necessary here, because it will allow you to specify a subset of the variables as [0,1] integer variables) has finished the solution, you discard the slack variables, as they were introduced only to convert the L1 norm into a classical LP form.
Do you now understand?
Attached is a simple adaptation of my File Exchange submission,
that implements what John has described. Simply run as,
[x,resnormL1] =
minL1intlin(A,b,intcon, [],[],[],[],zeros(N,1),ones(N,1),x0,options);
John D'Errico
2019-10-30
Great! I did not know there was a tool on the FEX. And you can trust code written by Matt, as he does know what he is doing.
Matt J
2019-10-30
John is very kind, but I guess I should have mentioned that I haven't had a chance to test the modification. It is literally a 2-line change though.
Matt J
2019-10-31
Benson's comment moved here:
Dear John and Matt,
Thanks a lot for your great help.
I followed the instruction of John and found it works. The objective function is sum(x) + sum(s_i). If I do not use weights for both variables, I got null solution for x. So I added weight on s_i so that x becomes non-zero. The new objective function becomes sum(x) + 100*sum(s_i). It works after I added the weight.
Do you have a better approach than what I did? Thanks a lot again.
Best regards,
Benson
Matt J
2019-10-31
I followed the instruction of John and found it works. The objective function is sum(x) + sum(s_i).
No, John told you that the objective should be sum(s_i) and that is what my code implements as well. It is not clear why you have added the sum(x) term.
Benson Gou
2019-11-1
编辑：Benson Gou
2019-11-3
John D'Errico
2019-11-4
编辑：John D'Errico
2019-11-4
Adding x to the objective function means you will get the wrong answer. We told you how to solve it. The objective function includes ONLY the slack variables. You cannot just make the objective function anything you want and have it be correct.
Or, far betteryet, just use Matt's code, as writing code to do somethign for which well written code already exists is just a bad idea. Unless of course, you already completely understand the problem, and how to solve it, AND you have considerable expertise in coding. You have none of that, so it is far better to use Matt's code.
Benson Gou
2019-11-18
更多回答（0 个）
类别
在 帮助中心 和 File Exchange 中查找有关 Solver Outputs and Iterative Display 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Translated by 
