Optimization problem: CVXPY Problem does not follow DCP rules

132 views Asked by At

I'm trying to minimize the number of warehouses needed to serve a specific number of customers (whose locations are known) using CVXPY.

import numpy as np
import math
import networkx as nx
import cvxpy as cvx

customer = np.array([[9.23832006,6.69815259], [6.86143781,8.00793126], [1.88446383,3.18609488], [9.37633395,0.95052868], [9.65147217,1.18788532], [9.73841699,4.59025871], [1.91812923,0.58647245], [4.21276711,1.54069302], [3.79746489,6.06997667], [4.91810797,0.88371757], [1.42219028,2.39434242], [4.15910699,2.66411967], [6.34420357,2.66060155], [9.3074639,6.57377939], [4.2108558,5.73567056]])
customer_num=customer.size/2
dc_num=10
x_min=min(customer[:,0])
x_max=max(customer[:,0])
y_min=min(customer[:,1])
y_max=max(customer[:,1])
maxxy=max(x_max,y_max)
M=maxxy**2
max_dist=6
covered_customers=math.ceil(customer_num)


print ("------ START MODEL 1 ------")
#Model 1 : Minimize number of warehouses

###Variable
dc={}
x={}
y={}
assign={}
n=0

for j in range(dc_num):
  dc[j]=cvx.Variable(value=1, boolean=True, name="DC%d" %j)
  x[j]=cvx.Variable (integer=True, name="x%d" % j)
  y[j]=cvx.Variable(integer=True, name="y%d" % j)

for i in range(len(customer)):
    for j in range(len(dc)):
        assign[(i,j)] = cvx.Variable(value=1,boolean=True, name="Cu%d from DC%d" % (i,j))

constraints=[]

for i in range(len(customer)):
    for j in range(len(dc)):
      constraints += [((customer[i][0] - x[j])*(customer[i][0] - x[j]) + (customer[i][1] - y[j])*(customer[i][1] - y[j])) <= max_dist*max_dist + M*(1-assign[(i,j)])]

for i in range(len(customer)):
  constraints += [sum(assign[(i,j)] for j in range(len(dc))) <= 1]

for i in range(len(customer)):
    for j in range(len(dc)):
      constraints += [assign[(i, j)] <= dc[j]]

for j in range(dc_num-1):
    constraints += [(dc[j] >= dc[j+1])]

constraints += [sum(assign[(i,j)] for i in range(len(customer)) for j in range(len(dc))) >= covered_customers]

n=sum(cvx.entr(dc[j]) for j in dc)


obj=cvx.Minimize(n)

prob = cvx.Problem(obj, constraints)
res=prob.solve()

But I get the following error:

DCPError: Problem does not follow DCP rules. Specifically: The objective is not DCP, even though each sub-expression is. You are trying to minimize a function that is concave.

If I understood it correctly, the algorithm is not working because the objective funcion and the constraints of my problem are given by moltiplications of DCP element. How can I solve the problem?

Thanks in advice.

0

There are 0 answers