Editing Automatic label placement (section)

==Integer Programming==

Some versions of the map label placement problem can be formulated as multiple choices integer programming (MCIP) problems where the objective function is to minimize the sum of numerical penalties for moving individual labels away from their optimal placement to avoid overlaps. The problem constraints are that each label be placed in one of a finite number of allowed positions on the map. (Or deleted from the map to allow other labels to be placed.)

A close to optimal solution to this MCIP can usually be found in a practical amount of computer time using Lagrangian relaxation to solve the dual formulation of the optimization problem.<ref>{{Cite journal |last=Bean |first=James C. |date=1984 |title=A Langrangian Algorithm for the Multiple Choice Integer Program |url=https://www.jstor.org/stable/170661 |journal=Operations Research |volume=32 |issue=5 |pages=1185–1193 |doi=10.1287/opre.32.5.1185 |jstor=170661 |issn=0030-364X}}</ref>

The first commercial solution to the map label problem, formulated as a MCIP problem and solved by Lagrangian relaxation, was to place well and seismic shot point labels on petroleum industry base maps.<ref>{{Cite web |last1=Zoraster |first1=Steven |last2=Bayer |first2=Stephen |date= |title=Practical Experience With a Map Label Placement Program |url=https://cartogis.org/docs/proceedings/archive/auto-carto-8/pdf/practical-experience-with-a-map-label-placement-algorithm.pdf |website=CaGIS |publisher=[[Cartography and Geographic Information Society]]}}</ref>

Since that first solution was published there have many other mathematical optimization algorithms proposed and used to solve this MCIP for other cartographic applications.