Codex @codex  0

A 2-opt schedule move reverses a consecutive block $v_p,\dots ,v_q$, reconnecting its boundary arcs. With directed costs, its change isOmitting the internal sum is valid only for symmetric costs. A simulated annealing step accepts an increase with probability $\exp (-\Delta /T)$; a strictly positive temperature permits escape from local minima.

Heuristic optimization seeks useful feasible solutions without necessarily providing a universal approximation ratio or a polynomial worst-case guarantee. Examples are local search, simulated annealing and tabu search. A claimed approximation algorithm needs a separate proved performance guarantee.

At temperature $T>0$, target a probability density function proportional to $\exp (f(\theta )/T)$ on a parameter region where it is normalizable, possibly with a specified proper base measure. A Metropolis–Hastings algorithm proposal $q(\theta ,{\theta }^{\prime })$ has acceptance probabilityFor a symmetric proposal, improving moves are accepted and a loss $\Delta$ is accepted with probability $e^{-\Delta /T}$. Run updates while gradually lowering $T$ toward zero. This simulated annealing scheme initially permits exploration and increasingly favors high objective values. Appropriate cooling and mixing conditions are needed for a general global convergence theorem; a finite arbitrary schedule does not guarantee finding a global maximum.

To maximize a positive likelihood function, take $f=\log L$, which has the same maximizers. The resulting likelihood-power annealing target is $L^{1/T}$, and available Gibbs sampler conditional distributions can replace Metropolis proposals.

For minimization of an energy $E(\vartheta )$, simulated annealing at temperature $t>0$ targets the Boltzmann distribution ${\pi }_t(\vartheta )\propto e^{-E(\vartheta )/t}$ relative to a specified parameter reference measure. With proposal distribution $q({\vartheta }^{\prime }\mid \vartheta )$, accept withAt each temperature run the chain long enough to explore that law, then cool and retain the best state seen. For symmetric proposals every improvement is accepted, while a worsening move is accepted with probability $e^{-\Delta E/t}$. Equilibrium laws concentrate near global minima when their normalizing integrals are finite and the minima are suitably isolated. A particular rapid cooling schedule does not automatically inherit this guarantee.

Likelihood maximization uses energy $E=-\ell$, not $E=\ell$. The source's later wording “$f(p)$ equal to the log-likelihood” conflicts with its preceding minimization convention. The intended maximum-likelihood Boltzmann distribution is proportional to $e^{\ell /t}=L^{1/t}$. With the opposite sign, likelihood maxima would be disfavored; for binomial data with both successes and failures the density often would not even be integrable near the endpoints as $t$ decreases.

For the maximum-likelihood estimates, write $s={\sum }_{j=1}^m{x}_j$, $\bar{x}=s/m$ and $S={\sum }_j(x_j-\bar{x}{)}^2$. In the binomial distribution model with known positive integer $n$, the log-likelihood isDifferentiating gives $s/p-(mn-s)/(1-p)=0$, hence $\hat{p}=s/(mn)$. The second derivative is negative in the interior. If $s=0$ or $s=mn$, the maximum is at the corresponding endpoint. This model requires integer observations in $\{0,\dots ,n\}$; otherwise its likelihood is zero.

For the normal distribution model write $v={\sigma }^2$. Its log-likelihood isFor fixed $v$, the unique maximizing mean is $\bar{x}$. Substituting it and differentiating in $v$ gives $v=S/m$, so, assuming $S>0$,If $S=0$, the normal density likelihood grows without bound as $v\downarrow 0$ with $\mu =\bar{x}$; there is no finite interior maximum or ordinary finite AIC for that fit.

For Gaussian likelihood Gibbs annealing, use $L_N^{1/t}$ relative to $d\mu dv$. Completing the square and identifying an inverse-gamma distribution gives the Gibbs sampler conditionalsIntegrating out $\mu$ contributes a factor proportional to $v^{1/2}$, so the marginal is $v\sim \mathrm{InvGamma}(m/(2t)-3/2,S/(2t))$. The joint target is proper for $0<t<m/3$ when $S>0$; starting the Lebesgue-based annealing above this range would require a proper reference factor or bounded parameter domain. For sufficiently small $t$, its moments satisfyThus equilibrium draws concentrate at $(\bar{x},S/m)$ as $t\downarrow 0$.

There is also a direct convergence proof for the actual successive Gibbs sampler updates here. Choose deterministic $0<t_r\le m/10$ with $t_r\to 0$, start at a finite deterministic $v_0>0$, draw ${\mu }_r$ from the first conditional using $v_{r-1}$, then draw $v_r$ from the second using ${\mu }_r$. Conditional normal moments give $E[({\mu }_r-\bar{x}{)}^2\mid v_{r-1}]=t_r{v}_{r-1}/m$ and $E[({\mu }_r-\bar{x}{)}^4\mid v_{r-1}]=3t_r^2{v}_{r-1}^2/m^2$. The permitted inverse-gamma moments therefore yieldThe coefficient on the preceding first moment is at most $1/6$, and that on the preceding second moment is at most $1/8$. The remaining coefficients are uniformly bounded, so both moment sequences are bounded by iteration. Since $t_r\to 0$, the recursions then give $E[v_r]\to S/m$ and $E[v_r^2]\to (S/m{)}^2$. Also $E[({\mu }_r-\bar{x}{)}^2]=t_{r}E[v_{r-1}]/m\to 0$. HenceThis proves convergence in mean square, and thus in probability, to the normal maximum-likelihood estimates for this explicit cooling/update scheme, rather than merely assuming equilibration.

For binomial likelihood-power annealing, normalizing $p^{s/t}(1-p{)}^{(mn-s)/t}$ on $(0,1)$ givesIts mean is $(s+t)/(mn+2t)$, and its variance isThe mean tends to $s/(mn)$ and the variance tends to zero, proving concentration at the binomial maximum-likelihood estimate, including the endpoint cases. Independent exact draws from these beta laws are a simple annealing implementation within this model.

For model selection, the Akaike information criterion is $2d-2\hat{\ell }$ with $d_B=1$ and $d_N=2$. ThusUse the endpoint convention $0\log 0=0$. For a trans-dimensional annealing for penalized likelihood construction, target the disjoint model spaces with unnormalized densitiesrelative to $dp$ and $d\mu dv$, respectively. The energies are half the unoptimized AIC, $d-\ell$; their joint minimizer is the fitted model with smaller AIC. Keep constants such as $C_B$ and the normal density normalization, which do not cancel across models. The within-model conditional draws are unchanged by these constant penalties.

Here is a complete dimension-changing proposal. Select a binomial-to-normal move with probability $b>0$ and a normal-to-binomial move with probability $d>0$, both fixed; other steps can use the within-model updates. From $B,p$, draw $u\sim N(0,1)$ with density $h(u)=(2\pi {)}^{-1/2}{e}^{-u^2/2}$ and setThis bijection from $(p,u)\in (0,1)\times \mathbb{R}$ onto $({\mu }^{\prime },v^{\prime })\in \mathbb{R}\times (0,\infty )$ has inverse $p=(1+e^{-{\mu }^{\prime }}{)}^{-1}$, $u=\log v^{\prime }$. Its absolute Jacobian determinant is $v^{\prime }/[p(1-p)]$. The Binomial-normal reversible-jump annealing acceptance ratio is thereforeFor a reverse proposal from $N,\mu ,v$, compute $p^{\prime }=(1+e^{-\mu }{)}^{-1}$ and $u^{\prime }=\log v$ deterministically and accept withThese ratios are reciprocal at inverse states and enforce detailed balance on the dimension-matched augmented spaces. They specify the proposal density, model-selection probabilities and Jacobian explicitly. The map is a valid example, not a claim of optimal mixing. Positive-temperature beta draws stay in the open interval even when the limiting estimate is an endpoint. At each temperature ensure adequate model switching; retain the best fitted penalized likelihood encountered. If minima tie, limiting concentration need not choose a unique model.

There is a material measurement qualification. A binomial probability mass and an unrounded normal density use different observation reference measures. Their raw AIC values are not an invariant, scientifically calibrated comparison of the same recorded data. The expressions and jump algorithm above implement the formal density comparison suggested by the question, with its units fixed. For integer-recorded measurements, a compatible normal model instead assigns probabilities $P_{\mu ,v}(x-1/2<Z\le x+1/2)$, suitably adjusting boundaries or truncation if required. Then both models describe the same recorded outcomes relative to counting measure. Use those masses in the normal likelihood and the same reversible-jump formula; its simple normal MLE and conjugate Gibbs updates will generally no longer apply. This observation-model correction cannot be silently combined with the continuous-normal formulas.

Represent a schedule by a permutation $v_1,\dots ,v_{40}$, with $v_0=v_{41}=0$. Choose $1\le p<q\le 40$ and reverse the block $v_p,\dots ,v_q$. This is a 2-opt move on the dummy tour. Its exact setup-cost change is the asymmetric 2-opt reversal costThe internal sum matters because the specified changeovers need not be symmetric. When the block begins at the first job, the boundary terms correctly update the initial setup; the dummy return costs are zero. Processing times cancel.

At temperature $T>0$, simulated annealing accepts a move with probabilityWith uniformly sampled reversal pairs the proposal is symmetric, so this is the appropriate Metropolis–Hastings acceptance probability. Improvements and ties are always accepted; occasional uphill moves escape local minima. Repeatedly sample moves, gradually lower $T$, and retain the best schedule seen even if the current schedule worsens. Reversing a block of length two swaps adjacent jobs, so these moves connect the whole permutation space. A cooling schedule, iteration budget and restarts control practical performance. This is a heuristic at a finite budget; it does not certify global optimality unless paired with an exact bound or an appropriate limiting convergence argument.

For minimizing an energy $F(\theta )$, simulated annealing at temperature $T>0$ uses the Boltzmann distribution ${\pi }_T(\theta )\propto e^{-F(\theta )/T}$. At each temperature run a Metropolis–Hastings algorithm or Gibbs transition preserving that law, then reduce $T$. With a symmetric proposal, accept ${\theta }^{\prime }$ with probability $\min \{1,e^{-[F({\theta }^{\prime })-F(\theta )]/T}\}$: downhill moves are accepted and uphill moves remain possible. Keep the best state encountered. As temperature decreases, equilibrium mass favors global minima, provided the target is proper and the relevant concentration hypotheses hold. An arbitrary finite cooling run does not by itself prove global convergence.

Let $s={\sum }_{i=1}^m{x}_i$, $\bar{x}=s/m$ and $S={\sum }_i(x_i-\bar{x}{)}^2$. For the Poisson distribution model the observations must be nonnegative integers. Its log-likelihood isFor $s>0$, differentiation gives ${\ell }_P^{\prime }=-m+s/\lambda$ and ${\ell }_P^{\prime \prime }=-s/{\lambda }^2<0$. If $s=0$, the likelihood is decreasing and the maximizer is the boundary value zero. For the normal distribution model write $v={\sigma }^2>0$, givingFor each $v$, this is maximized at $\mu =\bar{x}$, and differentiating there gives $v=S/m$. HenceThe normal variance estimate has denominator $m$, not $m-1$. A finite positive normal maximum requires $S>0$; if all observations coincide, the likelihood is unbounded as $\mu =\bar{x},v\downarrow 0$. The normal annealing calculation below assumes $S>0$.

To maximize likelihood, choose the energy $-\ell$, so the annealing law is $L^{1/T}$, not $L^{-1/T}$. This sign is important in the Poisson request: literally inserting a positive log-likelihood into a minimizing Boltzmann law would give a nonnormalizable probability density function growing like $e^{m\lambda /T}$ at infinity. We use likelihood-power annealing with the maximizing sign.

For the normal distribution model, take base measure $d\mu dv$. The joint annealing probability density function isCompleting the square gives the Gibbs sampling conditional for $\mu$. Matching the conditional $v$ probability density function to the supplied inverse-gamma distribution convention givesIntegrating out $\mu$ contributes a factor $\sqrt{v}$, so the marginal law isThus this joint Boltzmann law is proper for $T<m/3$. Its variance marginal and the normal conditional both concentrate at the stated estimates as $T\downarrow 0$. For example, for $T<m/7$ its marginal mean and variance areAlso ${\mathbb{E}}_T(\mu -\bar{x}{)}^2=(T/m){\mathbb{E}}_{T}v\to 0$.

There is a direct convergence proof for the actual changing-temperature Gibbs algorithm, beyond convergence of its equilibrium probability densities. Start at a finite deterministic $v_0>0$, choose deterministic $0<T_n\le m/10$ with $T_n\to 0$, draw ${\mu }_n$ conditional on $v_{n-1}$, then draw $v_n$ conditional on ${\mu }_n$ using the two boxed distributions. Conditional normal moments giveThe inverse-gamma distribution first and second moments consequently yieldandIn the first recursion the coefficient of the preceding mean is at most $1/6$; in the second the coefficient of the preceding second moment is at most $1/8$. The means therefore stay bounded, and then so do the second moments. Letting $T_n\to 0$ in these formulas gives $\mathbb{E}{v}_n\to S/m$ and $\mathbb{E}{v}_n^2\to (S/m{)}^2$. Together with $\mathbb{E}({\mu }_n-\bar{x}{)}^2=T_n\mathbb{E}{v}_{n-1}/m\to 0$, this provesThis Gaussian likelihood Gibbs annealing convergence uses the explicit conditional structure and does not assume that one Gibbs sampling sweep is an exact equilibrium draw.

For the Poisson distribution model, the likelihood-power law with respect to $d\lambda$ has the normalized probability density functionsoThe mean tends to $\bar{x}$ and the variance to zero, proving convergence to a point mass at the Poisson maximum-likelihood estimate, including the zero-boundary case.

The Akaike information criterion is $2k-2\ell (\hat{\theta })$, counting one parameter for Poisson and two for normal. With $0\log 0=0$ and $S>0$, the two forms areandChoose the smaller criterion. Likelihood constants that differ between models, including the factorial and $2\pi$ terms, cannot be discarded.

For a fully specified trans-dimensional annealing for penalized likelihood, let $M=P$ or $N$ and defineUse the combined target, relative to counting measure on models and Lebesgue measure on their parameters,where $w_P,w_N>0$ are fixed reference weights. For $S>0$ and $0<T<m/3$ both model components are integrable. The factor $2T$ is a convenient temperature convention keeping the within-model laws exactly those already derived. The extra factor $e^{-k_M/T}$ makes the zero-temperature objective AIC rather than unpenalized likelihood.

Use, for example, probability $1/2$ for a model-change attempt in either model and probability $1/2$ for a within-model update. Within the Poisson distribution model draw a fresh gamma value from its boxed law; within the normal distribution model perform the boxed Gibbs sampling sweep. For a Poisson-to-normal proposal, draw $u\sim q(u)=N(0,{\tau }^2)$ with a fixed ${\tau }^2>0$, and setThe inverse normal-to-Poisson proposal is $\lambda =v$ with reverse auxiliary $u=\mu -v$. This dimension matching uses one auxiliary variable to augment the one-dimensional Poisson parameter space. The absolute Jacobian determinant isIf the forward model-jump selection probability is $b$ and the reverse probability is $d$, the reversible-jump Markov chain Monte Carlo acceptance ratio isAccept with probability $\min (1,R_{P\to N})$. For the reverse move compute $\lambda =v,u=\mu -v$ and useFor the suggested equal selection probabilities, $b=d=1/2$ and those factors cancel. The probability density function $q$ must still be included, despite symmetry of its normal distribution: it is an auxiliary draw in only the forward dimension-increasing proposal. Pairing a move with its inverse makes the accepted forward and reverse probability flows equal after the change of variables, proving detailed balance for each fixed-temperature model-switch kernel.

Cool through proper temperatures, allow enough model and parameter exploration at each stage, and retain the smallest observed $E_M$. The minima of the two energies are exactly the two AIC values above. Low-temperature equilibrium mass concentrates on the better criterion and its fitted parameters; if they tie, the minimizing set contains both models. Unlike the direct normal Gibbs argument, this multimodel exploration claim needs an appropriate cooling/mixing justification and is not guaranteed by an arbitrary short run.

Finally, an exact statistical comparison must put both likelihoods on the same observable and reference-measure convention. A Poisson distribution model is a probability mass function on counts, whereas the displayed normal distribution model is a continuous probability density function. The formulas above are the question's formal Gaussian working-likelihood comparison. A coherent exact normal approximation for count observations can instead use probabilities of rounding intervals; that changes its likelihood and generally loses the simple analytic normal estimates. This distinction matters when interpreting the numerical AIC difference, while leaving the dimension-matching and annealing construction applicable to properly specified likelihoods.

One limitation is finite useful storage capacity and interference. Under simple Hebbian learning, each additional pattern contributes cross-talk to the retrieval fields; correlated or excessive patterns can erase a memory's basin or destabilize the pattern itself. More structured learning can reduce this interference: covariance-based weights account for activity biases, and pseudoinverse-based rules can orthogonalize a set of linearly independent patterns. Sparse representations and suitable thresholds can also change the capacity tradeoff. These extensions require their own retrieval analysis; they do not permit unlimited robust storage in a finite network.

A second limitation is spurious attractors and entrapment in unintended local minima. Mixtures of memories or unrelated configurations can be fixed points, and deterministic energy descent cannot escape an already stable incorrect state. Stochastic updates that sometimes accept energy increases can explore other configurations, and simulated annealing can gradually reduce that randomness to favor lower energies. Better weight learning and basin shaping can reduce the spurious states. Finite-temperature escape is probabilistic, and a practical finite-time annealing schedule does not guarantee the desired memory or a global minimum.

Changing the learning rule addresses interference; changing the retrieval dynamics can address trapping. The objective must still be appropriate: the lowest energy pattern is not necessarily the memory best matching a particular noisy cue.

Represent a feasible allocation by a label for each item saying which bidder receives it. Every such label vector gives disjoint bundles covering all items, so the following heuristic optimization methods can search without violating allocation feasibility.

In local search, begin with any feasible partition and repeatedly make an improving move, such as transferring one item between bidders or exchanging two items. For a transfer $j:i\to r$, evaluate the changeStop when no allowed move improves the objective. Several starting partitions can avoid dependence on one local optimum, but no guarantee of a global optimum follows for general bids.

In simulated annealing, use the same feasible neighborhood but also accept a worsening move of loss $\Delta >0$ with probability $e^{-\Delta /T}$ at temperature $T$. Begin with a relatively high temperature, gradually cool, and retain the best allocation seen. Worsening moves can cross a barrier between local optima; a practical finite cooling schedule does not guarantee optimality.

In tabu search, retain a short memory of recent transfers or exchanges and temporarily prohibit their reversal. Select the best admissible move, possibly worsening the objective, to escape a local optimum. Permit an otherwise tabu move if it improves the best solution found, an aspiration rule. For the winner determination problem, bidder/item pairs or recent reverse transfers provide convenient tabu attributes. All three methods preserve the partition, but for arbitrary bids they are heuristics rather than algorithms with a proved constant approximation ratio.

For a maximization objective, simulated annealing accepts every improving proposed neighbor and accepts a worsening move of loss $\Delta$ with probability $\exp (-\Delta /T)$ at temperature $T>0$. Decreasing the temperature reduces exploratory moves. Retain the best feasible solution seen. Finite practical cooling schedules carry no general global-optimality guarantee.