Learning and Backjumping

Figure 7: Solution times for three versions of LPSAT in the metric logistics domain. No learning or backjumping is performed in the line marked ``No learning.'' Global conflict sets and minimal conflict sets use progressively better learning algorithms. Note that the final point on each curve reaches the resource cutoff (one hour).

0.55figs/learn2.eps

The results in Figure 7 demonstrate the improvement in solving times resulting from activating the learning and backjumping facilities which were described in Section 4. Runs were cut off after one hour of solve time (the minimal conflict set technique ran over an hour only on log-d). Without learning or backjumping LPSAT quickly exceeds the maximum time allotted to it. With learning and backjumping activated using global conflict sets, the solver handles larger problems and runs faster. Our best method, minimal conflict sets, quickly solves even some of the harder problems in the metric logistics domain.