File: CG.py

package info (click to toggle)
python-pulp 2.6.0%2Bdfsg-1
  • links: PTS, VCS
  • area: main
  • in suites: bookworm
  • size: 14,720 kB
  • sloc: python: 7,505; makefile: 16; sh: 16
file content (142 lines) | stat: -rw-r--r-- 4,178 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
"""
Column Generation Functions

Authors: Antony Phillips,  Dr Stuart Mitchell  2008
"""

# Import PuLP modeler functions
from pulp import *


class Pattern:
    """
    Information on a specific pattern in the SpongeRoll Problem
    """

    cost = 1
    trimValue = 0.04
    totalRollLength = 20
    lenOpts = ["5", "7", "9"]

    def __init__(self, name, lengths=None):
        self.name = name
        self.lengthsdict = dict(zip(self.lenOpts, lengths))

    def __str__(self):
        return self.name

    def trim(self):
        return Pattern.totalRollLength - sum(
            [int(i) * int(self.lengthsdict[i]) for i in self.lengthsdict]
        )


def masterSolve(Patterns, rollData, relax=True):

    # The rollData is made into separate dictionaries
    (rollDemand, surplusPrice) = splitDict(rollData)

    # The variable 'prob' is created
    prob = LpProblem("Cutting Stock Problem", LpMinimize)

    # vartype represents whether or not the variables are relaxed
    if relax:
        vartype = LpContinuous
    else:
        vartype = LpInteger

    # The problem variables are created
    pattVars = LpVariable.dicts("Pattern", Patterns, 0, None, vartype)
    surplusVars = LpVariable.dicts("Surplus", Pattern.lenOpts, 0, None, vartype)

    # The objective function is entered: (the total number of large rolls used * the cost of each) -
    # (the value of the surplus stock) - (the value of the trim)
    prob += (
        lpSum([pattVars[i] * Pattern.cost for i in Patterns])
        - lpSum([surplusVars[i] * surplusPrice[i] for i in Pattern.lenOpts])
        - lpSum([pattVars[i] * i.trim() * Pattern.trimValue for i in Patterns])
    )

    # The demand minimum constraint is entered
    for j in Pattern.lenOpts:
        prob += (
            lpSum([pattVars[i] * i.lengthsdict[j] for i in Patterns]) - surplusVars[j]
            >= rollDemand[j],
            "Min%s" % j,
        )

    # The problem is solved
    prob.solve()

    # The variable values are rounded
    prob.roundSolution()

    if relax:
        # Creates a dual variables list
        duals = {}
        for name, i in zip(["Min5", "Min7", "Min9"], Pattern.lenOpts):
            duals[i] = prob.constraints[name].pi

        return duals

    else:
        # Creates a dictionary of the variables and their values
        varsdict = {}
        for v in prob.variables():
            varsdict[v.name] = v.varValue

        # The number of rolls of each length in each pattern is printed
        for i in Patterns:
            print(i, " = %s" % [i.lengthsdict[j] for j in Pattern.lenOpts])

        return value(prob.objective), varsdict


def subSolve(Patterns, duals):

    # The variable 'prob' is created
    prob = LpProblem("SubProb", LpMinimize)

    # The problem variables are created
    _vars = LpVariable.dicts("Roll Length", Pattern.lenOpts, 0, None, LpInteger)

    trim = LpVariable("Trim", 0, None, LpInteger)

    # The objective function is entered: the reduced cost of a new pattern
    prob += (Pattern.cost - Pattern.trimValue * trim) - lpSum(
        [_vars[i] * duals[i] for i in Pattern.lenOpts]
    ), "Objective"

    # The conservation of length constraint is entered
    prob += (
        lpSum([_vars[i] * int(i) for i in Pattern.lenOpts]) + trim
        == Pattern.totalRollLength,
        "lengthEquate",
    )

    # The problem is solved
    prob.solve()

    # The variable values are rounded
    prob.roundSolution()

    # The new pattern is written to a dictionary
    varsdict = {}
    newPattern = {}
    for v in prob.variables():
        varsdict[v.name] = v.varValue
    for i, j in zip(
        Pattern.lenOpts, ["Roll_Length_5", "Roll_Length_7", "Roll_Length_9"]
    ):
        newPattern[i] = int(varsdict[j])

    # Check if there are more patterns which would reduce the master LP objective function further
    if value(prob.objective) < -(10 ** -5):
        morePatterns = True  # continue adding patterns
        Patterns += [
            Pattern("P" + str(len(Patterns)), [newPattern[i] for i in ["5", "7", "9"]])
        ]
    else:
        morePatterns = False  # all patterns have been added

    return Patterns, morePatterns