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)[source]

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)[source]

Constructor method

abstract solve()[source]

Base method for decogo MINLP algorithm

__abstractmethods__ = frozenset({'solve'})
_abc_impl = <_abc_data object>
class decogo.solver.colgen.ColGen(problem, settings, result)[source]

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)[source]

Constructor method

solve()[source]

Inner approximation algorithm

ia_init(duals=None)[source]

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)[source]

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()[source]

Performs fast FW column generation steps (see paper)

sub_gradient(direction_vector)[source]

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)[source]

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)[source]

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)[source]

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)[source]

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)[source]

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)[source]

Primal heuristics method

Parameters

iter_index – number of main iteration when the method is called

Type

int

print_z_values(z)[source]

Prints sorted z-weights blockwise

Parameters

z (BlockVector) – Weight vector

__abstractmethods__ = frozenset({})
_abc_impl = <_abc_data object>