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"""Solution of NLP subproblems.""" 12from __future__ import division 13import logging 14from pyomo.common.collections import ComponentMap 15from pyomo.contrib.mindtpy.cut_generation import (add_oa_cuts, 16 add_no_good_cuts, add_affine_cuts) 17from pyomo.contrib.mindtpy.util import add_feas_slacks, set_solver_options 18from pyomo.contrib.gdpopt.util import copy_var_list_values, get_main_elapsed_time, time_code 19from pyomo.core import (Constraint, Objective, 20 TransformationFactory, minimize, value) 21from pyomo.opt import TerminationCondition as tc 22from pyomo.opt import SolverFactory, SolverResults, SolverStatus 23from pyomo.contrib.gdpopt.util import SuppressInfeasibleWarning 24 25logger = logging.getLogger('pyomo.contrib.mindtpy') 26 27 28def solve_subproblem(solve_data, config): 29 """ 30 Solves the Fixed-NLP (with fixed integers) 31 32 This function sets up the 'fixed_nlp' by fixing binaries, sets continuous variables to their intial var values, 33 precomputes dual values, deactivates trivial constraints, and then solves NLP model. 34 35 Parameters 36 ---------- 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 42 Returns 43 ------- 44 fixed_nlp: Pyomo model 45 integer-variable-fixed NLP model 46 results: Pyomo results object 47 result from solving the Fixed-NLP 48 """ 49 50 fixed_nlp = solve_data.working_model.clone() 51 MindtPy = fixed_nlp.MindtPy_utils 52 solve_data.nlp_iter += 1 53 config.logger.info('Fixed-NLP %s: Solve subproblem for fixed integers.' 54 % (solve_data.nlp_iter,)) 55 56 # Set up NLP 57 TransformationFactory('core.fix_integer_vars').apply_to(fixed_nlp) 58 59 MindtPy.cuts.deactivate() 60 if config.calculate_dual: 61 fixed_nlp.tmp_duals = ComponentMap() 62 # tmp_duals are the value of the dual variables stored before using deactivate trivial contraints 63 # The values of the duals are computed as follows: (Complementary Slackness) 64 # 65 # | constraint | c_geq | status at x1 | tmp_dual (violation) | 66 # |------------|-------|--------------|----------------------| 67 # | g(x) <= b | -1 | g(x1) <= b | 0 | 68 # | g(x) <= b | -1 | g(x1) > b | g(x1) - b | 69 # | g(x) >= b | +1 | g(x1) >= b | 0 | 70 # | g(x) >= b | +1 | g(x1) < b | b - g(x1) | 71 evaluation_error = False 72 for c in fixed_nlp.component_data_objects(ctype=Constraint, active=True, 73 descend_into=True): 74 # We prefer to include the upper bound as the right hand side since we are 75 # considering c by default a (hopefully) convex function, which would make 76 # c >= lb a nonconvex inequality which we wouldn't like to add linearizations 77 # if we don't have to 78 rhs = value(c.upper) if c.has_ub() else value(c.lower) 79 c_geq = -1 if c.has_ub() else 1 80 # c_leq = 1 if c.has_ub else -1 81 try: 82 fixed_nlp.tmp_duals[c] = c_geq * max( 83 0, c_geq*(rhs - value(c.body))) 84 except (ValueError, OverflowError) as error: 85 fixed_nlp.tmp_duals[c] = None 86 evaluation_error = True 87 if evaluation_error: 88 for nlp_var, orig_val in zip( 89 MindtPy.variable_list, 90 solve_data.initial_var_values): 91 if not nlp_var.fixed and not nlp_var.is_binary(): 92 nlp_var.value = orig_val 93 # fixed_nlp.tmp_duals[c] = c_leq * max( 94 # 0, c_leq*(value(c.body) - rhs)) 95 # TODO: change logic to c_leq based on benchmarking 96 try: 97 TransformationFactory('contrib.deactivate_trivial_constraints').apply_to( 98 fixed_nlp, tmp=True, ignore_infeasible=False, tolerance=config.constraint_tolerance) 99 except ValueError: 100 config.logger.warning( 101 'infeasibility detected in deactivate_trivial_constraints') 102 results = SolverResults() 103 results.solver.termination_condition = tc.infeasible 104 return fixed_nlp, results 105 # Solve the NLP 106 nlpopt = SolverFactory(config.nlp_solver) 107 nlp_args = dict(config.nlp_solver_args) 108 set_solver_options(nlpopt, solve_data, config, solver_type='nlp') 109 with SuppressInfeasibleWarning(): 110 with time_code(solve_data.timing, 'fixed subproblem'): 111 results = nlpopt.solve( 112 fixed_nlp, tee=config.nlp_solver_tee, **nlp_args) 113 return fixed_nlp, results 114 115 116def handle_nlp_subproblem_tc(fixed_nlp, result, solve_data, config, cb_opt=None): 117 ''' 118 This function handles different terminaton conditions of the fixed-NLP subproblem. 119 120 Parameters 121 ---------- 122 fixed_nlp: Pyomo model 123 integer-variable-fixed NLP model 124 results: Pyomo results object 125 result from solving the Fixed-NLP 126 solve_data: MindtPy Data Container 127 data container that holds solve-instance data 128 config: ConfigBlock 129 contains the specific configurations for the algorithm 130 cb_opt: SolverFactory 131 the gurobi_persistent solver 132 ''' 133 if result.solver.termination_condition in {tc.optimal, tc.locallyOptimal, tc.feasible}: 134 handle_subproblem_optimal(fixed_nlp, solve_data, config, cb_opt) 135 elif result.solver.termination_condition in {tc.infeasible, tc.noSolution}: 136 handle_subproblem_infeasible(fixed_nlp, solve_data, config, cb_opt) 137 elif result.solver.termination_condition is tc.maxTimeLimit: 138 config.logger.info( 139 'NLP subproblem failed to converge within the time limit.') 140 solve_data.results.solver.termination_condition = tc.maxTimeLimit 141 solve_data.should_terminate = True 142 elif result.solver.termination_condition is tc.maxEvaluations: 143 config.logger.info( 144 'NLP subproblem failed due to maxEvaluations.') 145 solve_data.results.solver.termination_condition = tc.maxEvaluations 146 solve_data.should_terminate = True 147 else: 148 handle_subproblem_other_termination(fixed_nlp, result.solver.termination_condition, 149 solve_data, config) 150 151 152# The next few functions deal with handling the solution we get from the above NLP solver function 153 154 155def handle_subproblem_optimal(fixed_nlp, solve_data, config, cb_opt=None, fp=False): 156 """ 157 This function copies the result of the NLP solver function ('solve_subproblem') to the working model, updates 158 the bounds, adds OA and no-good cuts, and then stores the new solution if it is the new best solution. This 159 function handles the result of the latest iteration of solving the NLP subproblem given an optimal solution. 160 161 Parameters 162 ---------- 163 fixed_nlp: Pyomo model 164 integer-variable-fixed NLP model 165 solve_data: MindtPy Data Container 166 data container that holds solve-instance data 167 config: ConfigBlock 168 contains the specific configurations for the algorithm 169 cb_opt: SolverFactory 170 the gurobi_persistent solver 171 fp: bool, optional 172 this parameter acts as a Boolean flag that signals whether it is in the loop of feasibility pump 173 """ 174 copy_var_list_values( 175 fixed_nlp.MindtPy_utils.variable_list, 176 solve_data.working_model.MindtPy_utils.variable_list, 177 config) 178 if config.calculate_dual: 179 for c in fixed_nlp.tmp_duals: 180 if fixed_nlp.dual.get(c, None) is None: 181 fixed_nlp.dual[c] = fixed_nlp.tmp_duals[c] 182 dual_values = list(fixed_nlp.dual[c] 183 for c in fixed_nlp.MindtPy_utils.constraint_list) 184 else: 185 dual_values = None 186 main_objective = fixed_nlp.MindtPy_utils.objective_list[-1] 187 if solve_data.objective_sense == minimize: 188 solve_data.UB = min(value(main_objective.expr), solve_data.UB) 189 solve_data.solution_improved = solve_data.UB < solve_data.UB_progress[-1] 190 solve_data.UB_progress.append(solve_data.UB) 191 else: 192 solve_data.LB = max(value(main_objective.expr), solve_data.LB) 193 solve_data.solution_improved = solve_data.LB > solve_data.LB_progress[-1] 194 solve_data.LB_progress.append(solve_data.LB) 195 config.logger.info( 196 'Fixed-NLP {}: OBJ: {} LB: {} UB: {} TIME: {}s' 197 .format(solve_data.nlp_iter if not fp else solve_data.fp_iter, value(main_objective.expr), 198 solve_data.LB, solve_data.UB, round(get_main_elapsed_time(solve_data.timing), 2))) 199 200 if solve_data.solution_improved: 201 solve_data.best_solution_found = fixed_nlp.clone() 202 solve_data.best_solution_found_time = get_main_elapsed_time( 203 solve_data.timing) 204 if config.strategy == 'GOA': 205 if solve_data.objective_sense == minimize: 206 solve_data.num_no_good_cuts_added.update( 207 {solve_data.UB: len(solve_data.mip.MindtPy_utils.cuts.no_good_cuts)}) 208 else: 209 solve_data.num_no_good_cuts_added.update( 210 {solve_data.LB: len(solve_data.mip.MindtPy_utils.cuts.no_good_cuts)}) 211 212 # add obj increasing constraint for fp 213 if fp: 214 solve_data.mip.MindtPy_utils.cuts.del_component( 215 'improving_objective_cut') 216 if solve_data.objective_sense == minimize: 217 solve_data.mip.MindtPy_utils.cuts.improving_objective_cut = Constraint(expr=solve_data.mip.MindtPy_utils.objective_value 218 <= solve_data.UB - config.fp_cutoffdecr*max(1, abs(solve_data.UB))) 219 else: 220 solve_data.mip.MindtPy_utils.cuts.improving_objective_cut = Constraint(expr=solve_data.mip.MindtPy_utils.objective_value 221 >= solve_data.LB + config.fp_cutoffdecr*max(1, abs(solve_data.UB))) 222 223 # Add the linear cut 224 if config.strategy == 'OA' or fp: 225 copy_var_list_values(fixed_nlp.MindtPy_utils.variable_list, 226 solve_data.mip.MindtPy_utils.variable_list, 227 config) 228 add_oa_cuts(solve_data.mip, dual_values, solve_data, config, cb_opt) 229 elif config.strategy == 'GOA': 230 copy_var_list_values(fixed_nlp.MindtPy_utils.variable_list, 231 solve_data.mip.MindtPy_utils.variable_list, 232 config) 233 add_affine_cuts(solve_data, config) 234 # elif config.strategy == 'PSC': 235 # # !!THIS SEEMS LIKE A BUG!! - mrmundt # 236 # add_psc_cut(solve_data, config) 237 # elif config.strategy == 'GBD': 238 # # !!THIS SEEMS LIKE A BUG!! - mrmundt # 239 # add_gbd_cut(solve_data, config) 240 241 var_values = list(v.value for v in fixed_nlp.MindtPy_utils.variable_list) 242 if config.add_no_good_cuts: 243 add_no_good_cuts(var_values, solve_data, config, feasible=True) 244 245 config.call_after_subproblem_feasible(fixed_nlp, solve_data) 246 247 248def handle_subproblem_infeasible(fixed_nlp, solve_data, config, cb_opt=None): 249 """ 250 Solves feasibility problem and adds cut according to the specified strategy 251 252 This function handles the result of the latest iteration of solving the NLP subproblem given an infeasible 253 solution and copies the solution of the feasibility problem to the working model. 254 255 Parameters 256 ---------- 257 fixed_nlp: Pyomo model 258 integer-variable-fixed NLP model 259 solve_data: MindtPy Data Container 260 data container that holds solve-instance data 261 config: ConfigBlock 262 contains the specific configurations for the algorithm 263 cb_opt: SolverFactory 264 the gurobi_persistent solver 265 """ 266 # TODO try something else? Reinitialize with different initial 267 # value? 268 config.logger.info('NLP subproblem was locally infeasible.') 269 solve_data.nlp_infeasible_counter += 1 270 if config.calculate_dual: 271 for c in fixed_nlp.component_data_objects(ctype=Constraint): 272 rhs = value(c.upper) if c. has_ub() else value(c.lower) 273 c_geq = -1 if c.has_ub() else 1 274 fixed_nlp.dual[c] = (c_geq 275 * max(0, c_geq * (rhs - value(c.body)))) 276 dual_values = list(fixed_nlp.dual[c] 277 for c in fixed_nlp.MindtPy_utils.constraint_list) 278 else: 279 dual_values = None 280 281 # if config.strategy == 'PSC' or config.strategy == 'GBD': 282 # for var in fixed_nlp.component_data_objects(ctype=Var, descend_into=True): 283 # fixed_nlp.ipopt_zL_out[var] = 0 284 # fixed_nlp.ipopt_zU_out[var] = 0 285 # if var.has_ub() and abs(var.ub - value(var)) < config.bound_tolerance: 286 # fixed_nlp.ipopt_zL_out[var] = 1 287 # elif var.has_lb() and abs(value(var) - var.lb) < config.bound_tolerance: 288 # fixed_nlp.ipopt_zU_out[var] = -1 289 290 if config.strategy in {'OA', 'GOA'}: 291 config.logger.info('Solving feasibility problem') 292 feas_subproblem, feas_subproblem_results = solve_feasibility_subproblem( 293 solve_data, config) 294 # TODO: do we really need this? 295 if solve_data.should_terminate: 296 return 297 copy_var_list_values(feas_subproblem.MindtPy_utils.variable_list, 298 solve_data.mip.MindtPy_utils.variable_list, 299 config) 300 if config.strategy == 'OA': 301 add_oa_cuts(solve_data.mip, dual_values, 302 solve_data, config, cb_opt) 303 elif config.strategy == 'GOA': 304 add_affine_cuts(solve_data, config) 305 # Add a no-good cut to exclude this discrete option 306 var_values = list(v.value for v in fixed_nlp.MindtPy_utils.variable_list) 307 if config.add_no_good_cuts: 308 # excludes current discrete option 309 add_no_good_cuts(var_values, solve_data, config) 310 311 312def handle_subproblem_other_termination(fixed_nlp, termination_condition, 313 solve_data, config): 314 """ 315 Handles the result of the latest iteration of solving the NLP subproblem given a solution that is neither optimal 316 nor infeasible. 317 318 Parameters 319 ---------- 320 termination_condition: Pyomo TerminationCondition 321 the termination condition of the NLP subproblem 322 solve_data: MindtPy Data Container 323 data container that holds solve-instance data 324 config: ConfigBlock 325 contains the specific configurations for the algorithm 326 """ 327 if termination_condition is tc.maxIterations: 328 # TODO try something else? Reinitialize with different initial value? 329 config.logger.info( 330 'NLP subproblem failed to converge within iteration limit.') 331 var_values = list( 332 v.value for v in fixed_nlp.MindtPy_utils.variable_list) 333 if config.add_no_good_cuts: 334 # excludes current discrete option 335 add_no_good_cuts(var_values, solve_data, config) 336 337 else: 338 raise ValueError( 339 'MindtPy unable to handle NLP subproblem termination ' 340 'condition of {}'.format(termination_condition)) 341 342 343def solve_feasibility_subproblem(solve_data, config): 344 """ 345 Solves a feasibility NLP if the fixed_nlp problem is infeasible 346 347 Parameters 348 ---------- 349 solve_data: MindtPy Data Container 350 data container that holds solve-instance data 351 config: ConfigBlock 352 contains the specific configurations for the algorithm 353 354 Returns 355 ------- 356 feas_subproblem: Pyomo model 357 feasibility NLP from the model 358 feas_soln: Pyomo results object 359 result from solving the feasibility NLP 360 """ 361 feas_subproblem = solve_data.working_model.clone() 362 add_feas_slacks(feas_subproblem, config) 363 364 MindtPy = feas_subproblem.MindtPy_utils 365 if MindtPy.find_component('objective_value') is not None: 366 MindtPy.objective_value.value = 0 367 368 next(feas_subproblem.component_data_objects( 369 Objective, active=True)).deactivate() 370 for constr in feas_subproblem.MindtPy_utils.nonlinear_constraint_list: 371 constr.deactivate() 372 373 MindtPy.feas_opt.activate() 374 if config.feasibility_norm == 'L1': 375 MindtPy.feas_obj = Objective( 376 expr=sum(s for s in MindtPy.feas_opt.slack_var[...]), 377 sense=minimize) 378 elif config.feasibility_norm == 'L2': 379 MindtPy.feas_obj = Objective( 380 expr=sum(s*s for s in MindtPy.feas_opt.slack_var[...]), 381 sense=minimize) 382 else: 383 MindtPy.feas_obj = Objective( 384 expr=MindtPy.feas_opt.slack_var, 385 sense=minimize) 386 TransformationFactory('core.fix_integer_vars').apply_to(feas_subproblem) 387 nlpopt = SolverFactory(config.nlp_solver) 388 nlp_args = dict(config.nlp_solver_args) 389 set_solver_options(nlpopt, solve_data, config, solver_type='nlp') 390 with SuppressInfeasibleWarning(): 391 try: 392 with time_code(solve_data.timing, 'feasibility subproblem'): 393 feas_soln = nlpopt.solve( 394 feas_subproblem, tee=config.nlp_solver_tee, **nlp_args) 395 except (ValueError, OverflowError) as error: 396 for nlp_var, orig_val in zip( 397 MindtPy.variable_list, 398 solve_data.initial_var_values): 399 if not nlp_var.fixed and not nlp_var.is_binary(): 400 nlp_var.value = orig_val 401 with time_code(solve_data.timing, 'feasibility subproblem'): 402 feas_soln = nlpopt.solve( 403 feas_subproblem, tee=config.nlp_solver_tee, **nlp_args) 404 handle_feasibility_subproblem_tc( 405 feas_soln.solver.termination_condition, MindtPy, solve_data, config) 406 return feas_subproblem, feas_soln 407 408 409def handle_feasibility_subproblem_tc(subprob_terminate_cond, MindtPy, solve_data, config): 410 if subprob_terminate_cond in {tc.optimal, tc.locallyOptimal, tc.feasible}: 411 copy_var_list_values( 412 MindtPy.variable_list, 413 solve_data.working_model.MindtPy_utils.variable_list, 414 config) 415 if value(MindtPy.feas_obj.expr) <= config.zero_tolerance: 416 config.logger.warning('The objective value %.4E of feasibility problem is less than zero_tolerance. ' 417 'This indicates that the nlp subproblem is feasible, although it is found infeasible in the previous step. ' 418 'Check the nlp solver output' % value(MindtPy.feas_obj.expr)) 419 elif subprob_terminate_cond in {tc.infeasible, tc.noSolution}: 420 config.logger.error('Feasibility subproblem infeasible. ' 421 'This should never happen.') 422 solve_data.should_terminate = True 423 solve_data.results.solver.status = SolverStatus.error 424 elif subprob_terminate_cond is tc.maxIterations: 425 config.logger.error('Subsolver reached its maximum number of iterations without converging, ' 426 'consider increasing the iterations limit of the subsolver or reviewing your formulation.') 427 solve_data.should_terminate = True 428 solve_data.results.solver.status = SolverStatus.error 429 else: 430 config.logger.error('MindtPy unable to handle feasibility subproblem termination condition ' 431 'of {}'.format(subprob_terminate_cond)) 432 solve_data.should_terminate = True 433 solve_data.results.solver.status = SolverStatus.error 434