Editing Weak ordering (section)

==Applications==

As mentioned above, weak orders have applications in utility theory.<ref name="roberts"/> In [[linear programming]] and other types of [[combinatorial optimization]] problem, the prioritization of solutions or of bases is often given by a weak order, determined by a real-valued [[objective function]]; the phenomenon of ties in these orderings is called "degeneracy", and several types of tie-breaking rule have been used to refine this weak ordering into a total ordering in order to prevent problems caused by degeneracy.<ref>{{citation|title=Linear Programming|first=Vašek|last=Chvátal|authorlink=Vašek Chvátal|publisher=Macmillan|year=1983|isbn=9780716715870|pages=29–38|url=https://books.google.com/books?id=DN20_tW_BV0C&pg=PA29}}.</ref>

Weak orders have also been used in [[computer science]], in [[partition refinement]] based algorithms for [[lexicographic breadth-first search]] and [[Coffman–Graham algorithm|lexicographic topological ordering]]. In these algorithms, a weak ordering on the vertices of a graph (represented as a family of sets that [[Partition of a set|partition]] the vertices, together with a [[doubly linked list]] providing a total order on the sets) is gradually refined over the course of the algorithm, eventually producing a total ordering that is the output of the algorithm.<ref>{{citation|last1=Habib|first1=Michel|last2=Paul|first2=Christophe|last3=Viennot|first3=Laurent|doi=10.1142/S0129054199000125|issue=2|journal=International Journal of Foundations of Computer Science|mr=1759929|pages=147–170|title=Partition refinement techniques: an interesting algorithmic tool kit|volume=10|year=1999}}.</ref>

In the [[C++ Standard Library|Standard Library]] for the [[C++]] programming language, the [[Associative containers (C++)|set and multiset data types]] sort their input by a comparison function that is specified at the time of template instantiation, and that is assumed to implement a strict weak ordering.<ref name="cpp"/>