Please help with this program
AnsweredLet's say a line network with nodes at M =[0,4,8,15] (say on Xaxis ), and r =7, m=2. I want to place m points on this line network
Objective:
To maximize the number of points out of m to be placed on the line network in such a way that they coincide with nodes from M
Constraints:
none of the points should be placed on either first and last elements of M
When placing points the distance between the adjacent points should be less than or equal to r (that is 7 in this case)
distance between first point and M[0] line network should be less than or equal to r
distance between last point and M[len(M)1] line network should be less than or equal to r
maximum 1 point can placed on each node of M
A single point cannot be assigned to multiple nodes of M
code:
import gurobipy as gp
from gurobipy import GRB
# Given data
M = [0, 4, 8, 15]
R = 7
m = 2
# Create a Gurobi model
model = gp.Model('Point_Placement')
# Create decision variables
x = {}
for i in range(m):
for j in range(len(M)  1): # Adjusted index range to include all points in M
x[i, j] = model.addVar(vtype=GRB.BINARY, name=f'x_{i}_{j}')
# Set objective to maximize the number of points placed on M
model.setObjective(gp.quicksum(x[i, j] for i in range(m) for j in range(len(M)  1)), sense=GRB.MAXIMIZE)
# Add constraints
for i in range(m):
# Constraint: Maximum 1 point on each M except M[0] and M[m1]
model.addConstr(gp.quicksum(x[i, j] for j in range(1, len(M)  1)) <= 1, name=f'constraint_max_1_{i}')
# Constraint: Ensure distance between adjacent points <= R
for i in range(m):
for j in range(len(M)  2):
model.addConstr(x[i, j]  x[i, j + 1] <= R, name=f'constraint_dist_{i}_{j}')
# Constraint: Distance between first point and M[0] <= R
for j in range(m):
model.addConstr(x[j, 1] <= R, name=f'constraint_first_point_{j}')
# Constraint: Distance between last point and M[m1] <= R
for j in range(m):
model.addConstr(x[j, len(M)  2] <= R, name=f'constraint_last_point_{j}')
# Constraint: Only one point per position on the line network
for j in range(1, len(M)  1):
model.addConstr(gp.quicksum(x[i, j] for i in range(m)) <= 1, name=f'constraint_one_point_per_position_{j}')
# Update the model
model.update()
# Optimize the model
model.optimize()
# Print the optimal solution
if model.status == GRB.OPTIMAL:
print('Optimal solution found:')
print('Positions of selected points:')
for i in range(1, len(M)  1):
for j in range(m):
if x[j, i].X > 0.5: # Check if the variable is selected (threshold = 0.5 for binary)
print(f'Point {j+1} should be placed at position {M[i]} on the line network.')
else:
print('No solution found.')
Point 1 should be placed at position 4 on the line network. Point 2 should be placed at position 8 on the line network.
The answer is correct for the above data , but giving the same output for
any other data. please help

Hi Vamsi,
Are you saying that the solution for the shown code and model is correct but for different input data you get the same solution? This sounds weird.
We recommend writing the formulated model to an LP file with model.write("model.lp") immediately before optimize(). Then, for small instances, you can manually check if the constraints are correctly built.
What seems strange to me is that xvariables are binary but they are used without some kind of distance coefficient in the distance constraints:
x[i, j]  x[i, j + 1] <= R
Note that the value of those variables can only be 0 or 1, so the lefthand side of those constraints can only be 1, 0, or 1. Maybe you need a different way to describe the distance.
Best regards,
Mario1 
Hi Mario,
Thanks for the suggestions.
Yes, wrong formulation of distance constraint.I have defined one more continuous variable that tries to capture this. Here is the updated code.
import gurobipy as gpfrom gurobipy import GRB
# Given data
M = [0, 4, 8, 15]
R = 7
m = 2
# Create a Gurobi model
model = gp.Model('Point_Mapping')
# Create decision variables
c = {}
x = {}
for i in range(1, len(M)  1):
for j in range(m):
c[j] = model.addVar(lb=GRB.INFINITY, vtype=GRB.CONTINUOUS, name=f'c_{j}')
x[i, j] = model.addVar(vtype=GRB.BINARY, name=f'x_{j}_{i}')
# Set objective to maximize the sum of x_ij
model.setObjective(gp.quicksum(x[i, j] for i in range(1, len(M)  1) for j in range(m) ), sense=GRB.MAXIMIZE)
# Add constraints at each node of M, the maximum points that can be placed is 1
for i in range(1,len(M)1):
model.addConstr(gp.quicksum(x[i, j] for j in range(m)) <= 1, name='Max_one_CS_cosntraint')
# Add point constraints
model.addConstr(c[0]  M[0] >= 0.1, name='constraint_c1_m0')
model.addConstr(c[0]  M[0] <= R, name='constraint_c1_m0_R')
model.addConstr(M[1]  c[m  1] <= R, name='constraint_mnplus1_cm')
model.addConstr(M[1]  c[m  1] >= 0.1, name='constraint_mnplus1_cm_R')
for j in range(m  1):
model.addConstr(c[j + 1]  c[j] <= R, name=f'constraint_c{j + 1}_cj')
# Create additional binary variables for indicator constraints
z = {}
for i in range(1, len(M)  1):
for j in range(m):
z[i, j] = model.addVar(vtype=GRB.BINARY, name=f"z_{i}_{j}")
# Indicator constraints for c[j] = M[i] implies z[i, j] = 1
for i in range(1, len(M)  1):
for j in range(m):
model.addConstr(c[j]  M[i] == 0 >> z[i, j] == 1, name=f"indicator_constraint_cj_mi_{i}_{j}")
# Indicator constraints for c[j] != M[i] implies z[i, j] = 0
model.addConstr(c[j]  M[i] != 0 >> z[i, j] == 0, name=f"indicator_constraint_cj_not_mi_{i}_{j}")
# Link z variables to x variables
for i in range(1, len(M)  1):
for j in range(m):
model.addConstr(z[i, j] == x[i, j], name=f"link_z_to_x_{i}_{j}")
# Update the model
model.update()
model.write('model.lp')
# Optimize the model
model.optimize()
# Print the optimal solution
if model.status == GRB.OPTIMAL:
print('Optimal solution found:')
for j in range(m):
print(f'c_{j} = {c[j].X}')
for i in range(1, len(M)  1):
for j in range(m):
print(f'x_{i}_{j} = {x[i, j].X}')
else:
print('No solution found.')I think I made some mistake in adding indicator constraint. I am getting the following error. Could you help?line 48, in <module>
model.addConstr(c[j]  M[i] == 0 >> z[i, j] == 1, name=f"indicator_constraint_cj_mi_{i}_{j}")
TypeError: unsupported operand type(s) for >>: 'int' and 'Var'0 
See the documentation of the indicator constraint: IF some binary variable is 1 (or 0) THEN some constraint must hold.
Your case is different: IF some constraint holds THEN a binary variable is 1.0
Please sign in to leave a comment.
Comments
3 comments