Common use of Conjecture Clause in Contracts

Conjecture. Based on our empirical results presented in Figures 6 and 7, we are able to conjecture a more precise behavior of the free energy for the two optimization problems discussed in this paper. We shall introduce a correction coefficient α whose value is determines experimentally in the sequel. Conjecture 1. Consider a class of combinatorial optimization problems com- plying with Common Theorem Setting, weights Wi having mean µ and variance (a) σ = 0.3 (b) σ = 2.4 Figure 8: Influence of the correction in the case of the quadratic assignment problem for different standard deviation. The mean is µ = 4 and µV = µH and σ2 = σ2 . σ2. Then the free energy satisfies E[log Z(β, X)] + β^µ N log m .1 + α2 β^2σ2 , β^ < for some α ≥ 1. log m αβ^σ β^ ≥ 2 (119) The correction coefficient α is related to the variance of the partition function which involves strong correlations between feasible solutions (that was largely ignored in (▇▇▇▇▇▇▇ et al., 2014)). Based on our experimental results, we conclude that α is well approximated by the following formula EcVarXR(c, X) Nσ2 α = . EX VarcR(c, X) = . EX VarcR(c, X) where the expectation Ec[ ] is taken w.r.t. to all feasible solutions selected uniformly. Appendix A. A Tighter Upper Bound for MBP‌ The general upper bound proven in Theorem 1 above is unfortunately not tight. To show it we consider the general minimum bisection problem with n . vertices, that is, d = n. In this case, N = |Sn(c)| = n2/4 is the number of edges cut in a bisection, and m = |Cn| = n/2 is the number of possible bisections. Thus we are still in our framework of log m = o(N ), and therefore we define a ^√ scaling β = β log m/N . log 2σ

Conjecture. Based on our empirical results presented in Figures 6 and 7, we are able to conjecture a more precise behavior of the free energy for the two optimization problems discussed in this paper. We shall introduce a correction coefficient α whose value is determines experimentally in the sequel. Conjecture 1. Consider a class of combinatorial optimization problems com- plying with Common Theorem Setting, weights Wi having mean µ and variance (a) σ = 0.3 (b) σ = 2.4 Figure 8: Influence of the correction in the case of the quadratic assignment problem for different standard deviation. The mean is µ = 4 and µV = µH and σ2 = σ2 . σ2. Then the free energy satisfies E[log Z(β, X)] + β^µ N log m .1 + α2 β^2σ2 , β^ < for some α ≥ 1. log m αβ^σ β^ ≥ 2 (119123) The correction coefficient α is related to the variance of the partition function which involves strong correlations between feasible solutions (that was largely ignored in (▇▇▇▇▇▇▇ et al., 2014)). Based on our experimental results, we conclude that α is well approximated by the following formula EcVarXR(c, X) Nσ2 α = . EX VarcR(c, X) = . EX VarcR(c, X) where the expectation Ec[ ] is taken w.r.t. to all feasible solutions selected uniformly. Appendix A. A Tighter Upper Bound for MBP‌ The general upper bound proven in Theorem 1 above is unfortunately not tight. To show it we consider the general minimum bisection problem with n . vertices, that is, d = n. In this case, N = |Sn(c)| = n2/4 is the number of edges cut in a bisection, and m = |Cn| = n/2 is the number of possible bisections. Thus we are still in our framework of log m = o(N ), and therefore we define a ^√ scaling β = β log m/N . log 2σ