1# ___________________________________________________________________________ 2# 3# Pyomo: Python Optimization Modeling Objects 4# Copyright 2017 National Technology and Engineering Solutions of Sandia, LLC 5# Under the terms of Contract DE-NA0003525 with National Technology and 6# Engineering Solutions of Sandia, LLC, the U.S. Government retains certain 7# rights in this software. 8# This software is distributed under the 3-clause BSD License. 9# ___________________________________________________________________________ 10 11"""Cut generation.""" 12from __future__ import division 13import logging 14from math import copysign 15from pyomo.core import minimize, value 16from pyomo.core.expr import current as EXPR 17from pyomo.contrib.gdpopt.util import identify_variables, time_code 18from pyomo.contrib.mcpp.pyomo_mcpp import McCormick as mc, MCPP_Error 19 20logger = logging.getLogger('pyomo.contrib.mindtpy') 21 22 23def add_oa_cuts(target_model, dual_values, solve_data, config, 24 cb_opt=None, 25 linearize_active=True, 26 linearize_violated=True): 27 """ 28 Linearizes nonlinear constraints; modifies the model to include the OA cuts 29 For nonconvex problems, turn on 'config.add_slack'. Slack variables will 30 always be used for nonlinear equality constraints. 31 Parameters 32 ---------- 33 target_model: 34 this is the MIP/MILP model for the OA algorithm; we want to add the OA cuts to 'target_model' 35 dual_values: 36 contains the value of the duals for each constraint 37 solve_data: MindtPy Data Container 38 data container that holds solve-instance data 39 config: ConfigBlock 40 contains the specific configurations for the algorithm 41 linearize_active: bool, optional 42 this parameter acts as a Boolean flag that signals whether the linearized constraint is active 43 linearize_violated: bool, optional 44 this parameter acts as a Boolean flag that signals whether the nonlinear constraint represented by the 45 linearized constraint has been violated 46 """ 47 with time_code(solve_data.timing, 'OA cut generation'): 48 for index, constr in enumerate(target_model.MindtPy_utils.constraint_list): 49 # TODO: here the index is correlated to the duals, try if this can be fixed when temp duals are removed. 50 if constr.body.polynomial_degree() in {0, 1}: 51 continue 52 53 constr_vars = list(identify_variables(constr.body)) 54 jacs = solve_data.jacobians 55 56 # Equality constraint (makes the problem nonconvex) 57 if constr.has_ub() and constr.has_lb() and value(constr.lower) == value(constr.upper) and config.equality_relaxation: 58 sign_adjust = -1 if solve_data.objective_sense == minimize else 1 59 rhs = constr.lower 60 if config.add_slack: 61 slack_var = target_model.MindtPy_utils.cuts.slack_vars.add() 62 target_model.MindtPy_utils.cuts.oa_cuts.add( 63 expr=copysign(1, sign_adjust * dual_values[index]) 64 * (sum(value(jacs[constr][var]) * (var - value(var)) 65 for var in EXPR.identify_variables(constr.body)) 66 + value(constr.body) - rhs) 67 - (slack_var if config.add_slack else 0) <= 0) 68 if config.single_tree and config.mip_solver == 'gurobi_persistent' and solve_data.mip_iter > 0 and cb_opt is not None: 69 cb_opt.cbLazy( 70 target_model.MindtPy_utils.cuts.oa_cuts[len(target_model.MindtPy_utils.cuts.oa_cuts)]) 71 72 else: # Inequality constraint (possibly two-sided) 73 if (constr.has_ub() 74 and (linearize_active and abs(constr.uslack()) < config.zero_tolerance) 75 or (linearize_violated and constr.uslack() < 0) 76 or (config.linearize_inactive and constr.uslack() > 0)) or (constr.name == 'MindtPy_utils.objective_constr' and constr.has_ub()): 77 # always add the linearization for the epigraph of the objective 78 if config.add_slack: 79 slack_var = target_model.MindtPy_utils.cuts.slack_vars.add() 80 81 target_model.MindtPy_utils.cuts.oa_cuts.add( 82 expr=(sum(value(jacs[constr][var])*(var - var.value) 83 for var in constr_vars) + value(constr.body) 84 - (slack_var if config.add_slack else 0) 85 <= value(constr.upper)) 86 ) 87 if config.single_tree and config.mip_solver == 'gurobi_persistent' and solve_data.mip_iter > 0 and cb_opt is not None: 88 cb_opt.cbLazy( 89 target_model.MindtPy_utils.cuts.oa_cuts[len(target_model.MindtPy_utils.cuts.oa_cuts)]) 90 91 if (constr.has_lb() 92 and (linearize_active and abs(constr.lslack()) < config.zero_tolerance) 93 or (linearize_violated and constr.lslack() < 0) 94 or (config.linearize_inactive and constr.lslack() > 0)) or (constr.name == 'MindtPy_utils.objective_constr' and constr.has_lb()): 95 if config.add_slack: 96 slack_var = target_model.MindtPy_utils.cuts.slack_vars.add() 97 98 target_model.MindtPy_utils.cuts.oa_cuts.add( 99 expr=(sum(value(jacs[constr][var])*(var - var.value) 100 for var in constr_vars) + value(constr.body) 101 + (slack_var if config.add_slack else 0) 102 >= value(constr.lower)) 103 ) 104 if config.single_tree and config.mip_solver == 'gurobi_persistent' and solve_data.mip_iter > 0 and cb_opt is not None: 105 cb_opt.cbLazy( 106 target_model.MindtPy_utils.cuts.oa_cuts[len(target_model.MindtPy_utils.cuts.oa_cuts)]) 107 108 109def add_ecp_cuts(target_model, solve_data, config, 110 linearize_active=True, 111 linearize_violated=True): 112 """ 113 Linearizes nonlinear constraints. Adds the cuts for the ECP method. 114 115 For nonconvex problems, turn on 'config.add_slack'. Slack variables will 116 always be used for nonlinear equality constraints. 117 118 Parameters 119 ---------- 120 target_model: 121 this is the MIP/MILP model for the OA algorithm; we want to add the OA cuts to 'target_model' 122 solve_data: MindtPy Data Container 123 data container that holds solve-instance data 124 config: ConfigBlock 125 contains the specific configurations for the algorithm 126 linearize_active: bool, optional 127 this parameter acts as a Boolean flag that signals whether the linearized constraint is active 128 linearize_violated: bool, optional 129 this parameter acts as a Boolean flag that signals whether the nonlinear constraint represented by the 130 linearized constraint has been violated 131 """ 132 with time_code(solve_data.timing, 'ECP cut generation'): 133 for constr in target_model.MindtPy_utils.nonlinear_constraint_list: 134 constr_vars = list(identify_variables(constr.body)) 135 jacs = solve_data.jacobians 136 137 if constr.has_lb() and constr.has_ub(): 138 config.logger.warning( 139 'constraint {} has both a lower ' 140 'and upper bound.' 141 '\n'.format( 142 constr)) 143 continue 144 if constr.has_ub(): 145 try: 146 upper_slack = constr.uslack() 147 except (ValueError, OverflowError): 148 config.logger.warning( 149 'constraint {} has caused either a ' 150 'ValueError or OverflowError.' 151 '\n'.format( 152 constr)) 153 continue 154 if (linearize_active and abs(upper_slack) < config.ecp_tolerance) \ 155 or (linearize_violated and upper_slack < 0) \ 156 or (config.linearize_inactive and upper_slack > 0): 157 if config.add_slack: 158 slack_var = target_model.MindtPy_utils.cuts.slack_vars.add() 159 160 target_model.MindtPy_utils.cuts.ecp_cuts.add( 161 expr=(sum(value(jacs[constr][var])*(var - var.value) 162 for var in constr_vars) 163 - (slack_var if config.add_slack else 0) 164 <= upper_slack) 165 ) 166 167 if constr.has_lb(): 168 try: 169 lower_slack = constr.lslack() 170 except (ValueError, OverflowError): 171 config.logger.warning( 172 'constraint {} has caused either a ' 173 'ValueError or OverflowError.' 174 '\n'.format( 175 constr)) 176 continue 177 if (linearize_active and abs(lower_slack) < config.ecp_tolerance) \ 178 or (linearize_violated and lower_slack < 0) \ 179 or (config.linearize_inactive and lower_slack > 0): 180 if config.add_slack: 181 slack_var = target_model.MindtPy_utils.cuts.slack_vars.add() 182 183 target_model.MindtPy_utils.cuts.ecp_cuts.add( 184 expr=(sum(value(jacs[constr][var])*(var - var.value) 185 for var in constr_vars) 186 + (slack_var if config.add_slack else 0) 187 >= -lower_slack) 188 ) 189 190 191def add_no_good_cuts(var_values, solve_data, config, feasible=False): 192 """ 193 Adds no-good cuts; modifies the model to include no-good cuts 194 This adds an no-good cuts to the no_good_cuts ConstraintList, which is not activated by default. 195 However, it may be activated as needed in certain situations or for certain values of option flags. 196 197 Parameters 198 ---------- 199 var_values: list 200 values of the current variables, used to generate the cut 201 solve_data: MindtPy Data Container 202 data container that holds solve-instance data 203 config: ConfigBlock 204 contains the specific configurations for the algorithm 205 feasible: bool, optional 206 boolean indicating if integer combination yields a feasible or infeasible NLP 207 """ 208 if not config.add_no_good_cuts: 209 return 210 with time_code(solve_data.timing, 'no_good cut generation'): 211 212 config.logger.info('Adding no_good cuts') 213 214 m = solve_data.mip 215 MindtPy = m.MindtPy_utils 216 int_tol = config.integer_tolerance 217 218 binary_vars = [v for v in MindtPy.variable_list if v.is_binary()] 219 220 # copy variable values over 221 for var, val in zip(MindtPy.variable_list, var_values): 222 if not var.is_binary(): 223 continue 224 var.value = val 225 226 # check to make sure that binary variables are all 0 or 1 227 for v in binary_vars: 228 if value(abs(v - 1)) > int_tol and value(abs(v)) > int_tol: 229 raise ValueError( 230 'Binary {} = {} is not 0 or 1'.format(v.name, value(v))) 231 232 if not binary_vars: # if no binary variables, skip 233 return 234 235 int_cut = (sum(1 - v for v in binary_vars 236 if value(abs(v - 1)) <= int_tol) + 237 sum(v for v in binary_vars 238 if value(abs(v)) <= int_tol) >= 1) 239 240 MindtPy.cuts.no_good_cuts.add(expr=int_cut) 241 242 243def add_affine_cuts(solve_data, config): 244 """ 245 Adds affine cuts using MCPP; modifies the model to include affine cuts 246 247 Parameters 248 ---------- 249 solve_data: MindtPy Data Container 250 data container that holds solve-instance data 251 config: ConfigBlock 252 contains the specific configurations for the algorithm 253 """ 254 with time_code(solve_data.timing, 'Affine cut generation'): 255 m = solve_data.mip 256 config.logger.info('Adding affine cuts') 257 counter = 0 258 259 for constr in m.MindtPy_utils.nonlinear_constraint_list: 260 vars_in_constr = list( 261 identify_variables(constr.body)) 262 if any(var.value is None for var in vars_in_constr): 263 continue # a variable has no values 264 265 # mcpp stuff 266 try: 267 mc_eqn = mc(constr.body) 268 except MCPP_Error as e: 269 config.logger.debug( 270 'Skipping constraint %s due to MCPP error %s' % (constr.name, str(e))) 271 continue # skip to the next constraint 272 273 ccSlope = mc_eqn.subcc() 274 cvSlope = mc_eqn.subcv() 275 ccStart = mc_eqn.concave() 276 cvStart = mc_eqn.convex() 277 278 # check if the value of ccSlope and cvSlope is not Nan or inf. If so, we skip this. 279 concave_cut_valid = True 280 convex_cut_valid = True 281 for var in vars_in_constr: 282 if not var.fixed: 283 if ccSlope[var] == float('nan') or ccSlope[var] == float('inf'): 284 concave_cut_valid = False 285 if cvSlope[var] == float('nan') or cvSlope[var] == float('inf'): 286 convex_cut_valid = False 287 # check if the value of ccSlope and cvSlope all equals zero. if so, we skip this. 288 if not any(list(ccSlope.values())): 289 concave_cut_valid = False 290 if not any(list(cvSlope.values())): 291 convex_cut_valid = False 292 if ccStart == float('nan') or ccStart == float('inf'): 293 concave_cut_valid = False 294 if cvStart == float('nan') or cvStart == float('inf'): 295 convex_cut_valid = False 296 if not (concave_cut_valid or convex_cut_valid): 297 continue 298 299 ub_int = min(value(constr.upper), mc_eqn.upper() 300 ) if constr.has_ub() else mc_eqn.upper() 301 lb_int = max(value(constr.lower), mc_eqn.lower() 302 ) if constr.has_lb() else mc_eqn.lower() 303 304 aff_cuts = m.MindtPy_utils.cuts.aff_cuts 305 if concave_cut_valid: 306 concave_cut = sum(ccSlope[var] * (var - var.value) 307 for var in vars_in_constr 308 if not var.fixed) + ccStart >= lb_int 309 aff_cuts.add(expr=concave_cut) 310 counter += 1 311 if convex_cut_valid: 312 convex_cut = sum(cvSlope[var] * (var - var.value) 313 for var in vars_in_constr 314 if not var.fixed) + cvStart <= ub_int 315 aff_cuts.add(expr=convex_cut) 316 counter += 1 317 318 config.logger.info('Added %s affine cuts' % counter) 319