CODEWITHSUNDEEP
pythonoptimizationpython-multiprocessingpulp
user14232027
user14232027

Reputation:

Cannot reduce time taken to add constraints to pulp

I have the following code(python 3) for adding constraints to pulp(v 2.3). It needs to add up to 400000 constraints(100^2 S, 4 A).

    def linearProgram(self, error = 1e-12):
        lp_problem = p.LpProblem('best-Vpi', p.LpMinimize)

        #create problem variables
        V = p.LpVariable.dicts("V",range(self.S), cat = "Continuous")
        #objective function
        for i in range(self.S):
            self.v.append(V[i])
        lp_problem += p.lpSum(self.v)
        #constraints
        for s in range(self.S):
            for a in range(self.A):
                pv = p.LpAffineExpression([(V[x],self.T[s][a][x]) for x in range(self.S)])
                constraint = p.lpSum([self.PR[s][a], self.gamma*pv ])
                lp_problem += V[s] >= constraint

        status = lp_problem.solve(p.PULP_CBC_CMD(msg = 0)) #solve

I can't seem to be able to optimise it further..

I even tried multiprocessing, but it gave a lot of errors-


    def __addconstraints(self, S0, S1, lp_problem):
        for s in range(S0, S1):
            for a in range(self.A):
                pv= p.lpDot(self.T[s][a],self.v)
                lp_problem += self.v[s] >= p.lpSum([self.PR[s][a], self.gamma*pv])
   ..................
   #in linearProgram
        if self.S%4:
            s0, s1 = 0, self.S//3
        else:
            s0, s1 = 0, self.S//4
        incr = s1
        processes = []
        for x in range(4):
            proc = multiprocessing.Process(target=self.__addconstraints, args=(s0, s1, lp_problem))
            processes.append(proc)
            proc.start()
            s0 = s1
            s1 = min(s1+incr, self.S)

        for proc in processes:
            proc.join()

        hard code for episodic? no need (due to initialization of mdp)
        if self.mdptype=="episodic":
            for state in self.end:
                lp_problem += V[state] == 0

I am new to both pulp and multiprocessing, so I don't really have an idea what I'm doing :p

Any kind of help is appreciated.

Upvotes: 1

Views: 593

Answers (1)

pchtsp
pchtsp

Reputation: 864

In your code, you first build a p.LpAffineExpression, then you apply a p.lpSum and finally you do a third operation on the result V[s] >= constraint. The two last operations may increase the time because the expression is being copied each time.

From my experience, the fastest times I've gotten are doing the following:

# _vars_tup is a list of (key, value) pairs where each key is a variable and each value is a coefficient.
#  it's like initializing a dictionary.
# CONSTANT is a python number (not a pulp variable)
model += p.LpAffineExpression(_vars_tup, constant=CONSTANT) >= 0

The idea is to reduce the number of times you do operations with p.LpAffineExpression objects, because a copy is done at each operation. So, build the list of variables and coefficients (_vars_tup) for ALL the variables present in the constraint and then at the last step create the p.LpAffineExpression and compare it with a constant.

An equivalent way would be (although I haven't tried it):

const = p.LpConstraint(e=p.LpAffineExpression(_vars_tup, constant=_constant), sense = p.LpConstraintGE, rhs = -CONSTANT)
model.addConstraint(other)

Upvotes: 1

Related Questions