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

Answer 1

[John D'Errico]

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

[Benson Gou]

Hello, John,

Thanks for your great help. I read your suggestions carefuly but I found my formulation is not Basis Pursuit problem, in another word, my objective fuction is f = ||A*x - b||_1, but in Basis Prusuit, the objective function is f = ||x||_1. In addition, in my constraints I do not want to make A*x = b, i.e. I am looking for an integer variable x so that ||A*x - b||_1 is minimized.

Anyway, your great help is highly appreciated.

Best regards,

Benson

[John D'Errico]

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?

[Matt J]

Attached is a simple adaptation of my File Exchange submission,

https://www.mathworks.com/matlabcentral/fileexchange/52795-minl1lin

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]

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]

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]

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]

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]

Because my goal is to solve for the integer variable x, that is why I added x in the objective function. If I do not add it, what solution of x could be? I am very sorry, I am not quite clear.

Thanks a lot.

Benson

[John D'Errico]

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]

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.