CVXPY optimization problem. DCPError: Problem does not follow DCP rules

0
votes

enter image description here We have the constraints set up very well and now are looking at the objective function of the partner preference problem right now. We can construct a 20x20 symmetric matrix of the worker to worker, each element being the combined score between two workers. however, the matrix is not positive semidefinite and we can not progress any further. We are using cvxpy python package. Please help!

Piece of code to clarify:

part_pref = pd.read_excel('Preferred Partners Updated.xlsx')
part_pref_np = np.array(part_pref)[:,1:21] # 20x20 symmetric matrix with partner preference

y = cp.Variable((20, 4), integer = True)

objective = cp.Maximize(-cp.sum(y.T @ part_pref_np @ y))

constraints = [y >= 0,
               y <= 1,
               cp.sum(y, axis = 1) == 1,
               cp.sum(y, axis = 0) >= b,
               cp.sum(y, axis = 0) <= c,
               (skill_np-d).T @ y >= e,
               cp.multiply((skill_np[:,2]-4),y[:,0]) >= 0,  
               cp.multiply((skill_np[:,0]-4),y[:,3]) >= 0,
               f @ x[:,0] >=1]
    
problem = cp.Problem(objective, constraints)
problem.solve()

raises error

DCPError: Problem does not follow DCP rules.

1
pythonmatrixoptimizationcvxpy

1 Answers

0
votes

I suspect the problem is in

cp.Maximize(-cp.sum(y.T @ part_pref_np @ y))

Can you try with

cp.Maximize(0)

and see what happens. I expect this will deliver a feasible solution.

CVXPY only allows convex quadratic objectives, and I think your objective is not convex (depends on the data so I cannot verify this). If so, you can linearize the objective as the decision variables are 0-1 variables. It is not so trivial however to do this in CVXPY as y is already a 2-dimensional variable (CVXPY only supports 0, 1 and 2-dimensional variables).

I am not completely sure why you are using a quadratic objective here. Maybe you can think about a linear one.