Non-Linear Objective Function with Linear Constraints Case
AnsweredHi,
Previously in this post, I have a quadratic as the objective function with linear constraints. Now, I want to extend the problem by having the objective function as Nonlinear, where the formulation changes to
\(minimize\) \(\max\{0, \sum_{j = 1}^m (room\_size[j] - (\sum_{i=1}^n people\_size[i] x_{ij})\}\)
Given the constraints subject to
\(\sum_{i=1}^n x_{ij} >= 1\) for all \(j = 1, ..., m\) indicate I want to assign a room that more than 1 person can fill
\(\sum_{j=1}^m x_{ij} >= 1\) for all \(i = 1, ..., n\) indicate a person only enter 1 room.
with \(x_{ij}\) is Binary.
Since my obj function is nonlinear, I changed the formulation above into
\(minimize\) p
Given the constraints subject to:
p >= 0
p >= \(\sum_{j = 1}^m (room_size[j] - (\sum_{i=1}^n people_size[i] x_{ij}))\)
\(\sum_{i=1}^n x_{ij} >= 1\) for all \(j = 1, ..., m\) indicate I want to assign a room that more than 1 person can fill
\(\sum_{j=1}^m x_{ij} >= 1\) for all \(i = 1, ..., n\) indicate a person only enter 1 room.
with \(x_{ij}\) is Binary.
Then, I put the formulation into a code (below)
import numpy as np
import gurobipy as gp
from gurobipy import GRB
# Initial condition
people_size = np.array([18., 15., 11., 9., 14., 13.])
room_size = [60., 64.50, 54.50]
N = len(people_size) # number of people
M = len(room_size) # number of room
assignment_matrix = np.zeros((N, M)) # put the assignment matrix
model = gp.Model("NL_General_Assignment_Problem")
# Create the decision variable the x_ij
x_ij = model.addVars(N, M, vtype = GRB.BINARY, name = 'x_ij')
# Create constraints
model.addConstrs((gp.quicksum(x_ij[i,j] for i in range(N)) >= 1) for j in range(M))
model.addConstrs((gp.quicksum(x_ij[i,j] for j in range(M)) == 1) for i in range(N))
# Constraints with max(0, objective function)
aux1 = model.addVars(M)
aux2 = model.addVars(M)
for j in range(M):
model.addConstr(aux1[j] == room_size[j] - gp.quicksum(people_size[i] * x_ij[i, j] for i in range(N)))
model.addGenConstrMax(aux2[j], [aux1[j]], 0.0)
model.setObjective(gp.quicksum(aux2[j] for j in range(M)), sense = GRB.MINIMIZE)
# Find the optimal solution
model.optimize()
model.write("people_assignment.lp")
# Create the assignment matrix
assignment_matrix = np.zeros((N, M))
for i in range(N):
for j in range(M):
if x_ij[i, j].x == 1:
assignment_matrix[i, j] = x_ij[i, j].x
print(assignment_matrix)
Then, my questions will be:
1. Do the Formulation I put before the code is correct?
2. Is the Gurobi implementation on the code above correct?
What makes me curious is the formulation above I have p >= 0 and x_ij as binary. Can I convert p and x_ij into a continuous variable, say z \in [0, 1]? If I can, how do I do that?
Thank you
-
is it okay for me to up this question?
0 -
-
-
Gurobi Staff
Hi Muhamad,
At a first glance your implementation looks correct except that in one linear constraint you have \(\geq\) and in the second \(=\) but you have \(\geq\) twice in the model formulation.
What you should do to double check is to check the model you wrote to the file \(\texttt{people_assignment.lp}\). For this, you should always provide unique constraint and variable names. Then, when the model solves, you should also check whether the optimal solution makes sense. If possible, you should try different data sets to verify that your model does what you want.
What makes me curious is the formulation above I have p >= 0 and x_ij as binary. Can I convert p and x_ij into a continuous variable, say z \in [0, 1]? If I can, how do I do that?
You can only convert x_ij to a continuous variable if you know that the solution of the continuous relaxation is an integer point, which is not trivial to prove and quite rare. You could just try and see what happens.
Best regards,
Jaromił0 -
-
Hi Jaromil
Thank you for pointing out the mistake. I mistakenly wrote the constraints in the formulation. The one in the code was the correct one. Regarding the model in the .lp file, is the content something like below or includes other information?
\ Model NLP_General_Assignment_Problem
\ LP format - for model browsing. Use MPS format to capture full model detail.
Minimize
C21 + C22 + C23
Subject To
R0: x_ij[0,0] + x_ij[1,0] + x_ij[2,0] + x_ij[3,0] + x_ij[4,0] + x_ij[5,0]
>= 1
R1: x_ij[0,1] + x_ij[1,1] + x_ij[2,1] + x_ij[3,1] + x_ij[4,1] + x_ij[5,1]
>= 1
R2: x_ij[0,2] + x_ij[1,2] + x_ij[2,2] + x_ij[3,2] + x_ij[4,2] + x_ij[5,2]
>= 1
R3: x_ij[0,0] + x_ij[0,1] + x_ij[0,2] = 1
R4: x_ij[1,0] + x_ij[1,1] + x_ij[1,2] = 1
R5: x_ij[2,0] + x_ij[2,1] + x_ij[2,2] = 1
R6: x_ij[3,0] + x_ij[3,1] + x_ij[3,2] = 1
R7: x_ij[4,0] + x_ij[4,1] + x_ij[4,2] = 1
R8: x_ij[5,0] + x_ij[5,1] + x_ij[5,2] = 1
R9: 18 x_ij[0,0] + 15 x_ij[1,0] + 11 x_ij[2,0] + 9 x_ij[3,0]
+ 14 x_ij[4,0] + 13 x_ij[5,0] + C18 = 60
R10: 18 x_ij[0,1] + 15 x_ij[1,1] + 11 x_ij[2,1] + 9 x_ij[3,1]
+ 14 x_ij[4,1] + 13 x_ij[5,1] + C19 = 64.5
R11: 18 x_ij[0,2] + 15 x_ij[1,2] + 11 x_ij[2,2] + 9 x_ij[3,2]
+ 14 x_ij[4,2] + 13 x_ij[5,2] + C20 = 54.5
Bounds
Binaries
x_ij[0,0] x_ij[0,1] x_ij[0,2] x_ij[1,0] x_ij[1,1] x_ij[1,2] x_ij[2,0]
x_ij[2,1] x_ij[2,2] x_ij[3,0] x_ij[3,1] x_ij[3,2] x_ij[4,0] x_ij[4,1]
x_ij[4,2] x_ij[5,0] x_ij[5,1] x_ij[5,2]
General Constraints
GC0: C21 = MAX ( C18 , 0 )
GC1: C22 = MAX ( C19 , 0 )
GC2: C23 = MAX ( C20 , 0 )
EndYou can only convert x_ij to a continuous variable if you know that the solution of the continuous relaxation is an integer point, which is not trivial to prove and quite rare. You could just try and see what happens.
Let's assume the constraints
\(\sum_{i=1}^n x_{ij} >= 1\) for all \(j = 1, ..., m\)
\(\sum_{j=1}^m x_{ij} = 1\) for all \(i = 1, ..., n\)
hold something related to totally unimodular property. If somehow the objective function is nonlinear and there is an additional variable, the room size and people size are kept to have no integer result. Do you think, it would make sense that the solution is still in an integer point?
Also, I found there were MILP tricks for instance if there is a binary variable (in my case is x_ij) and a continuous variable (in my case is p after assuming p has M). We can apply reformulation that makes a combination of it. Let's have the z variable as (x_ij * p), then,
z >= 0
z <= M x_ij
z <= p
z >= p - (1 - x_ij) M
and add those constraints in the code, do you think it would make sense?
Thank you0 -
-
-
Regarding the model in the .lp file, is the content something like below or includes other information?
Yes, this is the model you should check. As you can see, the variables and constraints have some default names. To avoid this, you should provide unique names to all your variables and constraints. This makes analyzing an LP file way easier.
If somehow the objective function is nonlinear and there is an additional variable, the room size and people size are kept to have no integer result. Do you think, it would make sense that the solution is still in an integer point?
I don't know. Thus, I proposed that you just relax the integrality to see what happens. It is best to do this for multiple data sets and not just one. If the optimal solution is not integral, then you easily disproved your conjecture.
Also, I found there were MILP tricks for instance if there is a binary variable (in my case is x_ij) and a continuous variable (in my case is p after assuming p has M). We can apply reformulation that makes a combination of it. Let's have the z variable as (x_ij * p), then,
Gurobi performs this reformulation automatically. It is only profitable to do this reformulation by hand if you can provide a very tight bigM which would equal to tightening bounds of p.
Best regards,
Jaromił0 -
-
Hi Jaromil,
Thank you for the insight. So far I understand the answer from me. It helps me a lot in understanding my learning
0 -
Please sign in to leave a comment.
Comments
5 comments