Search code examples
pythondictionaryoptimizationconstraintspulp

Formulating equations in Pulp Python

I'm trying to formulate the following equations: 25, 28, 29, 30 & 31, with Pulp in Python using dictionaries that include LpVariable, with the objective to minimize the end to end latency of a transmission from one network node to node.

  • i index refers to a specific type of transmission flow
  • k index refers to a frame within a flow
  • Vx, Va, Vb are nodes in the network with this topology (Vx <--> Va <--> Vb)

Equations:

Currently I am figuring out how to set the 29th constraint so, in my mind it should look like:

model = LpProblem(name="ilp", sense=LpMinimize)
I = range(2)
K = range(4)

offsets = {i: LpVariable(name=f"offset_{i}", lowBound=lowBounds[i]) for i in I}

e2e_lat = {}
e2e_lat_lowBound = {}
for i in I:
    for k in K:
        e2e_lat[i] = offsets[i, k] + t_tx[i, k] - offsets[i, 1]
        e2e_lat_lowBound[i] = offsets[i, k].lowBound + t_tx[i, k]

for i in I:
    model += e2e_lat[i] == deadline[i]

#Objective
model += c2 * lpSum([e2e_lat[i] - e2e_lat_lowBound[i] for i in I])

Since I'm new to linear programming I have no clue to how it should be coded.

I would be really grateful for any help.

Solution

  • Taking into account the previously posted equations this is a possible solution:

    from pulp import LpMinimize, LpProblem, LpStatus, lpSum, LpVariable, PULP_CBC_CMD

# Variables (ms)
# I = num of flows, K = num of frames
I = range(3)
K = range(4)
periods = [1.1, 1.1, 5]
deadline = [10, 30, 80]
t_tx = [0.012, 0.008, 0.0024]
e2e_lat = {}
e2e_lat_lowBound = {}

model = LpProblem(name="ilp", sense=LpMinimize)
offsets = {i: {k: LpVariable(name=f"f_{i}{k}", lowBound=k*periods[i]) for k in K} for i in I}

# Equation 25 & 28(e2e & e2e_lowBound definitions):
for i in range(len(offsets)):
    for k in range(len(offsets[i])):
        e2e_lat[i] = offsets[i][k] - t_tx[i] - offsets[i][0]
        e2e_lat_lowBound[i] = offsets[i][k].lowBound + t_tx[i]
        
        print("e2e: {} = {} - {} - {}".format(e2e_lat[i], offsets[i][k], t_tx[i], offsets[i][0]))
        print("e2e_lb: {} = {} + {}".format(e2e_lat_lowBound[i], offsets[i][k].lowBound, t_tx[i]))

# Equation 29 (Deadline):
for i in I:
    model += e2e_lat[i] <= deadline[i]
    
    print("{} <= {}".format(e2e_lat[i], deadline[i]))

# Equation 30 (offset upperBound): 
for i in range(len(offsets)):
    for k in range(len(offsets[i])):
        model += offsets[i][k] <= ((k+1)*periods[i] - t_tx[i])
        
        print("{} <= {}*{} - {}".format(offsets[i][k], k+1,periods[i], t_tx[i]))

# Equation 26 (Objective Function): 
model += lpSum([e2e_lat[i] - e2e_lat_lowBound[i] for i in range(len(e2e_lat))])

    Since this equations reefer to a time resource allocation from a TSN scheduling problem I also needed to add the following equation to prevent 2 flows overlaps.

    for i in range(len(offsets)):
    for k in range(len(offsets[i])):
        if i+1 in I: 
            model += (k+1)*periods[i] + offsets[i][k] + t_tx[i] <= (k+1)*periods[i+1] + offsets[i+1][k]