Plans regarding the tau function (see SAThandbook article of OK)
More...
Go to the source code of this file.
Detailed Description
Plans regarding the tau function (see SAThandbook article of OK)
 Todo:
 Connections to other modules
 Todo:
 Handling of demos

See "Handling of demos" in ComputerAlgebra/plans/Maxima.hpp.

We must likely update the current file.

We should write a dedicated demosfile with the computations for OK's handbookarticle on heuristics.
 Todo:
 Cleanup BranchingTuples/Basic.mac

What to do with the computations under "Convexity considerations: line versions" ?

The point should be to demonstrate that certain functions are not convex; see ComputerAlgebra/Satisfiability/Lisp/BranchingTuples/demos/Basic.mac.

For example linear combination of distances, where the target is to minimise the variance, does not yield a convex optimisation problem, as shown in ComputerAlgebra/Satisfiability/Lisp/demos/FundamentsBranchingHeuristics.mac

So likely all these convexity considerations should move to the demos.
 Todo:
 Reimplement the remaining functionality from Mupad/tau.mup in Maxima

tau : DONE

tree probability distributions:

tpd_flatten : DONE

tpd_moment : DONE

tpd_tuples

td_combine

tpd_ccombine

tpd_ccmoment
 Todo:
 Trees
 Todo:
 Details of computations

tauprob :

Are there better scaling schemes?

tau_eps :

Could epsilon be eliminated, and the computation always proceeds until dx is 0 (for the arithmetic)?

Are there better lower bounds than tau_lo ?
 Todo:
 Optimisation

Support typical applications to worstcase upper bounds:

Given a parameter alpha and branching tuples depending on alpha, find the minimal tauvalue depending on alpha, for a given domain.

This is a very common task, and we should provide a convenient framework for this, with some nice demos (for the upperbounds community).

The common case seems to be a linear dependence on alpha, and then the domain can be computed via linear programming.

We should provide a variety of optimisation methods.

See the methods for quasiconvex optimisation discussed in [Eppstein, 2006, Quasiconvex Analysis of Multivariate Recurrence Equations for Backtracking Algorithms].

The other basic case is optimising a distance on a given tree, and again a convenient framework needs to be provided.

See ComputerAlgebra/Satisfiability/Lisp/BranchingTuples/demos/Basic.mac.

See "Mupad/tau.mup" above.

Likely this should go into its own submodule.
 Todo:
 Investigations on approximations

Perhaps for k=3 it is true that for all eps > 0 and K > eps the integral on [eps,K]^3 of dtau_3 is positive?
Definition in file general.hpp.