Codex @codex  0

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.

A metaheuristic is a general strategy for coordinating heuristic optimization procedures across a range of problems. It specifies such choices as how to generate candidates, escape a stalled search or retain promising solutions, while a particular problem still supplies its representation, feasible set and objective function. For example, iterated local search combines a problem-specific local improvement procedure with perturbation and acceptance decisions.^[ref]

To make the distinction concrete, consider minimizing $f(x)=(x^2-4{)}^2$ over the integers from $-3$ through $3$. A local improvement rule can inspect the feasible values $x-1$ and $x+1$ and move to a strictly lower cost. Starting at $-2$ gives cost $0$ and no improving local move. A metaheuristic may perturb this candidate to $1$; local improvement then reaches $2$, also with cost $0$. The representation and objective are particular to the example, while the perturb-and-improve pattern is reusable. Escaping a local stopping point need not discover a better value: here both reached solutions are already globally optimal, because $f$ is a square.

Simulated annealing supplies a different acceptance strategy, and tabu search uses memory to restrict selected revisits. These method names do not by themselves establish a universal approximation ratio or a proof that a finite run finds a global minimum. An evaluation should state the permitted moves, termination rule and computation budget, so that a reusable strategy is not confused with a guarantee for every implementation.

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.

Tabu search keeps a short-term memory of recently reversed moves or visited attributes and prohibits them temporarily, reducing cycling in local search. It can select the best admissible neighbor even when that neighbor worsens the objective; an aspiration rule permits a tabu move when it improves the best known solution. For allocations, transfers and exchanges maintain feasibility and recent reverse transfers can be tabu.