The standard network problems such as shortest path and min-cost flow are easily expressed as linear programming problems. Here is a network problem that is somewhat more challenging both in solving and in modeling.
We have a bipartite graph (like in the transportation problem):
The task is to find the largest sub-graph that is complete (i.e. all selected nodes on the left are connected to all selected nodes on the right). The size is measured as number of edges. In this small case we would have:
A first Mixed Integer Quadratic Programming model could look like:
This is a non-convex problem. Cplex needs a special option to solve this: OptimalityTarget 3. After that we see a few interesting things in the log file. The first are some scary messages. I assume this is not very harmfull (we find the optimal solution), but it surely looks dangerous:
* 610+ 367 40.0000 405.7801 914.45%
The second interesting thing is how large the gap is at the end of the search:
Found incumbent of value 45.000000 after 54.77 sec. (15071.32 ticks)
A MIP model can be developed around the idea that a binary multiplication y=x1*x2 is easily linearized:
y ≥ x1+x2-1
y ≤ x1
y ≤ x2
In our case we want that a link e(i,j) exists if both x(i) and y(j) are selected. I.e. e(i,j) = x(i)*x(j). As we are maximizing the number of e(i,j)’s we can drop the first inequality in the linearization. Furthermore we can relax e(i,j) to be continuous between zero and one (it will be integer valued automatically). In the model below we do this by setting the branching priority to infinity.
Finally if there is no link between x(i) and y(j) we forbid both to be selected.
This model is somewhat smart in the sense that only e(i,j)’s are generated where there exist links between i and j (i.e. if a(i,j) exists).
Relaxing the e(i,j)’s does not have much of an impact on Cplex. It will reintroduce the variables as binary, as we can see in the log:
Tried aggregator 1 time.
For a larger problem with 100 + 100 nodes and 2000 arcs (20% density) we find the optimal solution in 25 seconds and prove optimality in 7 minutes.
Using a display of the initial arcs and the selected ones gives another interpretation of this problem:
---- 47 SET a links
j1 j2 j3 j4 j5 j6 j7 j8
i1 YES YES YES YES YES
---- 47 VARIABLE e.L selected links
j1 j5 j6
i1 1 1 1
I.e. select rows and columns such that all entries are YES (and choose the selection with the maximum number of entries).
Some more MIP formulations can be found in:
V. Acuna, C. E. Ferreira, A. S. Freire and E. Moreno: “On the maximum edge biclique packing problem: formulations and computational experiments,” 2010.