Minimize number of nonzero entries
AnsweredHi,
i try to minimize the number of non zero entries in a vector and got stuck on the implementation.
Matrix H is m x n
Vector c is n x 1 (should be a vector with nonzero entries)
Vector a is m x 1
min ||a||_0 = min||H*c||_0
s.t. H[i]*c = 1 for a give i
How can i formulate the objective function?
m = gp.Model("vector optimiztation")
n_messwert = 6
n_zustand = 4
H = np.array([[1, 0, 3, 0],
[2, 4, 0, 2],
[0, 0, 1, 0],
[5, 0, 2, 3],
[2, 5, 2, 0],
[2, 4, 0, 1]])
alpha = m.addVar()
c = m.addMVar(n_zustand)
a = m.addMVar(n_messwert)
m.addConstr(H[2]@c == 1)
m.addConstr(H[2]@c == a[2])
m.addConstr(a == H@c)
m.setObjective(a, GRB.MINIMIZE)
m.optimize()-
Official comment
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
-
-
Hi Christoph,
Since you are trying to compute a norm and only need access to specific rows of the matrix, it might be easier to use the standard Python API. A possible code would be
import gurobipy as gp
from gurobipy import GRB
m = gp.Model("vector optimization")
n_messwert = 6
n_zustand = 4
H = np.array([[1, 0, 3, 0],
[2, 4, 0, 2],
[0, 0, 1, 0],
[5, 0, 2, 3],
[2, 5, 2, 0],
[2, 4, 0, 1]])
alpha = m.addVar()
c = m.addVars(n_zustand, name="c")
a = m.addVars(n_messwert, name="a")
m.addConstr( gp.quicksum(H[2][j]*c[j] for j in range(n_zustand) ) == 1)
m.addConstr( gp.quicksum(H[2][j]*c[j] for j in range(n_zustand) ) == a[2])
m.addConstr( gp.quicksum(a[i] for i in range(n_messwert)) ==
gp.quicksum( gp.quicksum( H[i][j]*c[j] for j in range(n_zustand)) for i in range(n_messwert) ) )
m.setObjective(gp.quicksum(a[i] for i in range(n_messwert)), GRB.MINIMIZE)
m.write("myLP.lp")
m.optimize()I used the write() function to write an LP file and check whether the created model looks as expected. Since you are interested in the \(l_0\), the easiest way would be to set all non-zero entries of your matrix \(H\) to 1 and use binary variables for your variables \(a\) and \(c\).
Best regards,
Jaromił0 -
-
Hi Jaromił,
The possible code using the Python API looks great.
variable a has to be a linear combination of H and I need it for further use. So i can not switch up H.
Can i weight the elements like:*
m.setObjective(gp.quicksum(9999*a[i] for i in range(n_messwert)), GRB.MINIMIZE)
Will the optimization try to get much zero entries since 9999*0=0 and non zero entries gets very big?
0 -
-
-
HI Christoph,
A big M approach might work but can lead to nasty numerics and can be hard to debug. An alternative might be to add only \(\neq 0\) entries during constraint construction. A possible code would be
m.addConstr( gp.quicksum( c[j] for j in range(n_zustand) if H[2][j]!=0 ) == 1)
m.addConstr( gp.quicksum( c[j] for j in range(n_zustand) if H[2][j]!=0 ) == a[2])
m.addConstr( gp.quicksum( a[i] for i in range(n_messwert)) ==
gp.quicksum( gp.quicksum( c[j] for j in range(n_zustand) if H[i][j]!=0 ) for i in range(n_messwert) ) )This way, you still keep your matrix \(H\) and the entries of the matrix don't affect the constraints.
Best regards,
Jaromił0 -
-
Hi Jaromił,
try to implement your ideas in my project but i get an unsolveable/ unbounded problem.
In my project matrix H is 142x55 and includes elements < 0 too.
Even for a & c the lower bound is lb = -GRB.INFINITY so the can get values <0 too.
Is it still usefull and possible get use of quicksum() under these conditions?
0 -
-
-
Hi Christoph,
I don't understand how the negative coefficients affect the solution process, because in my suggestion they are not used except when checking whether they are \(\neq 0\). You could compute the unbounded ray to check which direction is unbounded by making your problem continuous and setting the InfUnbdInfo parameter. You can access the unbounded ray via the UnbdRay attribute.
Best regards,
Jaromił0 -
Post is closed for comments.
Comments
6 comments