tree connectivity constraints

A guide to inexact contiguity constraints

Categories Combinatorial Optimization, Integer Programming, Network Optimization Tags , , , ,

For decades, researchers have complained that contiguity constraints make problems like districting much harder than other combinatorial optimization problems. This has prompted the use of integer programming models with inexact contiguity constraints that may be fast in practice but are invalid in the sense that they cut off or “overlook” some contiguous solutions. Examples include … Read more

A Surface-Based Formulation of the Traveling Salesman Problem

Categories (Mixed) Integer Linear Programming, Other Topics Tags , , , ,

We present an exact formulation of the symmetric Traveling Salesman Problem (TSP) that replaces the classical edge-selection view with a surface-building approach. Instead of selecting edges to form a cycle, the model selects a set of connected triangles where the boundary of the resulting surface forms the tour. This method yields a mixed-integer linear programming … Read more