Looking for a code in Matlab optimization

Question

Benson Gou 2019-10-30

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/488359-looking-for-a-code-in-matlab-optimization

评论： Benson Gou 2019-11-18

采纳的回答： John D'Errico

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

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

John D'Errico 2019-10-30

2
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/488359-looking-for-a-code-in-matlab-optimization#answer_398999

编辑：John D'Errico 2019-10-30

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...

https://math.stackexchange.com/questions/1639716/how-can-l-1-norm-minimization-with-linear-equality-constraints-basis-pu

10 个评论
显示 8更早的评论隐藏 8更早的评论

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?

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

Thanks, John and Matt. I define the objective function as J = w_x*sum(x) + w_s*sum(s). In order to leave only s in the objective and at the same time add the integer contraint on x, I set w_x=0 when using intlinprog.m. It now works. Thanks a lot for your great hekp.

请先登录，再进行评论。