decomposition.h File Reference

Solving a large problem as a sequence of smaller ones. More...

#include <algorithm>
#include <chrono>
#include <cmath>
#include <limits>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <vector>
#include "line/opt/line_opt_solver.h"

Include dependency graph for decomposition.h:

Go to the source code of this file.

Classes
struct	line::opt::SubProblem
struct	line::opt::SubProblemResult
struct	line::opt::WorkflowResult
class	line::opt::DecompositionWorkflow

Namespaces
namespace	line
namespace	line::opt

Detailed Description

Solving a large problem as a sequence of smaller ones.

A SubProblem names a subset of the decision variables and fixes the rest. DecompositionWorkflow::solve_sequential cycles over the sub-problems, solving each with the others held at their current values and feeding the result forward, until the objective stops improving by more than the tolerance or the cycle limit is reached.

This is a heuristic, not a decomposition theorem: it converges to a point that is optimal in each block separately, which need not be the joint optimum. It earns its place when the joint search space is too large for the population to cover, and WorkflowResult reports the per-cycle history so the trade is visible rather than assumed.

Definition in file decomposition.h.