1"""Iteration code."""
2from __future__ import division
3
4from pyomo.contrib.gdpopt.cut_generation import (add_integer_cut,
5                                                 add_outer_approximation_cuts,
6                                                 add_affine_cuts)
7from pyomo.contrib.gdpopt.mip_solve import solve_LOA_master
8from pyomo.contrib.gdpopt.nlp_solve import (solve_global_subproblem, solve_local_subproblem)
9from pyomo.opt import TerminationCondition as tc
10from pyomo.contrib.gdpopt.util import time_code, get_main_elapsed_time
11
12
13def GDPopt_iteration_loop(solve_data, config):
14    """Algorithm main loop.
15
16    Returns True if successful convergence is obtained. False otherwise.
17
18    """
19    while solve_data.master_iteration < config.iterlim:
20        # Set iteration counters for new master iteration.
21        solve_data.master_iteration += 1
22        solve_data.mip_iteration = 0
23        solve_data.nlp_iteration = 0
24
25        # print line for visual display
26        config.logger.info(
27            '---GDPopt Master Iteration %s---'
28            % solve_data.master_iteration)
29
30        # solve linear master problem
31        with time_code(solve_data.timing, 'mip'):
32            mip_result = solve_LOA_master(solve_data, config)
33
34        # Check termination conditions
35        if algorithm_should_terminate(solve_data, config):
36            break
37
38        # Solve NLP subproblem
39        if solve_data.active_strategy == 'LOA':
40            with time_code(solve_data.timing, 'nlp'):
41                nlp_result = solve_local_subproblem(mip_result, solve_data, config)
42            if nlp_result.feasible:
43                add_outer_approximation_cuts(nlp_result, solve_data, config)
44        elif solve_data.active_strategy == 'GLOA':
45            with time_code(solve_data.timing, 'nlp'):
46                nlp_result = solve_global_subproblem(mip_result, solve_data, config)
47            if nlp_result.feasible:
48                add_affine_cuts(nlp_result, solve_data, config)
49        elif solve_data.active_strategy == 'RIC':
50            with time_code(solve_data.timing, 'nlp'):
51                nlp_result = solve_local_subproblem(mip_result, solve_data, config)
52        else:
53            raise ValueError('Unrecognized strategy: ' + solve_data.active_strategy)
54
55        # Add integer cut
56        add_integer_cut(
57            mip_result.var_values, solve_data.linear_GDP, solve_data, config,
58            feasible=nlp_result.feasible)
59
60        # Check termination conditions
61        if algorithm_should_terminate(solve_data, config):
62            break
63
64
65def algorithm_should_terminate(solve_data, config):
66    """Check if the algorithm should terminate.
67
68    Termination conditions based on solver options and progress.
69
70    """
71    # Check bound convergence
72    if solve_data.LB + config.bound_tolerance >= solve_data.UB:
73        config.logger.info(
74            'GDPopt exiting on bound convergence. '
75            'LB: {:.10g} + (tol {:.10g}) >= UB: {:.10g}'.format(
76                solve_data.LB, config.bound_tolerance, solve_data.UB))
77        if solve_data.LB == float('inf') and solve_data.UB == float('inf'):
78            solve_data.results.solver.termination_condition = tc.infeasible
79        elif solve_data.LB == float('-inf') and solve_data.UB == float('-inf'):
80            solve_data.results.solver.termination_condition = tc.infeasible
81        else:
82            solve_data.results.solver.termination_condition = tc.optimal
83        return True
84
85    # Check iteration limit
86    if solve_data.master_iteration >= config.iterlim:
87        config.logger.info(
88            'GDPopt unable to converge bounds '
89            'after %s master iterations.'
90            % (solve_data.master_iteration,))
91        config.logger.info(
92            'Final bound values: LB: {:.10g}  UB: {:.10g}'.format(
93                solve_data.LB, solve_data.UB))
94        solve_data.results.solver.termination_condition = tc.maxIterations
95        return True
96
97    # Check time limit
98    elapsed = get_main_elapsed_time(solve_data.timing)
99    if elapsed >= config.time_limit:
100        config.logger.info(
101            'GDPopt unable to converge bounds '
102            'before time limit of {} seconds. '
103            'Elapsed: {} seconds'
104            .format(config.time_limit, elapsed))
105        config.logger.info(
106            'Final bound values: LB: {}  UB: {}'.
107            format(solve_data.LB, solve_data.UB))
108        solve_data.results.solver.termination_condition = tc.maxTimeLimit
109        return True
110
111    if not algorithm_is_making_progress(solve_data, config):
112        config.logger.debug(
113            'Algorithm is not making enough progress. '
114            'Exiting iteration loop.')
115        solve_data.results.solver.termination_condition = tc.locallyOptimal
116        return True
117    return False
118
119
120def algorithm_is_making_progress(solve_data, config):
121    """Make sure that the algorithm is making sufficient progress
122    at each iteration to continue."""
123
124    # TODO if backtracking is turned on, and algorithm visits the same point
125    # twice without improvement in objective value, turn off backtracking.
126
127    # TODO stop iterations if feasible solutions not progressing for a number
128    # of iterations.
129
130    # If the hybrid algorithm is not making progress, switch to OA.
131    # required_feas_prog = 1E-6
132    # if solve_data.working_model.GDPopt_utils.objective.sense == minimize:
133    #     sign_adjust = 1
134    # else:
135    #     sign_adjust = -1
136
137    # Maximum number of iterations in which feasible bound does not
138    # improve before terminating algorithm
139    # if (len(feas_prog_log) > config.algorithm_stall_after and
140    #     (sign_adjust * (feas_prog_log[-1] + required_feas_prog)
141    #      >= sign_adjust *
142    #      feas_prog_log[-1 - config.algorithm_stall_after])):
143    #     config.logger.info(
144    #         'Feasible solutions not making enough progress '
145    #         'for %s iterations. Algorithm stalled. Exiting.\n'
146    #         'To continue, increase value of parameter '
147    #         'algorithm_stall_after.'
148    #         % (config.algorithm_stall_after,))
149    #     return False
150
151    return True
152