Coverage for picos/solvers/solver_cplex.py : 78.77%
Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1# ------------------------------------------------------------------------------
2# Copyright (C) 2018-2019 Maximilian Stahlberg
3#
4# This file is part of PICOS.
5#
6# PICOS is free software: you can redistribute it and/or modify it under the
7# terms of the GNU General Public License as published by the Free Software
8# Foundation, either version 3 of the License, or (at your option) any later
9# version.
10#
11# PICOS is distributed in the hope that it will be useful, but WITHOUT ANY
12# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
13# A PARTICULAR PURPOSE. See the GNU General Public License for more details.
14#
15# You should have received a copy of the GNU General Public License along with
16# this program. If not, see <http://www.gnu.org/licenses/>.
17# ------------------------------------------------------------------------------
19"""Implementation of :class:`CPLEXSolver`."""
21import time
22from collections import namedtuple
24import cvxopt
26from ..apidoc import api_end, api_start
27from ..constraints import (AffineConstraint, ConvexQuadraticConstraint,
28 DummyConstraint, RSOCConstraint, SOCConstraint)
29from ..expressions import (CONTINUOUS_VARTYPES, AffineExpression,
30 BinaryVariable, IntegerVariable,
31 QuadraticExpression)
32from ..modeling.footprint import Specification
33from ..modeling.solution import (PS_FEASIBLE, PS_ILLPOSED, PS_INF_OR_UNB,
34 PS_INFEASIBLE, PS_UNBOUNDED, PS_UNKNOWN,
35 PS_UNSTABLE, SS_EMPTY, SS_FAILURE,
36 SS_FEASIBLE, SS_INFEASIBLE, SS_OPTIMAL,
37 SS_PREMATURE, SS_UNKNOWN)
38from .solver import (ConflictingOptionsError, DependentOptionError, Solver,
39 UnsupportedOptionError)
41_API_START = api_start(globals())
42# -------------------------------
45#: Maps CPLEX status code to PICOS status triples.
46CPLEX_STATUS_CODES = {
47 # primal status, dual status, problem status
481: (SS_OPTIMAL, SS_OPTIMAL, PS_FEASIBLE), # CPX_STAT_OPTIMAL
492: (SS_UNKNOWN, SS_INFEASIBLE, PS_UNBOUNDED), # CPX_STAT_UNBOUNDED
503: (SS_INFEASIBLE, SS_UNKNOWN, PS_INFEASIBLE), # CPX_STAT_INFEASIBLE
514: (SS_UNKNOWN, SS_UNKNOWN, PS_INF_OR_UNB), # CPX_STAT_INForUNBD
525: (SS_INFEASIBLE, SS_UNKNOWN, PS_UNSTABLE), # CPX_STAT_OPTIMAL_INFEAS
536: (SS_UNKNOWN, SS_UNKNOWN, PS_UNSTABLE), # CPX_STAT_NUM_BEST
54 # 7—9 are not defined.
5510: (SS_PREMATURE, SS_PREMATURE, PS_UNKNOWN), # CPX_STAT_ABORT_IT_LIM
5611: (SS_PREMATURE, SS_PREMATURE, PS_UNKNOWN), # CPX_STAT_ABORT_TIME_LIM
5712: (SS_PREMATURE, SS_PREMATURE, PS_UNKNOWN), # CPX_STAT_ABORT_OBJ_LIM
5813: (SS_PREMATURE, SS_PREMATURE, PS_UNKNOWN), # CPX_STAT_ABORT_USER
59 # 14—19 seem irrelevant (CPX_STAT_*_RELAXED_*).
6020: (SS_UNKNOWN, SS_UNKNOWN, PS_ILLPOSED), # …_OPTIMAL_FACE_UNBOUNDED
6121: (SS_PREMATURE, SS_PREMATURE, PS_UNKNOWN), # …_ABORT_PRIM_OBJ_LIM
6222: (SS_PREMATURE, SS_PREMATURE, PS_UNKNOWN), # …_ABORT_DUAL_OBJ_LIM
6323: (SS_FEASIBLE, SS_FEASIBLE, PS_FEASIBLE), # CPX_STAT_FEASIBLE
64 # 24 irrelevant (CPX_STAT_FIRSTORDER).
6525: (SS_PREMATURE, SS_PREMATURE, PS_UNKNOWN), # …_ABORT_DETTIME_LIM
66 # 26—29 are not defined.
67 # 30—39 seem irrelevant (CPX_STAT_CONFLICT_*).
68 # 40—100 are not defined.
69101: (SS_OPTIMAL, SS_EMPTY, PS_FEASIBLE), # CPXMIP_OPTIMAL
70102: (SS_OPTIMAL, SS_EMPTY, PS_FEASIBLE), # CPXMIP_OPTIMAL_TOL
71103: (SS_INFEASIBLE, SS_EMPTY, PS_INFEASIBLE), # CPXMIP_INFEASIBLE
72104: (SS_PREMATURE, SS_EMPTY, PS_UNKNOWN), # CPXMIP_SOL_LIM ?
73105: (SS_FEASIBLE, SS_EMPTY, PS_FEASIBLE), # CPXMIP_NODE_LIM_FEAS
74106: (SS_PREMATURE, SS_EMPTY, PS_UNKNOWN), # CPXMIP_NODE_LIM_INFEAS
75107: (SS_FEASIBLE, SS_EMPTY, PS_FEASIBLE), # CPXMIP_TIME_LIM_FEAS
76108: (SS_PREMATURE, SS_EMPTY, PS_UNKNOWN), # CPXMIP_TIME_LIM_INFEAS
77109: (SS_FEASIBLE, SS_EMPTY, PS_FEASIBLE), # CPXMIP_FAIL_FEAS
78110: (SS_FAILURE, SS_EMPTY, PS_UNKNOWN), # CPXMIP_FAIL_INFEAS
79111: (SS_FEASIBLE, SS_EMPTY, PS_FEASIBLE), # CPXMIP_MEM_LIM_FEAS
80112: (SS_PREMATURE, SS_EMPTY, PS_UNKNOWN), # CPXMIP_MEM_LIM_INFEAS
81113: (SS_FEASIBLE, SS_EMPTY, PS_FEASIBLE), # CPXMIP_ABORT_FEAS
82114: (SS_PREMATURE, SS_EMPTY, PS_UNKNOWN), # CPXMIP_ABORT_INFEAS
83115: (SS_INFEASIBLE, SS_EMPTY, PS_UNSTABLE), # CPXMIP_OPTIMAL_INFEAS
84116: (SS_FEASIBLE, SS_EMPTY, PS_FEASIBLE), # CPXMIP_FAIL_FEAS_NO_TREE
85117: (SS_FAILURE, SS_EMPTY, PS_UNKNOWN), # …_FAIL_INFEAS_NO_TREE
86118: (SS_UNKNOWN, SS_EMPTY, PS_UNBOUNDED), # CPXMIP_UNBOUNDED
87119: (SS_UNKNOWN, SS_EMPTY, PS_INF_OR_UNB), # CPXMIP_INForUNBD
88 # 120—126 seem irrelevant (CPXMIP_*_RELAXED_*).
89127: (SS_FEASIBLE, SS_EMPTY, PS_FEASIBLE), # CPXMIP_FEASIBLE
90128: (SS_OPTIMAL, SS_EMPTY, PS_FEASIBLE), # …_POPULATESOL_LIM ?
91129: (SS_OPTIMAL, SS_EMPTY, PS_FEASIBLE), # …_OPTIMAL_POPULATED ?
92130: (SS_OPTIMAL, SS_EMPTY, PS_FEASIBLE), # …_OPTIMAL_POPULATED_TOL ?
93131: (SS_FEASIBLE, SS_EMPTY, PS_FEASIBLE), # CPXMIP_DETTIME_LIM_FEAS
94132: (SS_PREMATURE, SS_EMPTY, PS_UNKNOWN), # CPXMIP_DETTIME_LIM_INFEAS
95}
98class CPLEXSolver(Solver):
99 """Interface to the CPLEX solver via its official Python interface.
101 .. note ::
102 Names are used instead of indices for identifying both variables and
103 constraints since indices can change if the CPLEX instance is modified.
104 """
106 # NOTE: When making changes, also see the section in _solve that tells CPLEX
107 # the problem type.
108 SUPPORTED = Specification(
109 objectives=[
110 AffineExpression,
111 QuadraticExpression],
112 constraints=[
113 DummyConstraint,
114 AffineConstraint,
115 SOCConstraint,
116 RSOCConstraint,
117 ConvexQuadraticConstraint])
119 NONCONVEX_QP = Specification(
120 objectives=[QuadraticExpression],
121 constraints=[DummyConstraint, AffineConstraint])
123 @classmethod
124 def supports(cls, footprint, explain=False):
125 """Implement :meth:`~.solver.Solver.supports`."""
126 result = Solver.supports(footprint, explain)
127 if not result or (explain and not result[0]):
128 return result
130 # Support QPs and MIQPs with a nonconvex objective.
131 # NOTE: SUPPORTED fully excludes nonconvex quadratic constraints. This
132 # further excludes QCQPs and MIQCQPs with a nonconvex objective.
133 # TODO: See which of the excluded cases can be supported as well.
134 if footprint.nonconvex_quadratic_objective \
135 and footprint not in cls.NONCONVEX_QP:
136 if explain:
137 return (False, "(MI)QCQPs with nonconvex objective.")
138 else:
139 return False
141 if footprint not in cls.SUPPORTED:
142 if explain:
143 return False, cls.SUPPORTED.mismatch_reason(footprint)
144 else:
145 return False
147 return (True, None) if explain else True
149 @classmethod
150 def default_penalty(cls):
151 """Implement :meth:`~.solver.Solver.default_penalty`."""
152 return 0.0 # Commercial solver.
154 @classmethod
155 def test_availability(cls):
156 """Implement :meth:`~.solver.Solver.test_availability`."""
157 cls.check_import("cplex")
159 @classmethod
160 def names(cls):
161 """Implement :meth:`~.solver.Solver.names`."""
162 return "cplex", "CPLEX", "IBM ILOG CPLEX Optimization Studio"
164 @classmethod
165 def is_free(cls):
166 """Implement :meth:`~.solver.Solver.is_free`."""
167 return False
169 CplexSOCC = namedtuple("CplexSOCC",
170 ("LHSVars", "RHSVar", "LHSCons", "RHSCon", "quadCon"))
172 CplexRSOCC = namedtuple("CplexRSOCC",
173 ("LHSVars", "RHSVars", "LHSCons", "RHSCons", "quadCon"))
175 def __init__(self, problem):
176 """Initialize a CPLEX solver interface.
178 :param ~picos.Problem problem: The problem to be solved.
179 """
180 super(CPLEXSolver, self).__init__(problem)
182 self._cplexVarName = dict()
183 """Maps PICOS variable indices to CPLEX variable names."""
185 self._cplexLinConNames = dict()
186 """Maps a PICOS (multidimensional) linear constraint to a collection of
187 CPLEX (scalar) linear constraint names."""
189 self._cplexQuadConName = dict()
190 """Maps a PICOS quadratic or conic quadratic constraint to a CPLEX
191 quadratic constraint name."""
193 self._cplexSOCC = dict()
194 """Maps a PICOS second order cone constraint to its CPLEX representation
195 involving auxiliary variables and constraints."""
197 self._cplexRSOCC = dict()
198 """Maps a PICOS rotated second order cone constraint to its CPLEX
199 representation involving auxiliary variables and constraints."""
201 self.nextConstraintID = 0
202 """Used to create unique names for constraints."""
204 def __del__(self):
205 if self.int is not None:
206 self.int.end()
208 def reset_problem(self):
209 """Implement :meth:`~.solver.Solver.reset_problem`."""
210 if self.int is not None:
211 self.int.end()
212 self.int = None
213 self._cplexVarName.clear()
214 self._cplexLinConNames.clear()
215 self._cplexQuadConName.clear()
216 self._cplexSOCC.clear()
217 self._cplexRSOCC.clear()
219 def _get_unique_constraint_id(self):
220 ID = self.nextConstraintID
221 self.nextConstraintID += 1
222 return ID
224 def _make_cplex_var_names(self, picosVar, localIndex=None):
225 """Make CPLEX variable names.
227 Converts a PICOS variable to a list of CPLEX variable names, each
228 corresponding to one scalar variable contained in the PICOS variable.
229 If localIndex is given, then only the name of the CPLEX variable
230 representing the scalar variable with that offset is returned.
231 The name format is "picosName[localIndex]".
232 """
233 # TODO: This function appears in multiple solvers, move it to the Solver
234 # base class as "_make_scalar_var_names".
235 if localIndex is not None:
236 return "{}[{}]".format(picosVar.name, localIndex)
237 else:
238 return [
239 self._make_cplex_var_names(picosVar, localIndex)
240 for localIndex in range(picosVar.dim)]
242 def _import_variable(self, picosVar):
243 import cplex
245 dim = picosVar.dim
247 # Create names.
248 names = self._make_cplex_var_names(picosVar)
250 # Retrieve types.
251 if isinstance(picosVar, CONTINUOUS_VARTYPES):
252 types = dim * self.int.variables.type.continuous
253 elif isinstance(picosVar, IntegerVariable):
254 types = dim * self.int.variables.type.integer
255 elif isinstance(picosVar, BinaryVariable):
256 types = dim * self.int.variables.type.binary
257 else:
258 assert False, "Unexpected variable type."
260 # Retrieve bounds.
261 lowerBounds = [-cplex.infinity]*dim
262 upperBounds = [cplex.infinity]*dim
263 lower, upper = picosVar.bound_dicts
264 for i, b in lower.items():
265 lowerBounds[i] = b
266 for i, b in upper.items():
267 upperBounds[i] = b
269 # Import variable.
270 # Note that CPLEX allows importing the objective function coefficients
271 # for the new variables here, but that is done later to streamline
272 # updates to the objective.
273 self.int.variables.add(
274 lb=lowerBounds, ub=upperBounds, types=types, names=names)
276 # Map PICOS indices to CPLEX names.
277 for localIndex in range(dim):
278 self._cplexVarName[picosVar.id_at(localIndex)] = names[localIndex]
280 if self._debug():
281 cplexVar = {"names": names, "types": types,
282 "lowerBounds": lowerBounds, "upperBounds": upperBounds}
283 self._debug(
284 "Variable imported: {} → {}".format(picosVar, cplexVar))
286 def _remove_variable(self, picosVar):
287 cplexVarNames = [self._cplexVarName.pop(picosVar.id_at(localIndex))
288 for localIndex in range(picosVar.dim)]
289 self.int.variables.delete(cplexVarNames)
291 def _affinexp_pic2cpl(self, picosExpression):
292 import cplex
293 for names, coefficients, constant in picosExpression.sparse_rows(
294 None, indexFunction=self._make_cplex_var_names):
295 yield cplex.SparsePair(ind=names, val=coefficients), constant
297 def _scalar_affinexp_pic2cpl(self, picosExpression):
298 assert len(picosExpression) == 1
299 return next(self._affinexp_pic2cpl(picosExpression))
301 def _quadexp_pic2cpl(self, picosExpression):
302 """Transform a quadratic expression from PICOS to CPLEX.
304 :returns: :class:`SparseTriple <cplex.SparseTriple>` mapping a pair of
305 CPLEX variable names to scalar constants.
306 """
307 import cplex
309 assert isinstance(picosExpression, QuadraticExpression)
311 cplexI, cplexJ, cplexV = [], [], []
312 for (picosVar1, picosVar2), picosCoefficients \
313 in picosExpression._sparse_quads.items():
314 for sparseIndex in range(len(picosCoefficients)):
315 localVar1Index = picosCoefficients.I[sparseIndex]
316 localVar2Index = picosCoefficients.J[sparseIndex]
317 localCoefficient = picosCoefficients.V[sparseIndex]
318 cplexI.append(self._cplexVarName[picosVar1.id + localVar1Index])
319 cplexJ.append(self._cplexVarName[picosVar2.id + localVar2Index])
320 cplexV.append(localCoefficient)
322 return cplex.SparseTriple(ind1=cplexI, ind2=cplexJ, val=cplexV)
324 def _import_linear_constraint(self, picosConstraint):
325 import cplex
327 assert isinstance(picosConstraint, AffineConstraint)
329 length = len(picosConstraint)
331 # Retrieve left hand side and right hand side expressions.
332 cplexLHS, cplexRHS = [], []
333 for names, coefficients, constant in picosConstraint.sparse_Ab_rows(
334 None, indexFunction=self._make_cplex_var_names):
335 cplexLHS.append(cplex.SparsePair(ind=names, val=coefficients))
336 cplexRHS.append(constant)
338 # Retrieve senses.
339 if picosConstraint.is_increasing():
340 senses = length * "L"
341 elif picosConstraint.is_decreasing():
342 senses = length * "G"
343 elif picosConstraint.is_equality():
344 senses = length * "E"
345 else:
346 assert False, "Unexpected constraint relation."
348 # Give unique names that are used to identify the constraint. This is
349 # necessary as constraint indices can change if the problem is modified.
350 conID = self._get_unique_constraint_id()
351 names = ["{}:{}".format(conID, localConstraintIndex)
352 for localConstraintIndex in range(length)]
354 if self._debug():
355 cplexConstraint = {"lin_expr": cplexLHS, "senses": senses,
356 "rhs": cplexRHS, "names": names}
357 self._debug(
358 "Linear constraint imported: {} → {}".format(
359 picosConstraint, cplexConstraint))
361 # Import the constraint.
362 self.int.linear_constraints.add(
363 lin_expr=cplexLHS, senses=senses, rhs=cplexRHS, names=names)
365 return names
367 def _import_quad_constraint(self, picosConstraint):
368 assert isinstance(picosConstraint, ConvexQuadraticConstraint)
370 # Retrieve
371 # - CPLEX' linear term, which is the linear term of the affine
372 # expression in the PICOS constraint, and
373 # - CPLEX' right hand side, which is the negated constant term of the
374 # affine expression in the PICOS constraint.
375 cplexLinear, cplexRHS = \
376 self._scalar_affinexp_pic2cpl(picosConstraint.le0.aff)
377 cplexRHS = -cplexRHS
379 # Retrieve CPLEX' quadratic term.
380 cplexQuad = self._quadexp_pic2cpl(picosConstraint.le0)
382 # Give a unique name that is used to identify the constraint. This is
383 # necessary as constraint indices can change if the problem is modified.
384 name = "{}:{}".format(self._get_unique_constraint_id(), 0)
386 if self._debug():
387 cplexConstraint = {"lin_expr": cplexLinear, "quad_expr": cplexQuad,
388 "rhs": cplexRHS, "name": name}
389 self._debug(
390 "Quadratic constraint imported: {} → {}".format(
391 picosConstraint, cplexConstraint))
393 # Import the constraint.
394 self.int.quadratic_constraints.add(lin_expr=cplexLinear,
395 quad_expr=cplexQuad, sense="L", rhs=cplexRHS, name=name)
397 return name
399 # TODO: Handle SOC → Quadratic via a reformulation.
400 def _import_socone_constraint(self, picosConstraint):
401 import cplex
403 assert isinstance(picosConstraint, SOCConstraint)
405 picosLHS = picosConstraint.ne
406 picosRHS = picosConstraint.ub
407 picosLHSLen = len(picosLHS)
409 # Make identifying names for the auxiliary variables and constraints.
410 conID = self._get_unique_constraint_id()
411 cplexLHSVars = ["{}:V{}".format(conID, i) for i in range(picosLHSLen)]
412 cplexRHSVar = "{}:V{}".format(conID, picosLHSLen)
413 cplexLHSCons = ["{}:C{}".format(conID, i) for i in range(picosLHSLen)]
414 cplexRHSCon = "{}:C{}".format(conID, picosLHSLen)
415 cplexQuadCon = "{}:C{}".format(conID, picosLHSLen + 1)
417 # Add auxiliary variables: One for every dimension of the left hand side
418 # of the PICOS constraint and one for its right hand side.
419 self.int.variables.add(
420 names=cplexLHSVars, lb=[-cplex.infinity] * picosLHSLen,
421 ub=[+cplex.infinity] * picosLHSLen,
422 types=self.int.variables.type.continuous * picosLHSLen)
423 self.int.variables.add(
424 names=[cplexRHSVar], lb=[0.0], ub=[+cplex.infinity],
425 types=self.int.variables.type.continuous)
427 # Add constraints that identify the left hand side CPLEX auxiliary
428 # variables with their slice of the PICOS left hand side expression.
429 cplexLHSConsLHSs = []
430 cplexLHSConsRHSs = []
431 for localConIndex, (localLinExp, localConstant) in \
432 enumerate(self._affinexp_pic2cpl(picosLHS)):
433 localConstant = -localConstant
434 localLinExp.ind.append(cplexLHSVars[localConIndex])
435 localLinExp.val.append(-1.0)
436 cplexLHSConsLHSs.append(localLinExp)
437 cplexLHSConsRHSs.append(localConstant)
438 self.int.linear_constraints.add(
439 names=cplexLHSCons, lin_expr=cplexLHSConsLHSs,
440 senses="E" * picosLHSLen, rhs=cplexLHSConsRHSs)
442 # Add a constraint that identifies the right hand side CPLEX auxiliary
443 # variable with the PICOS right hand side scalar expression.
444 cplexRHSConLHS, cplexRHSConRHS = \
445 self._scalar_affinexp_pic2cpl(-picosRHS)
446 cplexRHSConRHS = -cplexRHSConRHS
447 cplexRHSConLHS.ind.append(cplexRHSVar)
448 cplexRHSConLHS.val.append(1.0)
449 self.int.linear_constraints.add(
450 names=[cplexRHSCon], lin_expr=[cplexRHSConLHS],
451 senses="E", rhs=[cplexRHSConRHS])
453 # Add a quadratic constraint over the auxiliary variables that
454 # represents the PICOS second order cone constraint itself.
455 quadIndices = [cplexRHSVar] + list(cplexLHSVars)
456 quadExpr = cplex.SparseTriple(
457 ind1=quadIndices, ind2=quadIndices, val=[-1.0] + [1.0]*picosLHSLen)
458 self.int.quadratic_constraints.add(
459 name=cplexQuadCon, quad_expr=quadExpr, sense="L", rhs=0.0)
461 cplexMetaCon = self.CplexSOCC(LHSVars=cplexLHSVars, RHSVar=cplexRHSVar,
462 LHSCons=cplexLHSCons, RHSCon=cplexRHSCon, quadCon=cplexQuadCon)
464 if self._debug():
465 cplexCons = {
466 "LHSs of LHS auxiliary equalities": cplexLHSConsLHSs,
467 "RHSs of LHS auxiliary equalities": cplexLHSConsRHSs,
468 "LHS of RHS auxiliary equality": cplexRHSConLHS,
469 "RHS of RHS auxiliary equality": cplexRHSConRHS,
470 "Non-positive quadratic term": quadExpr}
471 self._debug(
472 "SOcone constraint imported: {} → {}, {}".format(
473 picosConstraint, cplexMetaCon, cplexCons))
475 return cplexMetaCon
477 # TODO: Handle RSOC → Quadratic via a reformulation.
478 def _import_rscone_constraint(self, picosConstraint):
479 import cplex
481 assert isinstance(picosConstraint, RSOCConstraint)
483 picosLHS = picosConstraint.ne
484 picosRHS1 = picosConstraint.ub1
485 picosRHS2 = picosConstraint.ub2
486 picosLHSLen = len(picosLHS)
488 # Make identifying names for the auxiliary variables and constraints.
489 conID = self._get_unique_constraint_id()
490 cplexLHSVars = ["{}:V{}".format(conID, i) for i in range(picosLHSLen)]
491 cplexRHSVars = ["{}:V{}".format(conID, picosLHSLen + i) for i in (0, 1)]
492 cplexLHSCons = ["{}:C{}".format(conID, i) for i in range(picosLHSLen)]
493 cplexRHSCons = ["{}:C{}".format(conID, picosLHSLen + i) for i in (0, 1)]
494 cplexQuadCon = "{}:C{}".format(conID, picosLHSLen + 2)
496 # Add auxiliary variables: One for every dimension of the left hand side
497 # of the PICOS constraint and two for its right hand side.
498 self.int.variables.add(
499 names=cplexLHSVars, lb=[-cplex.infinity] * picosLHSLen,
500 ub=[+cplex.infinity] * picosLHSLen,
501 types=self.int.variables.type.continuous * picosLHSLen)
502 self.int.variables.add(
503 names=cplexRHSVars, lb=[0.0, 0.0], ub=[+cplex.infinity] * 2,
504 types=self.int.variables.type.continuous * 2)
506 # Add constraints that identify the left hand side CPLEX auxiliary
507 # variables with their slice of the PICOS left hand side expression.
508 cplexLHSConsLHSs = []
509 cplexLHSConsRHSs = []
510 for localConIndex, (localLinExp, localConstant) in \
511 enumerate(self._affinexp_pic2cpl(picosLHS)):
512 localLinExp.ind.append(cplexLHSVars[localConIndex])
513 localLinExp.val.append(-1.0)
514 localConstant = -localConstant
515 cplexLHSConsLHSs.append(localLinExp)
516 cplexLHSConsRHSs.append(localConstant)
517 self.int.linear_constraints.add(
518 names=cplexLHSCons, lin_expr=cplexLHSConsLHSs,
519 senses="E" * picosLHSLen, rhs=cplexLHSConsRHSs)
521 # Add two constraints that identify the right hand side CPLEX auxiliary
522 # variables with the PICOS right hand side scalar expressions.
523 cplexRHSConsLHSs = []
524 cplexRHSConsRHSs = []
525 for picosRHS, cplexRHSVar in zip((picosRHS1, picosRHS2), cplexRHSVars):
526 linExp, constant = self._scalar_affinexp_pic2cpl(-picosRHS)
527 linExp.ind.append(cplexRHSVar)
528 linExp.val.append(1.0)
529 constant = -constant
530 cplexRHSConsLHSs.append(linExp)
531 cplexRHSConsRHSs.append(constant)
532 self.int.linear_constraints.add(
533 names=cplexRHSCons, lin_expr=cplexRHSConsLHSs,
534 senses="E" * 2, rhs=cplexRHSConsRHSs)
536 # Add a quadratic constraint over the auxiliary variables that
537 # represents the PICOS rotated second order cone constraint itself.
538 quadExpr = cplex.SparseTriple(
539 ind1=[cplexRHSVars[0]] + list(cplexLHSVars),
540 ind2=[cplexRHSVars[1]] + list(cplexLHSVars),
541 val=[-1.0] + [1.0] * picosLHSLen)
542 self.int.quadratic_constraints.add(
543 name=cplexQuadCon, quad_expr=quadExpr, sense="L", rhs=0.0)
545 cplexMetaCon = self.CplexRSOCC(
546 LHSVars=cplexLHSVars, RHSVars=cplexRHSVars, LHSCons=cplexLHSCons,
547 RHSCons=cplexRHSCons, quadCon=cplexQuadCon)
549 if self._debug():
550 cplexCons = {
551 "LHSs of LHS auxiliary equalities": cplexLHSConsLHSs,
552 "RHSs of LHS auxiliary equalities": cplexLHSConsRHSs,
553 "LHSs of RHS auxiliary equalities": cplexRHSConsLHSs,
554 "RHSs of RHS auxiliary equalities": cplexRHSConsRHSs,
555 "Non-positive quadratic term": quadExpr}
556 self._debug(
557 "RScone constraint imported: {} → {}, {}".format(
558 picosConstraint, cplexMetaCon, cplexCons))
560 return cplexMetaCon
562 def _import_constraint(self, picosConstraint):
563 # Import constraint based on type and keep track of the corresponding
564 # CPLEX constraint and auxiliary variable names.
565 if isinstance(picosConstraint, AffineConstraint):
566 self._cplexLinConNames[picosConstraint] = \
567 self._import_linear_constraint(picosConstraint)
568 elif isinstance(picosConstraint, ConvexQuadraticConstraint):
569 self._cplexQuadConName[picosConstraint] = \
570 self._import_quad_constraint(picosConstraint)
571 elif isinstance(picosConstraint, SOCConstraint):
572 self._cplexSOCC[picosConstraint] = \
573 self._import_socone_constraint(picosConstraint)
574 elif isinstance(picosConstraint, RSOCConstraint):
575 self._cplexRSOCC[picosConstraint] = \
576 self._import_rscone_constraint(picosConstraint)
577 else:
578 assert isinstance(picosConstraint, DummyConstraint), \
579 "Unexpected constraint type: {}".format(
580 picosConstraint.__class__.__name__)
582 def _remove_constraint(self, picosConstraint):
583 if isinstance(picosConstraint, AffineConstraint):
584 self.int.linear_constraints.delete(
585 self._cplexLinConNames.pop(picosConstraint))
586 elif isinstance(picosConstraint, ConvexQuadraticConstraint):
587 self.int.quadratic_constraints.delete(
588 self._cplexQuadConName.pop(picosConstraint))
589 elif isinstance(picosConstraint, SOCConstraint):
590 c = self._cplexSOCC.pop(picosConstraint)
591 self.int.linear_constraints.delete(c.cplexLHSCons + [c.cplexRHSCon])
592 self.int.quadratic_constraints.delete(c.cplexQuadCon)
593 self.int.variables.delete(c.cplexLHSVars + [c.cplexRHSVar])
594 elif isinstance(picosConstraint, RSOCConstraint):
595 c = self._cplexRSOCC.pop(picosConstraint)
596 self.int.linear_constraints.delete(c.cplexLHSCons + c.cplexRHSCons)
597 self.int.quadratic_constraints.delete(c.cplexQuadCon)
598 self.int.variables.delete(c.cplexLHSVars + c.cplexRHSVars)
599 else:
600 assert isinstance(picosConstraint, DummyConstraint), \
601 "Unexpected constraint type: {}".format(
602 picosConstraint.__class__.__name__)
604 def _import_affine_objective(self, picosExpression):
605 assert isinstance(picosExpression, AffineExpression)
607 if picosExpression._constant_coef:
608 offset = picosExpression._constant_coef[0]
610 self.int.objective.set_offset(offset)
612 if self._debug():
613 self._debug("Constant part of objective imported: {} → {}"
614 .format(picosExpression.cst.string, offset))
616 cplexExpression = []
617 for picosVar, picosCoefficient in picosExpression._linear_coefs.items():
618 assert picosCoefficient.size[0] == 1
620 for localIndex in range(picosVar.dim):
621 cplexCoefficient = picosCoefficient[localIndex]
622 if not cplexCoefficient:
623 continue
624 picosIndex = picosVar.id + localIndex
625 cplexName = self._cplexVarName[picosIndex]
626 cplexExpression.append((cplexName, cplexCoefficient))
628 if cplexExpression:
629 self.int.objective.set_linear(cplexExpression)
631 if self._debug():
632 self._debug("Linear part of objective imported: {} → {}"
633 .format(picosExpression.lin.string, cplexExpression))
635 def _reset_affine_objective(self):
636 self.int.objective.set_offset(0.0)
638 linear = self.int.objective.get_linear()
639 if any(linear):
640 self.int.objective.set_linear(
641 [(cplexVarIndex, 0.0) for cplexVarIndex, coefficient
642 in enumerate(linear) if coefficient])
644 def _import_quadratic_objective(self, picosExpression):
645 assert isinstance(picosExpression, QuadraticExpression)
647 # Import affine part of objective function.
648 self._import_affine_objective(picosExpression.aff)
650 # Import quadratic part of objective function.
651 cplexQuadExpression = self._quadexp_pic2cpl(picosExpression)
652 cplexQuadCoefficients = zip(
653 cplexQuadExpression.ind1, cplexQuadExpression.ind2,
654 [2.0 * coefficient for coefficient in cplexQuadExpression.val])
655 self.int.objective.set_quadratic_coefficients(cplexQuadCoefficients)
657 self._debug("Quadratic part of objective imported: {} → {}"
658 .format(picosExpression.quad.string, cplexQuadCoefficients))
660 def _reset_quadratic_objective(self):
661 quadratics = self.int.objective.get_quadratic()
662 if quadratics:
663 self.int.objective.set_quadratic(
664 [(sparsePair.ind, [0]*len(sparsePair.ind))
665 for sparsePair in quadratics])
667 def _import_objective(self):
668 picosSense, picosObjective = self.ext.no
670 # Import objective sense.
671 if picosSense == "min":
672 cplexSense = self.int.objective.sense.minimize
673 else:
674 assert picosSense == "max"
675 cplexSense = self.int.objective.sense.maximize
676 self.int.objective.set_sense(cplexSense)
678 # Import objective function.
679 if isinstance(picosObjective, AffineExpression):
680 self._import_affine_objective(picosObjective)
681 else:
682 assert isinstance(picosObjective, QuadraticExpression)
683 self._import_quadratic_objective(picosObjective)
685 def _reset_objective(self):
686 self._reset_affine_objective()
687 self._reset_quadratic_objective()
689 def _import_problem(self):
690 import cplex
692 # Create a problem instance.
693 self.int = cplex.Cplex()
695 # Import variables.
696 for variable in self.ext.variables.values():
697 self._import_variable(variable)
699 # Import constraints.
700 for constraint in self.ext.constraints.values():
701 self._import_constraint(constraint)
703 # Set objective.
704 self._import_objective()
706 def _update_problem(self):
707 for oldConstraint in self._removed_constraints():
708 self._remove_constraint(oldConstraint)
710 for oldVariable in self._removed_variables():
711 self._remove_variable(oldVariable)
713 for newVariable in self._new_variables():
714 self._import_variable(newVariable)
716 for newConstraint in self._new_constraints():
717 self._import_constraint(newConstraint)
719 if self._objective_has_changed():
720 self._reset_objective()
721 self._import_objective()
723 def _solve(self):
724 import cplex
726 # Reset options.
727 self.int.parameters.reset()
729 o = self.ext.options
730 p = self.int.parameters
732 continuous = self.ext.is_continuous()
734 # TODO: Allow querying self.ext.objective directly.
735 nonconvex_quad_obj = self.ext.footprint.nonconvex_quadratic_objective
737 # verbosity
738 verbosity = self.verbosity()
739 if verbosity <= 0:
740 # Note that this behaviour disables warning even with a verbosity of
741 # zero but this is still better than having verbose output for every
742 # option that is set.
743 self.int.set_results_stream(None)
744 else:
745 p.barrier.display.set(min(2, verbosity))
746 p.conflict.display.set(min(2, verbosity))
747 p.mip.display.set(min(5, verbosity))
748 p.sifting.display.set(min(2, verbosity))
749 p.simplex.display.set(min(2, verbosity))
750 p.tune.display.set(min(3, verbosity))
751 self.int.set_error_stream(None) # Already handled as exceptions.
753 # abs_prim_fsb_tol
754 if o.abs_prim_fsb_tol is not None:
755 p.simplex.tolerances.feasibility.set(o.abs_prim_fsb_tol)
757 # abs_dual_fsb_tol
758 if o.abs_dual_fsb_tol is not None:
759 p.simplex.tolerances.optimality.set(o.abs_dual_fsb_tol)
761 # rel_prim_fsb_tol, rel_dual_fsb_tol, rel_ipm_opt_tol
762 convergenceTols = [tol for tol in (o.rel_prim_fsb_tol,
763 o.rel_dual_fsb_tol, o.rel_ipm_opt_tol) if tol is not None]
764 if convergenceTols:
765 convergenceTol = min(convergenceTols)
766 p.barrier.convergetol.set(convergenceTol)
767 p.barrier.qcpconvergetol.set(convergenceTol)
769 # abs_bnb_opt_tol
770 if o.abs_bnb_opt_tol is not None:
771 p.mip.tolerances.absmipgap.set(o.abs_bnb_opt_tol)
773 # rel_bnb_opt_tol
774 if o.rel_bnb_opt_tol is not None:
775 p.mip.tolerances.mipgap.set(o.rel_bnb_opt_tol)
777 # integrality_tol
778 if o.integrality_tol is not None:
779 p.mip.tolerances.integrality.set(o.integrality_tol)
781 # markowitz_tol
782 if o.markowitz_tol is not None:
783 p.simplex.tolerances.markowitz.set(o.markowitz_tol)
785 # max_iterations
786 if o.max_iterations is not None:
787 maxit = o.max_iterations
788 p.barrier.limits.iteration.set(maxit)
789 p.simplex.limits.iterations.set(maxit)
791 _lpm = {"interior": 4, "psimplex": 1, "dsimplex": 2}
793 # lp_node_method
794 if o.lp_node_method is not None:
795 assert o.lp_node_method in _lpm, "Unexpected lp_node_method value."
796 p.mip.strategy.subalgorithm.set(_lpm[o.lp_node_method])
798 # lp_root_method
799 if o.lp_root_method is not None:
800 assert o.lp_root_method in _lpm, "Unexpected lp_root_method value."
801 p.lpmethod.set(_lpm[o.lp_root_method])
803 # timelimit
804 if o.timelimit is not None:
805 p.timelimit.set(o.timelimit)
807 # treememory
808 if o.treememory is not None:
809 p.mip.limits.treememory.set(o.treememory)
811 # Handle option conflict between "max_fsb_nodes" and "pool_size".
812 if o.max_fsb_nodes is not None \
813 and o.pool_size is not None:
814 raise ConflictingOptionsError("The options 'max_fsb_nodes' and "
815 "'pool_size' cannot be used in conjunction.")
817 # max_fsb_nodes
818 if o.max_fsb_nodes is not None:
819 p.mip.limits.solutions.set(o.max_fsb_nodes)
821 # pool_size
822 if o.pool_size is not None:
823 if continuous:
824 raise UnsupportedOptionError("The option 'pool_size' can only "
825 "be used with mixed integer problems.")
826 maxNumSolutions = max(1, int(o.pool_size))
827 p.mip.limits.populate.set(maxNumSolutions)
828 else:
829 maxNumSolutions = 1
831 # pool_relgap
832 if o.pool_rel_gap is not None:
833 if o.pool_size is None:
834 raise DependentOptionError("The option 'pool_rel_gap' requires "
835 "the option 'pool_size'.")
836 p.mip.pool.relgap.set(o.pool_rel_gap)
838 # pool_abs_gap
839 if o.pool_abs_gap is not None:
840 if o.pool_size is None:
841 raise DependentOptionError("The option 'pool_abs_gap' requires "
842 "the option 'pool_size'.")
843 p.mip.pool.absgap.set(o.pool_abs_gap)
845 # hotstart
846 if o.hotstart:
847 names, values = [], []
848 for picosVar in self.ext.variables.values():
849 if picosVar.valued:
850 for localIndex in range(picosVar.dim):
851 name = self._cplexVarName[picosVar.id_at(localIndex)]
852 names.append(name)
853 values.append(picosVar.internal_value[localIndex])
854 if names:
855 self.int.MIP_starts.add(
856 cplex.SparsePair(ind=names, val=values),
857 self.int.MIP_starts.effort_level.repair)
859 # Set the optimality target now so that cplex_params may overwrite it.
860 # This allows solving QPs and MIQPs with a nonconvex objective.
861 if nonconvex_quad_obj:
862 p.optimalitytarget.set(3)
864 # Handle CPLEX-specific options.
865 for key, value in o.cplex_params.items():
866 try:
867 parameter = getattr(self.int.parameters, key)
868 except AttributeError as error:
869 self._handle_bad_solver_specific_option_key(key, error)
871 try:
872 parameter.set(value)
873 except cplex.exceptions.errors.CplexError as error:
874 self._handle_bad_solver_specific_option_value(key, value, error)
876 # Handle options "cplex_upr_bnd_limit", "cplex_lwr_bnd_limit" and
877 # "cplex_bnd_monitor" via a CPLEX callback handler.
878 callback = None
879 if o.cplex_upr_bnd_limit or o.cplex_lwr_bnd_limit \
880 or o.cplex_bnd_monitor:
881 from cplex.callbacks import MIPInfoCallback
883 class PicosInfoCallback(MIPInfoCallback):
884 def __call__(self):
885 v1 = self.get_incumbent_objective_value()
886 v2 = self.get_best_objective_value()
887 ub = max(v1, v2)
888 lb = min(v1, v2)
889 if self.bounds is not None:
890 elapsedTime = time.time() - self.startTime
891 self.bounds.append((elapsedTime, lb, ub))
892 if self.lbound is not None and lb >= self.lbound:
893 self.printer("The specified lower bound was reached, "
894 "so PICOS will ask CPLEX to stop the search.")
895 self.abort()
896 if self.ubound is not None and ub <= self.ubound:
897 self.printer("The specified upper bound was reached, "
898 "so PICOS will ask CPLEX to stop the search.")
899 self.abort()
901 # Register the callback handler with CPLEX.
902 callback = self.int.register_callback(PicosInfoCallback)
904 # Pass parameters to the callback handler. Note that
905 # callback.startTime will be set just before optimization begins.
906 callback.printer = self._verbose
907 callback.ubound = o.cplex_upr_bnd_limit
908 callback.lbound = o.cplex_lwr_bnd_limit
909 callback.bounds = [] if o.cplex_bnd_monitor else None
911 # Inform CPLEX about the problem type.
912 # This seems necessary, as otherwise LP can get solved as MIP, producing
913 # misleading status output (e.g. "not integer feasible").
914 conTypes = set(c.__class__ for c in self.ext.constraints.values())
915 quadObj = isinstance(self.ext.no.function, QuadraticExpression)
916 cplexTypes = self.int.problem_type
918 if quadObj:
919 if conTypes.issubset(set([DummyConstraint, AffineConstraint])):
920 cplexType = cplexTypes.QP if continuous else cplexTypes.MIQP
921 else:
922 # Assume quadratic constraint types.
923 cplexType = cplexTypes.QCP if continuous else cplexTypes.MIQCP
924 else:
925 if conTypes.issubset(set([DummyConstraint, AffineConstraint])):
926 cplexType = cplexTypes.LP if continuous else cplexTypes.MILP
927 else:
928 # Assume quadratic constraint types.
929 cplexType = cplexTypes.QCP if continuous else cplexTypes.MIQCP
931 # Silence a warning explaining that optimality target 3 changes the
932 # problem type from QP to MIQP by doing so manually.
933 if nonconvex_quad_obj:
934 # Enforce consistency with CPLEXSolver.supports.
935 assert cplexType in (cplexTypes.QP, cplexTypes.MIQP)
937 if p.optimalitytarget.get() == 3: # User might have changed it.
938 cplexType = cplexTypes.MIQP
940 if cplexType is not None:
941 self.int.set_problem_type(cplexType)
943 # Attempt to solve the problem.
944 if callback:
945 callback.startTime = time.time()
946 with self._header(), self._stopwatch():
947 try:
948 if maxNumSolutions > 1:
949 self.int.populate_solution_pool()
950 numSolutions = self.int.solution.pool.get_num()
951 else:
952 self.int.solve()
953 numSolutions = 1
954 except cplex.exceptions.errors.CplexSolverError as error:
955 if error.args[2] == 5002:
956 self._handle_continuous_nonconvex_error(error)
957 else:
958 raise
960 solutions = []
961 for solutionNum in range(numSolutions):
962 # Retrieve primals.
963 primals = {}
964 if o.primals is not False:
965 for picosVar in self.ext.variables.values():
966 try:
967 cplexNames = []
969 for localIndex in range(picosVar.dim):
970 picosIndex = picosVar.id + localIndex
971 cplexNames.append(self._cplexVarName[picosIndex])
972 if maxNumSolutions > 1:
973 value = self.int.solution.pool.get_values(
974 solutionNum, cplexNames)
975 else:
976 value = self.int.solution.get_values(cplexNames)
977 primals[picosVar] = value
978 except cplex.exceptions.errors.CplexSolverError:
979 primals[picosVar] = None
981 # Retrieve duals.
982 duals = {}
983 if o.duals is not False and continuous:
984 assert maxNumSolutions == 1
986 for picosCon in self.ext.constraints.values():
987 if isinstance(picosCon, DummyConstraint):
988 duals[picosCon] = cvxopt.spmatrix(
989 [], [], [], picosCon.size)
990 continue
992 try:
993 if isinstance(picosCon, AffineConstraint):
994 cplexCons = self._cplexLinConNames[picosCon]
995 values = self.int.solution.get_dual_values(
996 cplexCons)
997 picosDual = cvxopt.matrix(values, picosCon.size)
999 # Flip sign based on constraint relation.
1000 if not picosCon.is_increasing():
1001 picosDual = -picosDual
1002 elif isinstance(picosCon, SOCConstraint):
1003 cplexMetaCon = self._cplexSOCC[picosCon]
1004 lb = self.int.solution.get_dual_values(
1005 cplexMetaCon.RHSCon)
1006 z = self.int.solution.get_dual_values(
1007 list(cplexMetaCon.LHSCons))
1008 picosDual = -cvxopt.matrix([-lb] + z)
1009 elif isinstance(picosCon, RSOCConstraint):
1010 cplexMetaCon = self._cplexRSOCC[picosCon]
1011 ab = [-x for x in self.int.solution.get_dual_values(
1012 list(cplexMetaCon.RHSCons))]
1013 z = self.int.solution.get_dual_values(
1014 list(cplexMetaCon.LHSCons))
1015 picosDual = -cvxopt.matrix(ab + z)
1016 elif isinstance(picosCon, ConvexQuadraticConstraint):
1017 picosDual = None
1018 else:
1019 assert False, "Unexpected constraint type."
1021 # Flip sign based on objective sense.
1022 if picosDual and self.ext.no.direction == "min":
1023 picosDual = -picosDual
1024 except cplex.exceptions.errors.CplexSolverError:
1025 duals[picosCon] = None
1026 else:
1027 duals[picosCon] = picosDual
1029 # Retrieve objective value.
1030 try:
1031 if quadObj:
1032 # FIXME: Retrieval of QP and MIQP objective value appears to
1033 # miss the quadratic part.
1034 value = None
1035 elif maxNumSolutions > 1:
1036 value = self.int.solution.pool.get_objective_value(
1037 solutionNum)
1038 else:
1039 value = self.int.solution.get_objective_value()
1040 except cplex.exceptions.errors.CplexSolverError:
1041 value = None
1043 # Retrieve solution status.
1044 code = self.int.solution.get_status()
1045 if code in CPLEX_STATUS_CODES:
1046 prmlStatus, dualStatus, probStatus = CPLEX_STATUS_CODES[code]
1047 else:
1048 prmlStatus = SS_UNKNOWN
1049 dualStatus = SS_UNKNOWN
1050 probStatus = PS_UNKNOWN
1052 info = {}
1053 if o.cplex_bnd_monitor:
1054 info["bounds_monitor"] = callback.bounds
1056 solutions.append(self._make_solution(value, primals, duals,
1057 prmlStatus, dualStatus, probStatus, info))
1059 if maxNumSolutions > 1:
1060 return solutions
1061 else:
1062 assert len(solutions) == 1
1063 return solutions[0]
1066# --------------------------------------
1067__all__ = api_end(_API_START, globals())