optscaling_oracle.hpp File Reference

Oracle for Optimal Matrix Scaling Problem. More...

#include <cassert>
#include <valarray>
#include "network_oracle.hpp"

Include dependency graph for optscaling_oracle.hpp:

Go to the source code of this file.

Classes
class	OptScalingOracle< Graph, Mapping, Fn >
	Oracle for Optimal Matrix Scaling. More...

Detailed Description

Oracle for Optimal Matrix Scaling Problem.

This module implements an oracle for solving the optimal matrix scaling problem as formulated by Orlin and Rothblum (1985). The problem involves finding diagonal scaling factors that minimize the ratio between the maximum and minimum scaled matrix entries.

The problem formulation:

\[ \min \frac{\pi}{\phi} \quad \text{s.t.} \quad \phi \le u_i |a_{ij}| u_j^{-1} \le \pi \; \forall a_{ij} \neq 0, \quad \pi, \phi, u_i > 0 \]

where \( u_i \) are the scaling factors, \( \pi \) is the maximum scaled entry, and \( \phi \) is the minimum scaled entry.