optimizer.py 7.41 KB
Newer Older
1
from time import time
Bowen Wu's avatar
Bowen Wu committed
2
3
4
5
import xml.etree.ElementTree as ET
from cplex import Cplex
import gurobipy as gp
from mps_util import VerbosePrint
6
import mip
Bowen Wu's avatar
Bowen Wu committed
7
8
9
10
11
12
13

# Solver status
OPTIMAL = 0
INFEASIBLE = 1
INF_OR_UNBD = 2
UNBOUNDED = 3
UNKNOWN = 4
14
TIME_LIMIT_EXCEEDED = 5
Bowen Wu's avatar
Bowen Wu committed
15
16
17
18
19
20

status_text = {
    OPTIMAL : "optimal",
    INFEASIBLE : "infeasible",
    INF_OR_UNBD : "infeasible or unbounded",
    UNBOUNDED : "unbounded",
21
22
    UNKNOWN : "unknown",
    TIME_LIMIT_EXCEEDED : "time limit exceeded",
Bowen Wu's avatar
Bowen Wu committed
23
24
}

Bowen Wu's avatar
Bowen Wu committed
25
MAX_TIME_LIMIT = 5
26

Bowen Wu's avatar
Bowen Wu committed
27
class Solver(object):
28
    def __init__(self, verbose = False, timeout = True) -> None:
Bowen Wu's avatar
Bowen Wu committed
29
30
        # by default, the solvers are very talky but we can make it less verbose
        self.verbose = verbose
31
        self.timeout = timeout
Bowen Wu's avatar
Bowen Wu committed
32
        self.stats = dict()
33
        for k in [OPTIMAL, INFEASIBLE, INF_OR_UNBD, UNBOUNDED, UNKNOWN, TIME_LIMIT_EXCEEDED]:
Bowen Wu's avatar
Bowen Wu committed
34
35
36
37
38
39
40
41
42
43
44
            self.stats[k] = 0
    
    def print_solver_stats(self) -> None:
        print("\n", self.__class__.__name__, " Stats:")
        for k in self.stats:
            print(status_text[k], " = ", self.stats[k], " times")

class CplexSolver(Solver):
    # https://www.tu-chemnitz.de/mathematik/discrete/manuals/cplex/doc/refman/html/appendixB.html
    status_code = {
        # LP
45
46
47
48
49
        1  : OPTIMAL,
        2  : UNBOUNDED,
        3  : INFEASIBLE,
        4  : INF_OR_UNBD,
        11 : TIME_LIMIT_EXCEEDED,
Bowen Wu's avatar
Bowen Wu committed
50
51
52
        # MIP
        101 : OPTIMAL, 
        102 : OPTIMAL,
53
54
        107 : TIME_LIMIT_EXCEEDED,
        108 : TIME_LIMIT_EXCEEDED,
55
        115 : INFEASIBLE, # https://www-eio.upc.edu/lceio/manuals/cplex-11/html/usrcplex/solveLP19.html
Bowen Wu's avatar
Bowen Wu committed
56
57
58
        103 : INFEASIBLE,
        118 : UNBOUNDED,
        119 : INF_OR_UNBD
Bowen Wu's avatar
Bowen Wu committed
59
60
    }

61
62
    def __init__(self, verbose = False, timeout = True) -> None:
        super().__init__(verbose, timeout)
Bowen Wu's avatar
Bowen Wu committed
63
64

    def __call__(self, mps_file: str) -> dict:
Bowen Wu's avatar
Bowen Wu committed
65
66
67
68
69
        model = Cplex()
        model.set_results_stream(None)
        model.set_warning_stream(None)
        model.set_error_stream(None)
        model.set_log_stream(None)
Bowen Wu's avatar
Bowen Wu committed
70
71
72
73
        
        ps = model.create_parameter_set()
        ps.add(model.parameters.threads, 4) # somehow 32 threads is very slow

74
75
        if self.timeout:
            ps.add(model.parameters.timelimit, MAX_TIME_LIMIT)
Bowen Wu's avatar
Bowen Wu committed
76
77

        model.set_parameter_set(ps)
Bowen Wu's avatar
Bowen Wu committed
78

Bowen Wu's avatar
Bowen Wu committed
79
        with VerbosePrint(self.verbose):
Bowen Wu's avatar
Bowen Wu committed
80
            model.read(mps_file)
Bowen Wu's avatar
Bowen Wu committed
81
82
83
            model.solve()     

        if self.get_sol_status(model.solution) == INF_OR_UNBD:
84
            model.parameters.preprocessing.reduce.set(0)
Bowen Wu's avatar
Bowen Wu committed
85
            with VerbosePrint(self.verbose):
86
                model.read(mps_file)
Bowen Wu's avatar
Bowen Wu committed
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
                model.solve()

        ret = dict()
        ret["status"] = self.get_sol_status(model.solution)
        self.stats[ret["status"]] += 1

        if ret["status"] == OPTIMAL:
            ret["obj_val"] = self.get_obj_val(model.solution)
            ret["var_val"] = self.get_var_val(model.solution, model.variables)

        return ret

    def get_sol_status(self, sol) -> int:
        try:
            return CplexSolver.status_code[sol.get_status()]
        except KeyError:
            return UNKNOWN
    
    def get_obj_val(self, sol) -> float:
        return sol.get_objective_value()

    def get_var_val(self, sol, var) -> dict:
        ret = dict()
        for name in var.get_names():
            ret[name] = sol.get_values(name)
        return ret

    def get_sol_status_xml(self, sol: ET.ElementTree) -> int:
        root = sol.getroot()
        header = root.find('header')
        status = header.get('solutionStatusString')
        if status == 'optimal':
            return OPTIMAL
        elif status == 'infeasible':
            return INFEASIBLE
        else:
            return UNKNOWN

    def get_obj_val_xml(self, sol: ET.ElementTree) -> float:
        root = sol.getroot()
        header = root.find('header')
        return float(header.get('objectiveValue'))

    def get_var_val_xml(self, sol: ET.ElementTree) -> dict:
        root = sol.getroot()
        variables = root.find('variables')
        ret = dict()
        for var in variables.iter(tag = "variable"):
            name = var.get("name")
            val = float(var.get("value"))
            ret[name] = val
        return ret

class GurobiSolver(Solver):
    """ Gurobi Solver Wrapper
    Python interface documentation: 
    https://www.gurobi.com/documentation/9.5/refman/py_model.html#pythonclass:Model
    """
    # https://www.gurobi.com/documentation/9.5/refman/optimization_status_codes.html#sec:StatusCodes
    status_code = {
        2 : OPTIMAL,
        3 : INFEASIBLE,
        4 : INF_OR_UNBD,
150
151
        5 : UNBOUNDED,
        9 : TIME_LIMIT_EXCEEDED, 
Bowen Wu's avatar
Bowen Wu committed
152
153
    }

154
155
    def __init__(self, verbose = False, timeout = True) -> None:
        super().__init__(verbose, timeout)
Bowen Wu's avatar
Bowen Wu committed
156
157
158
159

    def __call__(self, mps_file: str) -> dict:
        with VerbosePrint(self.verbose):
            model = gp.read(mps_file)
Bowen Wu's avatar
Bowen Wu committed
160
            model.setParam("OutputFlag", False)
161
162
            if self.timeout:
                model.setParam(gp.GRB.Param.TimeLimit, MAX_TIME_LIMIT)
Bowen Wu's avatar
Bowen Wu committed
163
164
165
166
167
168
169
170
            model.optimize()
        
        if self.get_sol_status(model) == INF_OR_UNBD:
            # https://www.gurobi.com/documentation/9.5/refman/dualreductions.html#parameter:DualReductions
            with VerbosePrint(self.verbose):
                model.setParam("DualReductions", 0)
                model.optimize()
        
171
172
173
174
175
176
177
        if self.get_sol_status(model) == UNBOUNDED:
            # set the obj val to 0 and re-optimize
            # in Gurobi, unbound does not imply feasible
            with VerbosePrint(self.verbose):
                model.setObjective(0, model.ModelSense)
                model.optimize()

Bowen Wu's avatar
Bowen Wu committed
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
        ret = dict()
        ret["status"] = self.get_sol_status(model)
        self.stats[ret["status"]] += 1

        if ret["status"] == OPTIMAL:
            ret["obj_val"] = self.get_obj_val(model)
            ret["var_val"] = self.get_var_val(model)

        return ret

    def get_sol_status(self, model) -> int:
        return GurobiSolver.status_code[model.Status]

    def get_obj_val(self, model) -> float:
        return model.ObjVal

    def get_var_val(self, model) -> dict:
        ret = dict()
        for v in model.getVars():
            ret[v.VarName] = v.X
        return ret

Ambi's avatar
Ambi committed
200
201
202
203
204
205
206
207
208
209
210
class CBCSolver(Solver):
    """ CBC Solver Wrapper
    Python interface documentation: 
    https://python-mip.readthedocs.io/en/latest/quickstart.html
    """

    def __init__(self, verbose = False) -> None:
        super().__init__(verbose)

    def __call__(self, mps_file: str) -> dict:
        with VerbosePrint(False):
211
            model = mip.Model()
Ambi's avatar
Ambi committed
212
213
214
215
            model.read(mps_file)
            status = model.optimize()

        ret = dict()
216
217
        if status == mip.OptimizationStatus.OPTIMAL or \
            status == mip.OptimizationStatus.FEASIBLE: #for now marking this as optimal as well
Ambi's avatar
Ambi committed
218
219
            ret['status'] = OPTIMAL
            ret["obj_val"] = model.objective_value
220
221
222
        elif status == mip.OptimizationStatus.NO_SOLUTION_FOUND or \
            status == mip.OptimizationStatus.INFEASIBLE or \
            status == mip.OptimizationStatus.INT_INFEASIBLE:
Ambi's avatar
Ambi committed
223
            ret['status'] = INFEASIBLE
224
225
226
227
        elif status == mip.OptimizationStatus.UNBOUNDED:
            ret['status'] = UNBOUNDED
        else:
            ret["status"] = UNKNOWN
Ambi's avatar
Ambi committed
228
229
230
231

        return ret


Bowen Wu's avatar
Bowen Wu committed
232
233
234
235
236
237
238
if __name__ == "__main__":
    mps_file = "mps/testprob_int.mps"
    cpx = CplexSolver()
    grb = GurobiSolver()
    print(cpx(mps_file))
    print(grb(mps_file))
    cpx.print_solver_stats()
Bowen Wu's avatar
Bowen Wu committed
239
    grb.print_solver_stats()