Graph connectivity as constraints

I was generating, for an example model, a random, sparse, directed graph. Unfortunately, when sparse enough, this is likely to yield a graph that is not connected. Here is my first attempt.

Nodes

I generate simply \(n=25\) nodes with \((x,y)\) coordinates from a uniform distribution \(U(0,100)\). This looks like:

\(n=25\) nodes randomly placed

MAX-CUT

The MAX-CUT problem is quite famous [1]. It can be stated as follows:

Given an undirected graph \(G=(V,E)\), split the nodes into two sets. Maximize the number of edges that have one node in each set.

Here is an example using a random sparse graph:

Reallocate people: a very small but interesting LP

U-Haul Moving Van [link]

This is a strange little problem [1]. We have individuals (of different categories) and regions with a given capacity. The initial set of assigned persons fits within the capacity of each region. Now a new batch of individuals arrives with their chosen zones. Unfortunately, the total demand (old + new individuals) does not fit anymore in all cases. This means we need to reallocate people. We can do this at a price (the costs are given). What is the optimal (least cost) new allocation?

A network model: Pyomo vs GAMS

Network models are an important class of optimization models, in itself but also as part of larger models. In [1] a nice presentation is given on how to set up a network model in the Python-based modeling tool Pyomo.

 

The simple shortest path problem is reproduced here:

Minimum Spanning Trees in Math Programming Models

Algorithms for the Minimum Spanning Tree (MST) problem are readily available. However, sometimes we want to solve this problem inside a Mathematical Programming model. Usually, this is for two reasons:

• We have some side constraints
• Or as part of a larger model

These reasons are essentially the same (a matter of gradation). Embedding an MST inside a model is not totally trivial.

Data

I used in our models the data from [1]. This data set has distances for 42 US cities.

----    298 SET cities  

Manchester, N.H.    ,    Montpelier, Vt.     ,    Detroit, Mich.      ,    Cleveland, Ohio     ,    Charleston, W.Va.   
Louisville, Ky.     ,    Indianapolis, Ind.  ,    Chicago, Ill.       ,    Milwaukee, Wis.     ,    Minneapolis, Minn.  
Pierre, S.D.        ,    Bismarck, N.D.      ,    Helena, Mont.       ,    Seattle, Wash.      ,    Portland, Ore.      
Boise, Idaho        ,    Salt Lake City, Utah,    Carson City, Nevada ,    Los Angeles, Calif. ,    Phoenix, Ariz.      
Santa Fe, N.M.      ,    Denver, Colo.       ,    Cheyenne, Wyo.      ,    Omaha, Neb.         ,    Des Moines, Iowa    
Kansas City, Mo.    ,    Topeka, Kans.       ,    Oklahoma City, Okla.,    Dallas, Tex.        ,    Little Rock, Ark.   
Memphis, Tenn.      ,    Jackson, Miss.      ,    New Orleans, La.    ,    Birmingham, Ala.    ,    Atlanta, Ga.        
Jacksonville, Fla.  ,    Columbia, S.C.      ,    Raleigh, N.C.       ,    Richmond, Va.       ,    Washington, D.C.    
Boston, Mass.       ,    Portland, Me.       

The original data set is called dantzig42 from TSPLIB [8].

An optimal spanning tree can look like:

Directed vs undirected networks in math programming models

Many practical optimization models contain some network structures. In virtually all cases, these networks are modeled as directed graphs. I.e., between nodes \(i\) and \(j\), we consider arcs \(i \rightarrow j\) and \(j \rightarrow i\). In graph theory, it is very customary to talk about undirected graphs. In this case, there is just one link between nodes \(i\) and \(j\). Why am I using directed graphs, with two uni-directional arcs for each pair of nodes? I will try to answer this in this post.

As an example, let's consider the shortest path problem. This is really the same as a min-cost problem. I took the following data (from [1]):