template<typename Graph, typename Mapping, typename Fn>
requires HasKeyType<Graph>
class OptScalingOracle< Graph, Mapping, Fn >
Oracle for Optimal Matrix Scaling.
This class implements a separation oracle for the optimal matrix scaling problem. It uses a network oracle internally to handle the feasibility constraints and provides cutting planes for optimization.
The oracle maintains:
- A reference to the underlying graph structure
- A cost function for matrix entries
- A Ratio helper class for constraint evaluation
- Network oracle for feasibility checking
- Template Parameters
-
| Graph | Type of the directed graph representing matrix sparsity |
| Mapping | Type of vertex potential mapping (scaling factors) |
| Fn | Type of the cost function (edge -> matrix entry pair) |
template<typename Graph , typename Mapping , typename Fn >
| auto OptScalingOracle< Graph, Mapping, Fn >::assess_optim |
( |
const Vec & |
x, |
|
|
double & |
t |
|
) |
| -> std::tuple<Cut, bool> |
|
inline |
Assess optimality at point x (cutting plane interface)
The optimal scaling problem minimizes the ratio \(\pi / \psi\). In log scale, the objective is \(s = \pi - \psi\). The algorithm maintains \(t\) as the best-so-far optimal value:
\[
f(x) = s - t = (\pi - \psi) - t
\]
If \(f(x) < 0\), the solution improves; otherwise a cutting plane \((1, -1)\) is returned.
- Parameters
-
| [in] | x | (pi, psi) in log scale |
| [in,out] | t | the best-so-far optimal value |
- Returns
- tuple of (cut, whether gamma was updated)
- See also
- cutting_plane_optim
