|
|
|
Quick Overview
|
Here you can find a number of recursive algorithms for obtaining solution(s) to the following integer linear
program (ILP) problem efficiently:
where A is an N by K binary-valued matrix. The weight vector w has a size of K with non-negative
elements. x is the binary-valued decision vector to be optimized with size K. This problem is related
to maximum set packing which appears in a variety of applications, including instantaneously decodable
network coding. In the context of set packing, the condition in (2) means that the solution should consist
of disjoint sets. More information on the set packing problem can be found in [1].
In the context of network coding, x shows the packets to be mixed together. The decision is made based
on receiver demands which is stored in A (a zero at row i and column j of A means that the receiver
i has decoded packet j, and a one means otherwise) and also based on the packet importance which is
stored in w. The packet importance could, for example, be the number of receivers that have not decoded
a packet yet. The condition in (2) guarantees instantaneous decodability of packets. That is, no two or
more new packets, which are not decoded by a receiver, can be mixed together. For more information
about our specific network coding problem see [2].
An outline of the recursive algorithm for finding the optimal solution to (1)-(2) is provided in [2] (see
Section III). The Matlab code and associated DLL are given here. It is noted that finding the optimal
solution to set packing is in general NP-hard. However, where N is reasonably sized compared to K, the
optimal solution can be found very efficiently. Roughly speaking, a large N results in many constrains
on the decision variables and hence the search space can be pruned very rapidly.
In other cases, one can use the same program to truncate the search as desired and to find possibly
suboptimal solutions much faster (for example, linearly with K). A number of heuristic algorithms can
be found in [2] (see section V). Heuristics 1 and 2 have been implemented in the Matlab version of the
code provided.
| REFERENCES:
|
[1] D. Bertsimas and R. Weissmantel, "Optimization Over Integers," Belmont, Massachusetts: Dynamic Ideas, 2005.
[2] P. Sadeghi, R. Shams and D. Traskov, "An optimal adaptive network coding scheme for minimizing decoding delay in broadcast erasure channels," submitted to EURASIP J. Wireless Commun. and Networking (under review), Aug. 2009
|
Download the Code
|
You can find the source code for finding efficient solutions of the above problem here.
The methods are described in the following publication:
"An Optimal Adaptive Network Coding Scheme for Minimizing
Decoding Delay in Broadcast Erasure Channels".
|
|
|