Spokes

In this section we provide an overview of some of the spoke classes that are part of the mpi-sppy release.

Outer Bound

For minimization problems, outer bound means lower bound.

Frank-Wolfe

This bound is based on the paper Combining Progressive Hedging with a Frank–Wolfe Method to Compute Lagrangian Dual Bounds in Stochastic Mixed-Integer Programming by Boland et al [boland2018]. It does not receive information from the hub, it simply sends bounds as they are available. Compared to the Lagrangian bounds, it takes longer to compute but is generally tighter once it reports a bound.

Lagrangian

This bound is based on the paper Obtaining lower bounds from the progressive hedging algorithm for stochastic mixed-integer programs by Gade et al [gade2016]. It takes W values from the hub and uses them to compute a bound.

Subgradient

This bound is based on the subgradient method. It computes its own W values based on the Lagrangian relaxation and reports a bound to the hub.

Lagranger

This bounder is no longer recommended for use. It does not seem to work as well as others.

This bound is a variant of the Lagrangian bound, but it takes x values from the hub and uses those to compute its own W values. It can modify the rho values (typically to use lower values). The modification is done in the form of scaling factors that are specified to be applied at a given iteration. The factors accumulate so if 0.5 is applied at iteration 1 and 1.2 is applied at iteration 10, from iteration 10 onward, the factor will be 0.6. Here is a sample json file:

{
 "1": "0.5",
 "10": "1.2"
}

ph_ob

This bounder is similar to the Lagrangian bounder, except that it executes a PH algorithm to obtain its own W values. The idea is that it can use lower rho values so as to obtain better outer (lower when minimizing) bounds. It can also provide a Lagrangian bound even if the hub does not provide lagrangian multipliers.

The easiest way to use ph_ob is via the vanilla ph_ob_spoke method as illustrated in examples.farmer.archive.farmer_cylinders.py. This method takes values from the config object (assuming the config object’s ph_ob method was called as shown in the function examples.farmer.archive.farmer_cylinders._parse_args) and sets up the options for the spoke.

The option ph-ob-initial-rho-rescale-factor defaults to 0.1, so if nothing other than --ph-ob is given on the command line, the ph_ob spoke will use one tenth the default rho (it might use one tenth of rho from a rho setter if one is configured in the cylinders program and passed to the ph_ob constructor). Additional control over rho values is provided by the phob-rho-rescale-factors-json option which is a json file that provides a dictionary with keys that are iteration numbers and values that are rescale factors. Note that all rescaling is cummulative.

See examples.uc.gradient_uc_cylinders.py for an example that uses a cost-based rho setter for the uc problem in the ph_ob cylinder.

As of August, 2024 use of a gradient based rho with ph_ob is untested.

Reduced Costs

The reduced cost spoke is equivalent to the Lagrangian spoke, except that it relaxes all integrality contraints in the subproblems. This enables the computation of reduced costs for the nonanticipative variables, which can be used for provable bound tightening, which is shared to all cylinders. The reduced cost can also be used for heuristic fixing in the hub via the reduced_cost_fixer extension.

Inner Bounds

For minimization problems, inner bound means upper bound. But more importantly, the bounds are based on a solution, whose value can be computed. In some sense, if you don’t have this solution, you don’t have anything (even if you think your hub algorithm has converged in some sense). We refer to this solution as xhat (\(\hat{x}\)) or somes as an incumbent solution. ` xhat_specific_bounder ^^^^^^^^^^^^^^^^^^^^^

At construction, this spoke takes a specification of a scenario per non-leaf node of the scenario tree (so for a two-stage problem, one scenario), which are used at every iteration of the hub algorithm as trial values for \(\hat{x}\).

xhatshufflelooper_bounder

This bounder shuffles the scenarios and loops over them to try a \(\hat{x}\) until the hub provides a new x. To ensure that all subproblems are tried eventually, the spoke remembers where it left off, and resumes from its prior position. Since the resulting subproblems after fixing the first-stage variables are usually much easier to solve, many candidate solutions can be tried before receiving new x values from the hub.

This spoke also supports multistage problems. It does not try every subproblem, but shuffles the scenarios and loops over the shuffled list. At each step, it takes the first-stage solution specified by a scenario, and then uses the scenarios that follows in the shuffled loop to get the values of the non-first-stage variables that were not fixed before.

xhatxbar_bounder

This bounder computes and uses \(\overline{x}\) as \(\hat{x}\). It does simple rounding for integer variables.

stage2ef

An option for xhatshufflelooper_bounder is under development for multistage problems that creates an EF for each second stage nodes by fixing the first stage nonanticipative variables. This code requires that the number of ranks allocated to the xhatshufflelooper_bounder is an integer multiple of the number of second stage nodes. Here is a hint about how to to use it in a driver:

xhatshuffle_spoke["opt_kwargs"]["options"]["stage2EFsolvern"] = solver_name
xhatshuffle_spoke["opt_kwargs"]["options"]["branching_factors"] = branching_factors

An example is shown in examples.hydro.hydro_cylinders.py (this particular example is intended to show the coding, not normal behavior. It is sort of an edge case: including this option causes the upper bound to immediately be Z*)

slam_heuristic

This heuristic attempts to find a feasible solution by slamming every variable to its maximum (or minimum) over every scenario associated with that scenario tree node. This spokes only supports two-stage problems at this time.

General

cross scenario

Computes and passes cross scenario cuts.

Relaxed PH

For S-MIPs, executes PH on the continuous relaxation of the problem. Provides W values to the Lagrangian or Reduced Costs spokes, as well as relaxed nonants which can be used with the relaxed PH fixer for the PH Primal Hub. This spoke can be useful, along with the PH Primal Hub, when the continuous relaxation allows for good dual (but not primal) convergence of the original problem. This typically happens for problems with a “strong” continuous relaxation. The option relaxed_ph_rescale_rho_factor allows the user to adjust provided rho values by a constant multiplier across all variables, which occurs between PH iteration 0 and PH iteration 1.

PH Dual

Executes another copy of PH, providing W values to the Lagrangian and/or Reduceds Costs spokes. This spoke can be useful, along with the PH Primal Hub, for problems which need different rho strategies for primal and dual convergence. The option ph_dual_rescale_rho_factor allows the user to adjust provided rho values by a constant multiplier across all variables, which occurs between PH iteration 0 and PH iteration 1.