-
Notifications
You must be signed in to change notification settings - Fork 0
/
solver.py
288 lines (233 loc) · 12.8 KB
/
solver.py
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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
"""Driver for the various solution methods of the trilevel game.
Calls each of the solution algorithms for a given problem instance, and also
applies the LP relaxation solution to the MILP to evaluate the optimality gap.
The functions in this module can be used to call a particular solution method
once, and are used by the main driver to call all available solution methods
for comparison.
"""
import gc
import time
import upper.upper_cp as ucp
import upper.lower.milp_lp_cp as milpcp
import upper.lower.network.network as net
#==============================================================================
class TrialSolver:
"""Class for driving the computational trial process.
Loads the given trial network file upon initialization. Includes public
methods for running each individual required test, each of which returns
the objective, defender/attacker decisions, and times and iteration counts
for use by the overall trial driver.
There is also an internal attribute that stores the value of the most
recent defensive vector returned by one of the solvers.
"""
#--------------------------------------------------------------------------
def __init__(self, file):
"""Trial evaluation object constructor.
Requires the following positional arguments:
file -- Complete file path for the NETGEN file containing the
network definition.
"""
# Build the network for the given trial file
self.Net = net.Network(file)
# Initialize memory object for most recent upper-level solution
self.last_defense = [False for i in range(len(self.Net.arcs))]
#--------------------------------------------------------------------------
def solve_milp_cutting_plane(self, upper_cutoff=100, lower_cutoff=100,
upper_gap=0.01, lower_gap=0.01, big_m=1.0e16,
small_m=1.0e10):
"""Solves the trilevel model using the MILP cutting plane algorithm.
Creates an upper-level solver object associated with the problem
network, and equipped to solve the model version with binary
interdependencies via the cutting plane lower-level algorithm.
Accepts the following optional keyword arguments:
upper_cutoff -- Iteration cutoff for the upper-level cutting plane
main loop. Defaults to 100.
upper_gap -- Optimality gap tolerance for the upper-level cutting
plane main loop. Defaults to 0.01.
lower_cutoff -- Iteration cutoff for the lower-level cutting plane
main loop (if applicable). Defaults to 100.
lower_gap -- Optimality gap tolerance for the lower-level cutting
plane main loop (if applicable). Defaults to 0.01.
big_m -- Large constant for use in the big-M method. Should be
chosen to be significantly larger than the largest objective
allowed to be returned by the lower-level submodel. Defaults to
1.0e16.
small_m -- Big-M constant for use in the lower-level model. Should
still be larger than any reasonable values produced by the
solution algorithm, but significantly smaller than big_m.
Defaults to 1.0e10.
Returns a tuple containing the following elements:
objective -- Objective value of the trilevel program.
defend -- Vector of defended arcs, as a boolean list.
destroy -- Vector of destroyed arcs, as a boolean list.
times -- Tuple of cumulative times spent on various parts of the
solution process, including: (total, upper level, lower level)
iterations -- Tuple of iterations of each cutting plane loop (upper
level then lower level), with -1 if not applicable (for example
in the case of the duality lower-level program)
"""
# Collect garbage
gc.collect()
# Initialize a temporary upper-level solver object
Up = ucp.UpperLevel(self.Net, 1, big_m=big_m, small_m=small_m)
# Apply solver, save defense, and time entire process
tot = time.time()
(obj, self.last_defense, attack, times, iterations, status) = Up.solve(
cutoff=upper_cutoff, lower_cutoff=lower_cutoff, gap=upper_gap,
lower_gap=lower_gap)
tot = time.time() - tot
# End solver
Up.end()
# Return results
return (obj, self.last_defense, attack, (tot, times[0], times[1]),
iterations)
#--------------------------------------------------------------------------
def solve_lp_cutting_plane(self, upper_cutoff=100, lower_cutoff=100,
upper_gap=0.01, lower_gap=0.01, big_m=1.0e16,
small_m=1.0e10):
"""Solves the trilevel model using the LP cutting plane algorithm.
Creates an upper-level solver object associated with the problem
network, and equipped to solve the model version with linear
interdependencies via the cutting plane lower-level algorithm.
Accepts the following optional keyword arguments:
upper_cutoff -- Iteration cutoff for the upper-level cutting plane
main loop. Defaults to 100.
upper_gap -- Optimality gap tolerance for the upper-level cutting
plane main loop. Defaults to 0.01.
lower_cutoff -- Iteration cutoff for the lower-level cutting plane
main loop (if applicable). Defaults to 100.
lower_gap -- Optimality gap tolerance for the lower-level cutting
plane main loop (if applicable). Defaults to 0.01.
big_m -- Large constant for use in the big-M method. Should be
chosen to be significantly larger than the largest objective
allowed to be returned by the lower-level submodel. Defaults to
1.0e16.
small_m -- Big-M constant for use in the lower-level model. Should
still be larger than any reasonable values produced by the
solution algorithm, but significantly smaller than big_m.
Defaults to 1.0e10.
Returns a tuple containing the following elements:
objective -- Objective value of the trilevel program.
defend -- Vector of defended arcs, as a boolean list.
destroy -- Vector of destroyed arcs, as a boolean list.
times -- Tuple of cumulative times spent on various parts of the
solution process, including: (total, upper level, lower level)
iterations -- Tuple of iterations of each cutting plane loop (upper
level then lower level), with -1 if not applicable (for example
in the case of the duality lower-level program)
"""
# Collect garbage
gc.collect()
# Initialize a temporary upper-level solver object
Up = ucp.UpperLevel(self.Net, 2, big_m=big_m, small_m=small_m)
# Apply solver, save defense, and time entire process
tot = time.time()
(obj, self.last_defense, attack, times, iterations, status) = Up.solve(
cutoff=upper_cutoff, lower_cutoff=lower_cutoff, gap=upper_gap,
lower_gap=lower_gap)
tot = time.time() - tot
# End solver
Up.end()
# Return results
return (obj, self.last_defense, attack, (tot, times[0], times[1]),
iterations)
#--------------------------------------------------------------------------
def solve_lp_duality(self, upper_cutoff=100, upper_gap=0.01, big_m=1.0e16):
"""Solves the trilevel model using the LP duality algorithm.
Creates an upper-level solver object associated with the problem
network, and equipped to solve the model version with linear
interdependencies via the duality lower-level algorithm.
Accepts the following optional keyword arguments:
upper_cutoff -- Iteration cutoff for the upper-level cutting plane
main loop. Defaults to 100.
upper_gap -- Optimality gap tolerance for the upper-level cutting
plane main loop. Defaults to 0.01.
big_m -- Large constant for use in the big-M method. Should be
chosen to be significantly larger than the largest objective
allowed to be returned by the lower-level submodel. Defaults to
1.0e16.
Returns a tuple containing the following elements:
objective -- Objective value of the trilevel program.
defend -- Vector of defended arcs, as a boolean list.
destroy -- Vector of destroyed arcs, as a boolean list.
times -- Tuple of cumulative times spent on various parts of the
solution process, including: (total, upper level, lower level)
iterations -- Tuple of iterations of each cutting plane loop (upper
level then lower level), with -1 if not applicable (for example
in the case of the duality lower-level program)
"""
# Collect garbage
gc.collect()
# Initialize a temporary upper-level solver object
Up = ucp.UpperLevel(self.Net, 3, big_m=big_m)
# Apply solver, save defense, and time entire process
tot = time.time()
(obj, self.last_defense, attack, times, iterations, status) = Up.solve(
cutoff=upper_cutoff, gap=upper_gap)
tot = time.time() - tot
# End solver
Up.end()
# Return results
return (obj, self.last_defense, attack, (tot, times[0], times[1]),
iterations)
#--------------------------------------------------------------------------
def solve_milp_defend(self, defend, cutoff=100, gap=0.01, big_m=1.0e10):
"""Calculates the MILP solution for a given defensive decision.
Requires the following positional arguments:
defend -- Vector of defended arcs, as a boolean list.
Accepts the following optional keyword arguments:
cutoff -- Iteration cutoff for the overall cutting plane main loop.
Defaults to 100. Used only for cutting plane lower-level
methods.
gap -- Optimality gap tolerance for the overall cutting plane main
loop. Defaults to 0.01. Used only for cutting plane lower-
level methods.
big_m -- Large constant for use in the big-M method. Should be
chosen to be significantly larger than the largest objective
allowed to be returned by the lower-level submodel. Defaults to
1.0e10.
Returns a tuple containing the following elements:
objective -- Objective value of the lower-level bilevel program.
destroy -- Vector of destroyed arcs, as a boolean list.
status -- Numerical code to describe the results of the solution
process, including the following:
0: Successful exit with finite objective value.
1: Successful exit with infinite objective value.
2: Exit due to error.
iterations -- Number of iterations of the lower-level algorithm's
cutting plane loop (0 if not applicable).
"""
# Collect garbage
gc.collect()
# Initialize a temporary upper-level solver object
Up = ucp.UpperLevel(self.Net, 1, small_m=big_m)
# Get lower level solution for specified defense
out = Up.lower_solve(defend, cutoff=cutoff, gap=gap)
# End solver
Up.end()
# Return solution
return out
#--------------------------------------------------------------------------
def solve_milp_initial(self):
"""Calculates the initial MILP solution.
Calculates the solution of the lower-level binary interdependency
model with no defensive or attack decisions made.
Returns a tuple containing the following elements:
objective -- Objective value of the lower-level bilevel program.
status -- Numerical code to describe the results of the solution
process, including the following:
0: Successful exit with feasible MILP.
1: Successful exit with infeasible MILP.
2: Exit due to error.
"""
# Initialize a temporary lower-level solver object
Milp = milpcp.LLCuttingPlane(self.Net, 1)
# Get lower level solution with no attacks made
(obj, _, feas) = Milp.lower_solve(destroy=[])
status = 0
if feas == False:
status = 1
# End solver
Milp.end()
# Return solution
return (obj, status)