mapqn_qrf_bas_nlp.h File Reference

qrf_bas_mmi, qrf_bas_mem and qrf_bas_bethe: the nonlinear bounds on the BAS-BLOCKING polytope. More...

#include <cstddef>
#include <string>
#include <vector>
#include "line/api/mapqn/mapqn_qr_bounds_bas.h"
#include "line/api/mapqn/mapqn_qrf_common.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/lp_highs.h"
#include "line/util/simplex.h"

Include dependency graph for mapqn_qrf_bas_nlp.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::mapqn
namespace	line::mapqn::qrfbas

Enumerations
enum class	line::mapqn::qrfbas::Objective { line::mapqn::qrfbas::Mmi , line::mapqn::qrfbas::Mem , line::mapqn::qrfbas::Bethe }
	Which functional mapqn_qrf_bas minimizes over the BAS polytope. More...

Functions
template<class T>
lp::LpModel< T >	line::mapqn::qrfbas::bas_polytope (const QrBasParams< T > &p, const QrBasIndex &x)
	The BAS feasible set, built by the same calls the LP bound makes.
void	line::mapqn::qrfbas::mmi_terms (const QrBasIndex &x, const std::vector< int > &F, std::vector< std::size_t > *ij, std::vector< std::size_t > *ii, std::vector< std::size_t > *jj, int n_from=1)
	The (ij, ii, jj) column triples of the MI objective, i != j, ni, nj >= n_from.
std::vector< std::size_t >	line::mapqn::qrfbas::mem_terms (const QrBasIndex &x, const std::vector< int > &F, int n_from=1)
	The diagonal columns of the MEM objective, ni >= n_from (1 for MEM, 0 for BETHE).
template<class T>
QrfMetrics< T >	line::mapqn::mapqn_qrf_bas (const QrBasParams< T > &p, qrfbas::Objective obj, unsigned max_iter=200)
	Solve one BAS-blocking NLP bound.
template<class T>
QrfMetrics< T >	line::mapqn::mapqn_qrf_bas_mmi (const QrBasParams< T > &p, unsigned max_iter=200)
	Minimum-mutual-information bound on the BAS-blocking polytope.
template<class T>
QrfMetrics< T >	line::mapqn::mapqn_qrf_bas_mem (const QrBasParams< T > &p, unsigned max_iter=200)
	Maximum-entropy bound on the BAS-blocking polytope.
template<class T>
QrfMetrics< T >	line::mapqn::mapqn_qrf_bas_bethe (const QrBasParams< T > &p, unsigned max_iter=200)
	Tree-reweighted (Bethe) free entropy bound on the BAS-blocking polytope.

Detailed Description

qrf_bas_mmi, qrf_bas_mem and qrf_bas_bethe: the nonlinear bounds on the BAS-BLOCKING polytope.

Port of python/line_solver/api/mapqn/qrf_bas_nlp.py. api/mapqn has no MATLAB implementation, so Python and the JAR are the references.

THE POLYTOPE IS NOT RE-DERIVED HERE. It is exactly the one mapqn_qr_bounds_bas builds and that the LP token qrf.bas is validated on against the AMPL model; only the OBJECTIVE differs, the LP maximizing one station's utilization where these minimize mutual information, negative entropy or the tree-reweighted (Bethe) free entropy over the same feasible set. Re-transcribing the fifteen constraint families would duplicate several hundred lines whose index conventions are exactly where the reference's own twin twice went wrong – the THM30/THM3 population-to-index shift, and a MARGINALS sum whose upper limit was taken on the 1-based index rather than on the population. Sharing the builder means a family added to the LP reaches the NLP with it.

The decision vector is therefore the LP's own, indexed through QrBasIndex, NOT the flat sub_qrfvar layout of the no-blocking family. The two are different orderings of different variable sets and must not be mixed: the BAS index skips a population above a station's capacity, which the no-blocking layout carries and pins to zero.

CONVEXITY, AS IN THE NO-BLOCKING TWIN: MEM is convex on the polytope and has a unique optimum; MMI is NOT (its -p_ij log p_ii terms are not), so it reports a local optimum fixed by the phase-1 LP vertex. BETHE is the convex combination the weight lambda = 1/M is chosen to make convex on the LOCAL MARGINAL polytope; the BAS set adds the blocking families on top of the marginal ones, so the objective's convexity carries but the per-configuration marginal consistency that the argument rests on is not proved under ZERO5. Start-point independence here is therefore MEASURED, not assumed. See mapqn_qrf_common.h for the measurement behind all three.

ARITHMETIC: transcendental.

Definition in file mapqn_qrf_bas_nlp.h.