CODEWITHSUNDEEP
pythonlinear-programmingsolverpulpmixed-integer-programming
Axel
Axel

Reputation: 2725

PuLP - How to specify the solver's accuracy

I will try to keep my question short and simple. If you need any further information, please let me know.

I have an MIP, implemented in Python with the package PuLP. (Roughly 100 variables and constraints) The mathematical formulation of the problem is from a research paper. This paper also includes a numerical study. However, my results differ from the results of the authors.

My problem variable is called prob

prob = LpProblem("Replenishment_Policy", LpMinimize)

I solve the problem with prob.solve() LpStatus returns Optimal

When I add some of the optimal (paper) results as contraints, I get a slightly better objective value. Same goes for constraining the objecive function to a slightly lower value. The LpStatus remains Optimal.

original objective value: total = 1704.20
decision variable: stock[1] = 370

adding constraints: prob += stock[1] == 379
new objective value: 1704.09

adding constraints: prob += prob.objective <= 1704
new objective value: 1702.81

My assumption is that PuLP's solver approximates the solution. The calculation is very fast, but apparently not very accurate. Is there a way I can improve the accuracy of the solver PuLP is using? I am looking for something like: prob.solve(accuracy=100%). I had a look at the documentation but couldn't figure out what to do. Are there any thoughts what the problem could be?

Any help is appreciated. Thanks.

Upvotes: 6

Views: 7023

Answers (1)

Axel
Axel

Reputation: 2725

The answer to my question was given by ayhan: To specify the accuracy of the solver, you can use the fracGap argument of the selected solver.

prob.solve(solvers.PULP_CBC_CMD(fracGap=0.01))

However, the question I asked, was not aligned with the problem I had. The deviation of the results was indeed not a matter of accuracy of the solver (as sascha pointed out in the comments).

The cause to my problem: The algorithm I implemented was the optimization of the order policy parameters for a (Rn, Sn) policy under non-stationary, stochastic demand. The above mentioned paper is: Tarim, S. A., & Kingsman, B. G. (2006). Modelling and computing (R n, S n) policies for inventory systems with non-stationary stochastic demand. European Journal of Operational Research, 174(1), 581-599.

The algorithm has two binary variables delta[t] and P[t][j]. The following two constraints only allow values of 0 and 1 for P[t][j], as long as delta[t] is defined as a binary.

for t in range(1, T+1):
    prob += sum([P[t][j] for j in range(1, t+1)]) == 1

    for j in range(1, t+1):
        prob += P[t][j] >= delta[t-j+1] - sum([delta[k] for k in range(t-j+2, t+1)])

Since P[t][j] can only take values of 0 or 1, hence being a binary variable, I declared it as follows:

for t in range(1, T+1):
    for j in range(1, T+1):
        P[t][j] = LpVariable(name="P_"+str(t)+"_"+str(j), lowBound=0, upBound=1, cat="Integer")

The objective value for the minimization returns: 1704.20

After researching for a solution for quite a while, I noticed a part of the paper that says:

... it follows that P_tj must still take a binary value even if it is declared as a continuous variable. Therefore, the total number of binary variables reduces to the total number of periods, N.

Therefore I changed the cat argument of the P[t][j] variable to cat="Continuous". Whithout changing anything else, I got the lower objective value of 1702.81. The status of the result shows in both cases: Optimal

I am still not sure how all these aspects are interrelated, but I guess for me this tweek worked. For everyone else who is directed to this question, will probably find the necessary help with the answer given at the top of this post.

Upvotes: 2

Related Questions