  This paper considers a base station that delivers packets to multiple
receivers through a sequence of coded transmissions. All receivers overhear the
same transmissions. Each receiver may already have some of the packets as side
information, and requests another subset of the packets. This problem is known
as the index coding problem and can be represented by a bipartite digraph. An
integer linear program is developed that provides a lower bound on the minimum
number of transmissions required for any coding algorithm. Conversely, its
linear programming relaxation is shown to provide an upper bound that is
achievable by a simple form of vector linear coding. Thus, the information
theoretic optimum is bounded by the integrality gap between the integer program
and its linear relaxation. In the special case when the digraph has a planar
structure, the integrality gap is shown to be zero, so that exact optimality is
achieved. Finally, for non-planar problems, an enhanced integer program is
constructed that provides a smaller integrality gap. The dual of this problem
corresponds to a more sophisticated partial clique coding strategy that
time-shares between Reed-Solomon erasure codes. This work illuminates the
relationship between index coding, duality, and integrality gaps between
integer programs and their linear relaxations.
