The Solution of Large 0–1 Integer Programming Problems Encountered in Automated Cartography | Zendy

Steven Zoraster | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

The Solution of Large 0–1 Integer Programming Problems Encountered in Automated Cartography

Author(s) -

Steven Zoraster

Publication year - 1990

Publication title -

operations research

Language(s) - English

Resource type - Journals

eISSN - 1526-5463

pISSN - 0030-364X

DOI - 10.1287/opre.38.5.752

Subject(s) - integer programming , mathematical optimization , computer science , heuristic , branch and price , integer (computer science) , combinatorial optimization , legibility , optimization problem , mathematics , programming language , art , visual arts

The placement of text on a map to maximize map legibility, while avoiding graphic overplotting, is a problem in combinatorial optimization. This particular optimization problem can be formulated as a multiple choice integer programming problem, and the integer programming problem has a structure that can be exploited, using a Lagrangian heuristic, to obtain a cost effective solution, even when tens of thousands of variables and thousands of constraints are involved. This paper presents the mathematical formulation of the map label placement problem and describes a computer program implemented to solve it.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research