This repository contains code used in the article

Network Coding: An Optimization Approach by Christopher Hojny, Altan B. Kılıç, and Alberto Ravagani.

This README provides information about the structure of the code and how it can be used.

Using the Code

The code can executed by calling

	 ./test.py <alphabet> <codesize> <optional parameters>

<alphabet> and <codesize> are positive integers specifying the size of the alphabet and the size of the code, respectively. Moreover, the following optional parameters control:

  -i<name> the name of the instance to be solved
  -s<0/1>  whether symmetry handling is enabled
  -p<0/1>  whether presolving is enabled
  -c<0/1>  whether cutting planes shall be added

The call

./test.py 4 2 -ibutterfly -s1 -c0

then checks whether there exists a code of size 2 on an alphabet of size 4 for the butterfly network. Symmetry handling is enabled and cutting planes are disabled.

When the code terminates, it either reports there does not exist an unambiguous code or it provides the maps at each node, which specify which output is generated by a certain input, together with the code words on the outgoing arcs of the source. If a map reports ? for a certain input, the image is not specified, because no code word sends this input to the corresponding node.

Structure of the Code

The supported network instances are hard-coded in instances.py.

To call the code, the additional software Gurobi and its Python interface are needed. If test.py is called as described above, the corresponding network is queried from instances.py. Afterwards, instances.py builds the mixed-integer nonlinear program as specified in the article and Gurobi solves this model.