Skip to main content

Please help with this program

Answered
Vamsi Krishna
Gurobi-versary
First Comment
First Question

Let's say a line network with nodes at M =[0,4,8,15] (say on X-axis ), 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[m-1]
    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[m-1] <= 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

1

Comments

3 comments

Date Votes
  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    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 x-variables 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 left-hand side of those constraints can only be -1, 0, or 1. Maybe you need a different way to describe the distance.

    Best regards,
    Mario

    1
  • Vamsi Krishna
    Gurobi-versary
    First Comment
    First Question

    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 gp
    from 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
  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    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.

Didn't find what you were looking for?

New post