CODEWITHSUNDEEP
pythonpulp
Aris
Aris

Reputation: 156

Linear modeling solver with set restrictions in pulp python

I have this integer linear modeling problem

xn = {0,1}

xn integer

max 12*x1+3*x2+4*x3+1*x4+23*x5+44*x6+55*x7+31*x8+4*x9+17*x10 

1000*x1+3000*x2+3500*x3+1200*x4+1023*x5+2044*x6+5050*x7+2100*x8+3500*x9+1700*x10 <= 10000

T1 = {x1,x2,x3} 
T2 = {x4} 
T3 = {x5,x6,x7,x8}
T4 = {x9,x10}

I need at least one element of 3 different T1,T2,T3,T4 sets

First two are easy to code with pulp in python

import pulp

#Constraints
P_UID = ['x1','x2','x3','x4','x5','x6','x7','x8','x9','x10']
P_Var = pulp.LpVariable.dicts("x", P_UID, lowBound = 0, upBound=1,  cat="Integer")

OptimizeCoef = [12,3,4,1,23,44,55,31,4,17]
OptimizeFunction =  pulp.LpAffineExpression([(P_Var[P_UID[i]],OptimizeCoef[i]) for i in range(len(P_UID))])


OverBoundCoef = [1000,3000,3500,1200,1023,2044,5050,2100,3500,1700]

OverBoundFunction = pulp.LpAffineExpression([(P_Var[P_UID[i]],OverBoundCoef[i]) for i in range(len(P_UID))])
OverBoundFunction = pulp.LpConstraint(e=OverBoundFunction,sense = pulp.LpConstraintLE, rhs=10000)


SelectionX = pulp.LpProblem('SelectionX', pulp.LpMaximize)

SelectionX += OptimizeFunction
SelectionX += OverBoundFunction


#Solvers
SelectionX.writeLP("SelectionPlayersModel.lp")

solver = pulp.solvers.PULP_CBC_CMD()
pulp.LpSolverDefault.msg = 1
SelectionX.solve(solver)

print (pulp.value(SelectionX.objective))

for v in SelectionX.variables():
    if v.varValue > 10e-4:
        print ( v.name, v.varValue)

I obtain next result with this code

139.0
x_x10 1.0
x_x5 1.0
x_x6 1.0
x_x7 1.0

But I don't know how to program set restrictions

Upvotes: 0

Views: 1138

Answers (2)

Aris
Aris

Reputation: 156

Thanks, that's a very good trick.

I changed "T" restrictions like that

T1-x1>=0
T1-x2>=0
T1-x3>=0

x1 + x2 + x3-T1>=0

...

I paste here all code

 import pulp

#Constraints
P_UID = ['x1','x2','x3','x4','x5','x6','x7','x8','x9','x10']
P_Var = pulp.LpVariable.dicts("x", P_UID, lowBound = 0, upBound=1,  cat="Integer")

T_UID = ['T1','T2','T3','T4']
T_Var = pulp.LpVariable.dicts("y", T_UID, lowBound = 0, upBound=1,  cat="Integer")

PinT = [[1,1,1,0,0,0,0,0,0,0],[0,0,0,1,0,0,0,0,0,0],[0,0,0,0,1,1,1,1,0,0],[0,0,0,0,0,0,0,0,1,1]]

OptimizeCoef = [12,3,4,1,23,44,55,31,4,17]
OptimizeFunction =  pulp.LpAffineExpression([(P_Var[P_UID[i]],OptimizeCoef[i]) for i in range(len(P_UID))])


OverBoundCoef = [1000,3000,3500,1200,1023,2044,5050,2100,3500,1700]

OverBoundFunction = pulp.LpAffineExpression([(P_Var[P_UID[i]],OverBoundCoef[i]) for i in range(len(P_UID))])
OverBoundFunction = pulp.LpConstraint(e=OverBoundFunction,sense = pulp.LpConstraintLE, rhs=10000)

PInTBound = []
PAllInTBound = []
TNum = 0
for T in T_UID:
    for p in range(len(P_UID)):
        if PinT[TNum][p]>0:
            PInTBoundTemp = pulp.LpAffineExpression(T_Var[T_UID[TNum]]-P_Var[P_UID[p]])
            PInTBoundTemp = pulp.LpConstraint(e=PInTBoundTemp,sense = pulp.LpConstraintGE, rhs=0)
            PInTBound.append(PInTBoundTemp)


    PAllInTBoundTemp =  pulp.LpAffineExpression([(P_Var[P_UID[i]],PinT[TNum][i]) for i in range(len(P_UID))])+\
                         pulp.LpAffineExpression(-T_Var[T_UID[TNum]])
    PAllInTBoundTemp =  pulp.LpConstraint(e=PAllInTBoundTemp,sense = pulp.LpConstraintGE, \
                                             rhs=0)
    PAllInTBound.append(PAllInTBoundTemp)

    TNum += 1


TBoundFunction = pulp.LpAffineExpression([(T_Var[T_UID[i]],1) for i in range(len(T_UID))])
TBoundFunction = pulp.LpConstraint(e=TBoundFunction,sense = pulp.LpConstraintGE, rhs=3)


SelectionX = pulp.LpProblem('SelectionX', pulp.LpMaximize)

SelectionX += OptimizeFunction
SelectionX += OverBoundFunction
SelectionX += TBoundFunction

for Bound in PAllInTBound:
    SelectionX += Bound

for Bound in PInTBound:
    SelectionX += Bound 

#Solvers
SelectionX.writeLP("SelectionXModel.lp")

solver = pulp.solvers.PULP_CBC_CMD()
pulp.LpSolverDefault.msg = 1
SelectionX.solve(solver)


print ('Maximized Value:', pulp.value(SelectionX.objective))
print(pulp.LpStatus[SelectionX.status])

for v in SelectionX.variables():
    if v.varValue > 10e-4:
        print ( v.name, v.varValue)

This is result

Maximized Value: 128.0
Optimal
x_x1 1.0
x_x10 1.0
x_x4 1.0
x_x5 1.0
x_x6 1.0
x_x8 1.0
y_T1 1.0
y_T2 1.0
y_T3 1.0
y_T4 1.0

Upvotes: 0

Stuart Mitchell
Stuart Mitchell

Reputation: 1059

A bit tricky but I would add a binary variable for each set

T1 >= x1
T1 >= x2
T1 >= x3

T1 <= x1 + x2 + x3

...

Then add

T1 + T2 + T3 + T4 >= 3

Upvotes: 1

Related Questions