decogo.solver.colgen

This module implements Column Generation

Classes

AlgorithmBase(problem, settings, result)	An abstract base class which implement an MINLP algorithm from decogo.
ColGen(problem, settings, result)	This class implements Column Generation (CG) algorithm

class decogo.solver.colgen.AlgorithmBase(problem, settings, result)

An abstract base class which implement an MINLP algorithm from decogo.

Parameters:

• problem (DecomposedProblem) – Decomposed problem class, which stores all input data

• settings (Settings) – Settings class

• result (Results) – Class which stores the results

__init__(problem, settings, result)

Constructor method

abstract solve()

Base method for decogo MINLP algorithm

__abstractmethods__ = frozenset({'solve'})

_abc_impl = <_abc_data object>

class decogo.solver.colgen.ColGen(problem, settings, result)

This class implements Column Generation (CG) algorithm

Parameters:

• problem (DecomposedProblem) – Decomposed problem class, which stores all input data

• settings (Settings) – Settings class

• result (Results) – Class which stores the results

__init__(problem, settings, result)

Constructor method

solve()

Inner approximation algorithm

ia_init(duals=None)

Initialization of inner outer approximation

Parameters:

duals (ndarray) – Initial dual vector for initialization

Returns:

Solution of MIP projection master problem

Return type:

BlockVector

column_generation(subset_of_blocks=None, approx_solver=False)

Performs column generation steps (see paper)

Parameters:

• subset_of_blocks (list or None) – apply column generation for reduced block set

• approx_solver (bool) – enables approximate solving of subproblems in column generation

Returns:

Dual solution from IA master problem regarding global constraints

Return type:

ndarray

column_generation_fast_fw()

Performs fast FW column generation steps (see paper)

sub_gradient(direction_vector)

Performs sub-gradient iterations

Parameters:

direction_vector (ndarray) – Initial vector for sub-gradient iterations

Returns:

Final direction vector

Return type:

tuple

generate_column(block_id, direction, heuristic=True, approx_solver=False, x_k=None)

Generates the inner point (and corresponding column) either with MINLP sub-problem or with NLP sub-problem (too heuristically); adds valid local linear cut to heu_oa_master_problem if any

Parameters:

• block_id (int) – Block identifier

• direction (ndarray) – Direction in image space

• heuristic (bool) – Indicates if the sub-problem must be solved heuristically

• approx_solver (bool) – enables approximate solving of subproblems in column generation

• x_k (BlockVector or None) – start_point for solving subproblems

Returns:

Inner point, primal bound, reduced cost of new point, bool value indicating whether new point is generated and corresponding column

Return type:

tuple

solve_minlp_subproblem(block_id, dir_im_space, compute_reduced_cost=True, heuristic=True)

Solves MINLP subproblem, adds inner point, (either in compact form or in the original) and computes reduced cost for the new inner point

Parameters:

• block_id (int) – Block identifier

• dir_im_space (ndarray) – Direction in image space

• compute_reduced_cost (bool) – Indicates if reduced cost has to be computed

• heuristic (bool) – Indicates if the sub-problem must be solved heuristically

Returns:

Inner point (feasible point), reduced cost value, primal bound of the sub-problem, dual bound of the sub-problem, bool value indicating whether new inner point was generated, corresponding column to the inner point

Return type:

tuple

get_slack_directions(slacks)

Computes new direction based on the slack values of IA master problem

Parameters:

slacks (list) – Slack values stored as a list of tuples

Returns:

New direction in image space

Return type:

ndarray

approx_solve_minlp_subproblem(block_id, dir_im_space, x_k=None)

Solves MINLP subproblem approximately, adds inner point (either in compact form or in the original) and computes reduced cost for the new inner point

Parameters:

• block_id (int) – Block identifier

• dir_im_space (ndarray) – Direction in image space

• x_k (BlockVector or None) – start_point for solving subproblems

Returns:

Inner point (feasible point), reduced cost value, primal bound of the sub-problem, dual bound of the sub-problem, bool value indicating whether new inner point was generated, corresponding column to the inner point

Return type:

tuple

find_solution_init(iter_index=None)

Method to generate a feasible solution and therefore reducing the slacks to zero in innerMaster problem

Parameters:

iter_index – number of main iteration when the method is called

Type:

int

find_solution(iter_index=None)

Primal heuristics method

Parameters:

iter_index – number of main iteration when the method is called

Type:

int

print_z_values(z)

Prints sorted z-weights blockwise

Parameters:

z (BlockVector) – Weight vector

__abstractmethods__ = frozenset({})

_abc_impl = <_abc_data object>