Digital Video Broadcasting (DVB).
In planning a DVB network, an interesting problem is that of determining the emission power of a given set of $ n$ transmitters so as to maximize territory coverage [21]. Suppose the territory is subdivided into $ m$ sufficiently small squared areas, considered as test points (TPs). A signal emitted from a transmitter is useful or interfering at a TP depending on the arrival delay. In the single frequency and fixed window model [21], for each TP $ i$ the signal quality constraint can be linearized as follows:
$\displaystyle \sum_{j=1}^{n} \ a_{ij} \ x_j \geq b_i,$
where the variable $ x_j$ indicates the emission power of the $ j$ th transmitter, subject to a mandatory upper bound given by the maximum power $ p_{\rm max}$ . The field strength $ a_{ij}$ of the signal arriving at TP $ i$ from transmitter $ j$ is positive (negative) for the useful (interfering) part of the signal, and $ b_i$ is the minimum field strength required to cover TP $ i$ with probability $ 0.95$ . Since total coverage is usually not achievable, one faces sparse instances of MaxFS with one inequality per TP, a variable per transmitter and mandatory upper (maximum power) and lower bounds for each variable. A reasonable discretization yields instances for the whole Italian territory with of the order of $ 55000$ inequalities in a few thousands of variables. To maximize the population covered, a weight can be assigned to each inequality (13) and one searches for a Feasible Subsystem (FS) of maximum total weight. See [21] for the modelling details.
Protein Folding Potentials.
As described in [16], the problem of modelling the energy function (potential) underlying the folding of amino acid sequences into proteins gives rise to large and dense linear systems with millions up to tens of millions inequalities in hundreds of variables. Let $ E({\bf s},{\bf t})$ denote the energy of sequence $ {\bf s}$ when folded into the three-dimensional structure $ {\bf t}$ and let $ {\bf t}_s^*$ be the native structure of sequence $ {\bf s}$ . The premise that the energy of the native structure is lower than that of any structure chosen from a set of “decoys” amounts to
$\displaystyle E({\bf s},{\bf t})-E({\bf s},{\bf t}_s^*)>0 \; \; \; \; \forall {\bf s}, \; \forall {\bf t} \neq {\bf t}_s^*.$ (14)
Focusing on the common features, potential modelling can then be formalized as the problem of approximating the unknown energy $ E$ by a linear combination of some appropriate basis function set $ \{ \phi_i({\bf s},{\bf t})\}_{1 \leq i \leq n}$ , i.e., by $ \tilde{E}({\bf s},{\bf t}) = \sum_{i=1}^{n} x_i \phi_i({\bf s},{\bf t})$ where $ {\bf x}$ is the vector of parameters. As a simple example, $ \phi_i({\bf s},{\bf t})$ may count the number of contacts between a certain pair of amino acids that appear when $ {\bf s}$ is folded into structure $ {\bf t}$ . Thus, by requiring that the potential models $ \tilde{E}$ satisfy (14), we have $ \sum_{i=1}^{n} x_i (\phi_i({\bf s},{\bf t})-\phi_i({\bf s},{\bf t}^*_{\bf s}))>0$ for all $ {\bf s}$ and all $ {\bf t} \neq {\bf t}_s^*$ . Since perfect structure recognition is unrealistic, these dense homogeneous systems are generally infeasible and one is interested in finding an $ {\bf x}$ satisfying as many inequalities (14) as possible [16].
As mentioned in the lower part of Table 1, these instances are much larger than the DVB ones, and the corresponding big- $ M$ formulations could not be solved within the time limit of two hours and did not provide any primal solution. For three out of the five first instances, our RTR variant yields in a very short amount of computing time a feasible subsystem containing more than $ 99.4\%$ of the inequalities in the original system, that is, a solution which is within $ 0.6\%$ from the optimum. Note, for example, that for prot3 the feasible subsystem with $ 249865$ inequalities found by the RTR variant after $ 9$ sec. is improved to size $ 250225$, with only $ 8$ violated inequalities, just after $ 92.85$ sec.
To further evaluate the quality of the RTR solutions, we have also considered five feasible systems with up to $ 400000$ inequalities in $ 301$ variables. For such systems, the MAX FS-optimal solution is obviously known and can be used for comparison purposes. It is worth emphasizing that, unlike linear programming solvers, our RTR variants deal with such instances (feasible systems) as if they were infeasible and strive to find an iterate satisfying as many inequalities as possible. The results are reported in the lower part of Table 1, where a “ $-$ ” indicates that the MIP solver performance on the big- $ M$ formulations is of no interest for these feasible systems. Our RTR method turns out to yield extremely good solutions (within 0.001% from the optimum) in less than $ 80$ sec., even for the largest instance with $ 401115$ inequalities. Note that, on the same PC, Cplex 8.1 MIP solver could not even start optimizing the big-M formulation for the feasible instances with more than $300000$ inequalities due to excessive memory requirements.
Discriminant Analysis.
Discriminant analysis. To assess the performance of the RTR method on small instances with known optimal solutions, we have considered the collection of linear classification instances used in [8]. The general problem is to determine the values of the parameters of a hyperplane so as to separate two groups of data points as well as possible. In Table 2 RTR results are compared with those obtained with the exact method based on Combinatorial Benders’ Cuts (CBC) [8] and with Cplex 8.1 MIP solver applied to the big- $ M$ formulations. The focus here is on the instances with more than 300 inequalities. We have adopted a simple two-phase approach: after running a given number of RTR iterations ( $ 5000$ ), we consider the inequalities in the largest feasible subsystem found, $ F$ , as mandatory and we apply a MIP solver to the reduced big- $ M$ formulation which aims at identifying among the other inequalities those that are consistent with $ F$.
CAPTION: Table 2: Comparison between the two-phase RTR variant, the CBC method and Cplex 8.1 MIP solver applied to the big-M formulations for some small classificatio instances. A “-” means that the time limit has been reached, whereas “ $ \star $ ” indicates proven optimal solutions. Computing times are expressed in seconds.
RTR+ CPLEX CBC
$ m$ $ n$ FS size time FS size time FS size time
BCW-367 367 10 359 $ ^\star$ 1.31 359 $ ^\star$ 365 359 $ ^\star$ 1
BCW-683 683 10 669 6.13 673 $ ^\star$ 6750 673 $ ^\star$ 10
BusVan445 445 18 436 4.76 436 – 437 $ ^\star$ 102
Bv-os-376 376 18 363 5.50 367 – 368 $ ^\star$ 125
Solar-flare-323 323 12 284 1.03 282 – 285 $ ^\star$ 3
Flags-169 169 29 159 1.24 159 – 159 –
Horse-colic-253 253 26 240 7.60 240 – 240 –
Horse-colic-185 183 26 173 3.08 173 – 173 –
Solar-flare-1066 1066 12 817 6.56 796 – 782 –
823 139.27
The upper part of Table 2 corresponds to the instances that are solved optimally with both the CBC method and the big-M formulations, the middle part to those solved only by CBC, and the lower part to the instances that could not be solved by either of them within the time limit of $ 10000$ sec. For the CBC method and the big-M formulations, we report either the optimal solution and the computing time to find it (if it is reached within the time limit) or the best lower bound. For the RTR method, we report the value of the best solution and the time needed to find it. Note that, for the instances that are easily solved by CBC, the RTR variant yields near-optimal solutions within less than $ 7$ seconds. For the instances that could not be solved to optimality within the time limit, RTR compares well with the two exact approaches since it provides the best solutions in extremely short computing times.