Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News Sign UpSign In
| Download

linprogram

Views: 50
1
##########################################
2
# Linear Programming Scripts
3
##########################################
4
#
5
# Johann Thiel
6
# ver 11.25.17
7
# Functions to solve linear
8
# programming problems.
9
#
10
##########################################
11
12
##########################################
13
# Necessary modules
14
##########################################
15
from sage.numerical.backends.generic_backend import get_solver
16
import sage.numerical.backends.glpk_backend as backend
17
from tabulate import tabulate
18
##########################################
19
20
##########################################
21
# Generic linear programming solver that
22
# produces a sensitivity report
23
##########################################
24
# var = list of variable names
25
# con = list of constraint names
26
# ob = list of coefficients of objective
27
# functions
28
# M = matrix of constraint coefficients
29
# inq = list of inequality direction
30
# 1 for '<=' and 0 for '>='
31
# bnd = list of constraint bounds
32
# mx = Boolean to determine if the
33
# problem is a maximization (True)
34
# or minimization (False) problem.
35
# Default is set to maximization.
36
##########################################
37
def lp(var, con, ob, M, inq, bnd, mx=True):
38
# loads the solver
39
q = get_solver(solver = 'GLPK')
40
# sets solver to min, max otherwise
41
if not mx:
42
q.set_sense(-1)
43
# adds all variables
44
for v in var:
45
q.add_variable(name=v)
46
# adds all constraints
47
for i in range(len(M)):
48
if inq[i]:
49
q.add_linear_constraint(list(zip(range(len(M[0])), M[i])), None, bnd[i], con[i])
50
else:
51
q.add_linear_constraint(list(zip(range(len(M[0])), M[i])), bnd[i], None, con[i])
52
# sets objective
53
q.set_objective(ob)
54
q.solver_parameter(backend.glp_simplex_or_intopt, backend.glp_simplex_only)
55
# solves the problem
56
q.solve()
57
# produces sensitivity report
58
q.print_ranges()
59
##########################################
60
61
##########################################
62
# Generic linear programming solver that
63
# produces a sensitivity report
64
##########################################
65
# var = list of variable names
66
# con = list of constraint names
67
# ob = list of coefficients of objective
68
# functions
69
# M = matrix of constraint coefficients
70
# inq = list of inequality direction
71
# 1 for '<=', -1 for '>=' and
72
# 0 for '='.
73
# bnd = list of constraint bounds
74
# mx = Boolean to determine if the
75
# problem is a maximization (True)
76
# or minimization (False) problem.
77
# Default is set to maximization.
78
##########################################
79
def lp(var, con, ob, M, inq, bnd, mx=True):
80
# loads the solver
81
q = get_solver(solver = 'GLPK')
82
# sets solver to min, max otherwise
83
if not mx:
84
q.set_sense(-1)
85
# adds all variables
86
for v in var:
87
q.add_variable(name=v)
88
# adds all constraints
89
for i in range(len(M)):
90
if inq[i] == 1:
91
q.add_linear_constraint(list(zip(range(len(M[0])), M[i])), None, bnd[i], con[i])
92
elif inq[i] == -1:
93
q.add_linear_constraint(list(zip(range(len(M[0])), M[i])), bnd[i], None, con[i])
94
else:
95
q.add_linear_constraint(list(zip(range(len(M[0])), M[i])), bnd[i], bnd[i], con[i])
96
# sets objective
97
q.set_objective(ob)
98
q.solver_parameter(backend.glp_simplex_or_intopt, backend.glp_simplex_only)
99
# solves the problem
100
q.solve()
101
# produces sensitivity report
102
q.print_ranges()
103
##########################################
104
105
##########################################
106
# Generic linear programming solver for
107
# integer programming problems (produces
108
# no sensitivity report)
109
##########################################
110
# var = list of variable names
111
# con = list of constraint names
112
# ob = list of coefficients of objective
113
# functions
114
# M = matrix of constraint coefficients
115
# inq = list of inequality direction
116
# 1 for '<=', -1 for '>=' and
117
# 0 for '='.
118
# bnd = list of constraint bounds
119
# mx = Boolean to determine if the
120
# problem is a maximization (True)
121
# or minimization (False) problem.
122
# Default is set to maximization.
123
##########################################
124
def lpInt(var, con, ob, M, inq, bnd, mx=True):
125
# loads the solver
126
q = get_solver(solver = 'GLPK')
127
# sets solver to min, max otherwise
128
if not mx:
129
q.set_sense(-1)
130
# adds all variables
131
for v in var:
132
q.add_variable(integer=True, name=v)
133
# adds all constraints
134
for i in range(len(M)):
135
if inq[i] == 1:
136
q.add_linear_constraint(list(zip(range(len(M[0])), M[i])), None, bnd[i], con[i])
137
elif inq[i] == -1:
138
q.add_linear_constraint(list(zip(range(len(M[0])), M[i])), bnd[i], None, con[i])
139
else:
140
q.add_linear_constraint(list(zip(range(len(M[0])), M[i])), bnd[i], bnd[i], con[i])
141
# sets objective
142
q.set_objective(ob)
143
q.solver_parameter(backend.glp_simplex_then_intopt)
144
# solves the problem
145
q.solve()
146
# The following lines all produce an output report
147
if mx:
148
st = ' (max) '
149
else:
150
st = ' (min) '
151
sol = [q.get_variable_value(i) for i in range(q.ncols())]
152
print 'Optimal'+st+'value: ', q.get_objective_value()
153
print ''
154
results = [[a,b] for a,b in zip(var,sol)]
155
print tabulate(results, headers=['Variable', 'Value'])
156
print ''
157
slack = [[q.row_name(j), round(max(0,abs(bnd[j]-sum([a*b for a,b in zip(sol,M[j])]))),3)] for j in range(q.nrows())]
158
print tabulate(slack, headers=['Constraint', 'Slack'])
159
##########################################
160
161
##########################################
162
# Generic linear programming solver for
163
# binary integer programming problems
164
# (produces no sensitivity report)
165
##########################################
166
#
167
# var = list of variable names
168
# con = list of constraint names
169
# ob = list of coefficients of objective
170
# functions
171
# M = matrix of constraint coefficients
172
# inq = list of inequality direction
173
# 1 for '<=', -1 for '>=' and
174
# 0 for '='.
175
# bnd = list of constraint bounds
176
# mx = Boolean to determine if the
177
# problem is a maximization (True)
178
# or minimization (False) problem.
179
# Default is set to maximization.
180
##########################################
181
def lpBin(var, con, ob, M, inq, bnd, mx=True):
182
# loads the solver
183
q = get_solver(solver = 'GLPK')
184
# sets solver to min, max otherwise
185
if not mx:
186
q.set_sense(-1)
187
# adds all variables
188
for v in var:
189
q.add_variable(binary=True, name=v)
190
# adds all constraints
191
for i in range(len(M)):
192
if inq[i] == 1:
193
q.add_linear_constraint(list(zip(range(len(M[0])), M[i])), None, bnd[i], con[i])
194
elif inq[i] == -1:
195
q.add_linear_constraint(list(zip(range(len(M[0])), M[i])), bnd[i], None, con[i])
196
else:
197
q.add_linear_constraint(list(zip(range(len(M[0])), M[i])), bnd[i], bnd[i], con[i])
198
# sets objective
199
q.set_objective(ob)
200
q.solver_parameter(backend.glp_simplex_then_intopt)
201
# solves the problem
202
q.solve()
203
# The following lines all produce an output report
204
if mx:
205
st = ' (max) '
206
else:
207
st = ' (min) '
208
sol = [q.get_variable_value(i) for i in range(q.ncols())]
209
print 'Optimal'+st+'value: ', q.get_objective_value()
210
print ''
211
results = [[a,b] for a,b in zip(var,sol)]
212
print tabulate(results, headers=['Variable', 'Value'])
213
print ''
214
slack = [[q.row_name(j), round(max(0,abs(bnd[j]-sum([a*b for a,b in zip(sol,M[j])]))),3)] for j in range(q.nrows())]
215
print tabulate(slack, headers=['Constraint', 'Slack'])
216
##########################################
217
218
219
220
221
222
223
224
225
226
227
228