Back to SYMPHONY Home Page
To track problem variables, each must be assigned a unique user index by which the user can always identify the variable. For instance, if the variables correspond to the edges of a graph, as in the Traveling Salesman Problem, then the index can simply be derived from a lexicographic ordering of these edges. This indexing requirement means that the user must have a priori knowledge of all problem variables. For most combinatorial models, this does not present a problem. However, for some set partitioning models, for instance, the number of columns may not be known in advance. This restriction will be eliminated in a future release of SYMPHONY.
The problem variables are divided into two sets, the base variables and the extra variables. The base variables remain in the problem at all times, whereas the extra variables can be removed by reduced cost or logical fixing, as well as generated by column generation (see Section 5.2.2 for details). There is no theoretical difference between base variables and extra variables; however, designating a base set of variables can increase efficiency since they only need to be sent out to each process once at the beginning of the computation. Also, because they can move in and out of the problem, maintaining extra variables requires additional bookkeeping and computation. If the user has reason to believe a priori that a variable is ``good'' or has a high probability of being involved in an optimal solution to the problem, then that variable should be designated as a base variable. For instance, in graph-based minimization problems, such as the TSP, the cheapest k edges adjacent to each node could be designated as the base set.
SYMPHONY supports variable fixing by reduced cost, as well as dynamic column generation. The variables included in the current LP relaxation are called the active variables. It is up to the user to designate which variables will be active in the root node. Typically, only base variables are active, but the user may want to include some extra variables as well. The details of variable fixing and dynamic column generation are given in Section 5.2.2.