Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs

A parameterized problem Π can be considered as a set of pairs (

I

,

k

) where

I

is the main part and

k

(usually an integer) is the parameter. Π is called fixed-parameter tractable (FPT) if membership of (

I

,

k

) in Π can be decided in time

O

(

f

(

k

)|

I

|

c

), where |

I

| denotes the size of

I

,

f

(

k

) is a computable function, and

c

is a constant independent of

k

and

I

. An algorithm of complexity

O

(

f

(

k

)|

I

|

c

) is called a fixed-parameter algorithm.

It often happens that although a problem is FPT, the practitioners prefer to use imprecise heuristic methods to solve the problem in the real-world situation simply because of the fact that the heuristic methods are faster. In this paper we argue that in this situation a fixed-parameter algorithm for the given problem may be still of a considerable practical use. In particular, the fixed-parameter algorithm can be used to evaluate the approximation quality of heuristic approaches.

To demonstrate this way of application of fixed-parameter algorithms, we consider the problem of extracting a maximum-size reflected network in a linear program. We evaluate a state-of-the-art heuristic SGA and two variations of it with a new heuristic and with an exact algorithm. The new heuristic and algorithm use fixed-parameter tractable procedures. The new heuristic turned out to be of little practical interest, but the exact algorithm is of interest when the network size is close to that of the linear program especially if the exact algorithm is used in conjunction with SGA. Another conclusion which has a large practical interest is that some variant of SGA can be the best choice because in most cases it returns optimal solutions; previously it was disregarded because comparing to the other heuristics it improved the solution insignificantly at the cost of much larger running times.