discopt.gdp.algorithms.init

Initialization strategies of the native GDP algorithms (#1775 G3.3).

Before its main loop an algorithm such as LOA solves the subproblems of a few configurations, to seed the master with cuts and to find a first incumbent. Pyomo GDPopt’s init_algorithm names the strategies; this module implements them over GDPSpace (the model with every disjunct’s indicator a master column) and the caller’s solve(selection) callback:

• "no_init" – nothing.

• "fix_disjuncts" – the one configuration whose indicators the user fixed at their active value (lb == ub); it must decide every active disjunction.

• "custom_disjuncts" – the configurations the caller lists, in order.

• "max_binary" – one master solve maximizing the number of active disjuncts, then its configuration.

• "set_covering" – repeated master solves, each maximizing the number of not-yet-covered disjuncts; a disjunct is covered once it was active in a configuration whose subproblem returned a point, and disjuncts holding only linear rows start covered (the master already sees them exactly). Stops when every disjunct is covered, the master finds nothing uncovered or nothing at all, iterlim is reached, or the deadline expires.

The strategies only choose configurations. A configuration whose subproblem fails is excluded from the strategy’s own later master solves, never from the caller’s master: whether it may be excluded there is the algorithm’s proof to make (C-35). Every master solve gets the deadline remainder.

Attributes

INIT_STRATEGIES
Selection

Classes

GDPSpace	A working copy of a GDP with every disjunct's indicator a column.
InitReport	What a strategy tried: each configuration with the callback's result.

Functions

initialize(→ InitReport)

Run strategy (one of INIT_STRATEGIES); see the module docstring.

Module Contents

discopt.gdp.algorithms.init.INIT_STRATEGIES = ('no_init', 'fix_disjuncts', 'custom_disjuncts', 'max_binary', 'set_covering')

discopt.gdp.algorithms.init.Selection

class discopt.gdp.algorithms.init.GDPSpace

A working copy of a GDP with every disjunct’s indicator a column.

work is a clone of the caller’s model (the original is never touched) with every either_or indicator allocated; lowered is its big-M lowering, whose first columns are work’s, so columns[d] indexes both. work is the model the subproblems are solved on.

work: discopt.modeling.core.Model

lowered: discopt.modeling.core.Model

tree: discopt.gdp.tree.GDPTree

columns: dict[discopt.gdp.tree.DisjunctNode, int]

nonlinear: set[discopt.gdp.tree.DisjunctNode]

before: discopt.gdp.tree.GDPTree | None = None

counterpart: dict[discopt.gdp.tree.DisjunctNode, discopt.gdp.tree.DisjunctNode]

classmethod from_model(model: discopt.modeling.core.Model) → GDPSpace

master(backend: str = DEFAULT_MASTER_BACKEND) → discopt.gdp.algorithms.master.MasterMILP

selection_from_x(x: Any) → Selection

The disjuncts a master point selects, walking down from the roots.

check(selection: collections.abc.Iterable[discopt.gdp.tree.DisjunctNode]) → Selection

selection as a list of this space’s nodes.

A node of another tree of the same model – the caller’s own gdp_tree(model), or one rebuilt from work – is resolved by its address with the structural check of discopt.gdp.state (#1794 S2); a node of a different or changed model is refused.

class discopt.gdp.algorithms.init.InitReport

What a strategy tried: each configuration with the callback’s result.

strategy: str

tried: list[tuple[Selection, Any]] = []

covered: set[discopt.gdp.tree.DisjunctNode]

uncovered: set[discopt.gdp.tree.DisjunctNode]

stop_reason: str = ''

discopt.gdp.algorithms.init.initialize(strategy: str, space: GDPSpace, solve: collections.abc.Callable[[Selection], Any], deadline: discopt.gdp.algorithms.base.Deadline, *, master: discopt.gdp.algorithms.master.MasterMILP | None = None, custom: collections.abc.Sequence[collections.abc.Iterable[discopt.gdp.tree.DisjunctNode]] | None = None, iterlim: int = 8, master_time_cap: float | None = None) → InitReport

Run strategy (one of INIT_STRATEGIES); see the module docstring.

solve(selection) is the algorithm’s: it solves the subproblem (and adds cuts, offers incumbents, records results). Its result counts as a point when it has a non-None x. master defaults to space.master() and is never changed: the strategies’ exclusions are per call.