Generation of Near-Optimal Solutions Using ILP-Guided Sampling

Ashwin Srinivasan, Gautam Shroff, Lovekesh Vig, Sarmimala Saikia, Puneet AgarwalarXiv 2016 · arXiv

Optimization is often a game of hide-and-seek in a massive search space. While numerical methods are the standard tool, many real-world problems—like scheduling trains or mastering chess endgames—come with a wealth of qualitative "expert knowledge" that is hard to cram into a spreadsheet.

This paper introduces a way to let that expert knowledge lead the search. By combining Estimation of Distribution Algorithms (EDAs) with Inductive Logic Programming (ILP), the authors present a framework called EOIS that uses logical rules to "sniff out" near-optimal solutions far more efficiently than random searching.

TL;DR

The authors propose EOIS, a framework that uses Inductive Logic Programming to build logical models of "good" solutions, which then guide the sampling process in evolutionary optimization. This approach significantly outperforms random sampling, finding near-optimal solutions for complex tasks like job-shop scheduling and chess endgames with much higher precision.

What Problem Does This Paper Address?

Standard optimization techniques often struggle with "intractable" problems where the search space is too large for brute force. While heuristic search methods like EDAs try to learn the probability distribution of good solutions, they typically use probabilistic models (like Bayesian Networks) that aren't great at incorporating complex, rule-based domain knowledge.

For example, a rail dispatcher knows that "a high-priority train should be preferred unless it causes a massive delay for others." Translating this qualitative rule into the linear inequalities required by traditional optimizers is incredibly complex. The authors wanted to find a way to use first-order logic—the natural language of expert rules—to guide the optimization process directly.

Methods

The core contribution is the EOIS (Evolutionary Optimisation using ILP-Assisted Sampling) procedure. It works in an iterative loop:

  1. Labeling: Take a population of solutions and label them as "good" or "bad" based on a cost threshold.
  2. Model Construction (The ILP Step): Use an ILP engine (specifically Aleph) to find logical rules that distinguish the "good" solutions from the "bad" ones, using provided background knowledge.
  3. Guided Sampling: Instead of just guessing new solutions, use the induced logical rules as a template. Generate new candidate solutions that satisfy these rules.
  4. Refinement: Lower the cost threshold and repeat, narrowing the search toward the absolute optimum.

This differs from standard EDAs by replacing simple probabilistic models with expressive logic programs that can capture intricate relationships between variables.

Datasets

The researchers tested their approach on two distinct synthetic benchmarks:

  • KRK Chess Endgame: Predicting the "depth-of-win" (moves to checkmate) for a White King and Rook against a Black King. This is a classic ILP benchmark with ~28,000 legal positions.
  • 5x5 Job-Shop Scheduling: A notoriously hard optimization problem involving scheduling 25 tasks across 5 machines to minimize total time.
Cost distribution for the Chess endgame dataset.

Key Insights and Ideas

  • Logic is More Expressive: The authors point out that a simple logical relation like XOR requires a complex set of linear inequalities to represent numerically. Logic allows for a much cleaner, more intuitive representation of domain constraints.
  • The "Relevance" Factor: The quality of the background knowledge is paramount. If you give the system "low-relevance" rules (like basic board geometry), it struggles. If you give it "high-relevance" rules (like concepts of "cornering" the king), the optimization speed skyrockets.
Figure 6: Precision (a), and recall of near-optimal instances (b) of the EOIS procedure with background knowledge of low relevance to near-optimal solutions. The results are for Chess, with Blow denoting background predicates that simply define the geometry of the board, using the predicates less than and adjacent. These predicates form the background knowledge for most ILP applications to the problem of detecting illegal positions in the KRK endgame. Bhigh denotes background used previously, with high relevance to low depths-of-win. The numbers in parentheses in (b) are the number of training instances as before.
  • Precision vs. Recall: The ILP model acts as a high-quality filter. It doesn't just find more solutions; it ensures that the solutions it finds are much more likely to be high-quality compared to a random draw.

Key Results

The quantitative gains were substantial across both domains:

  • Massive Precision Boost: In the Chess domain, by the third iteration, the ILP-guided model was 409 times more likely to generate a "good" instance than simple random sampling.
  • Finding the Needle in the Haystack: For Job-Shop scheduling, the ILP-guided search found 36 near-optimal instances in a sample where random sampling would only be expected to find 9.
  • Efficiency: The authors calculated that to find the same number of near-optimal solutions, random sampling would require 4 to 10 times more samples than their EOIS method.
Precision gains in the Chess domain across iterations.

Limitations and Future Work

  • Computational Trade-off: Building an ILP model takes time. While it saves time by requiring fewer samples, there is a break-even point where the overhead of logic programming might outweigh the benefits for simpler problems.
  • Knowledge Dependency: The system is only as good as the background knowledge provided. Automating the discovery of relevant background knowledge remains a challenge.
  • Future Directions: The authors suggest moving toward Probabilistic ILP to allow for more nuanced, non-uniform sampling and exploring ways to "recycle" logical theories across iterations to save on computation time.

Summary updated

Abstract

Our interest in this paper is in optimisation problems that are intractable to solve by direct numerical optimisation, but nevertheless have significant amounts of relevant domain-specific knowledge. The category of heuristic search techniques known as estimation of distribution algorithms (EDAs) seek to incrementally sample from probability distributions in which optimal (or near-optimal) solutions have increasingly higher probabilities. Can we use domain knowledge to assist the estimation of these distributions? To answer this in the affirmative, we need: (a)a general-purpose technique for the incorporation of domain knowledge when constructing models for optimal values; and (b)a way of using these models to generate new data samples. Here we investigate a combination of the use of Inductive Logic Programming (ILP) for (a), and standard logic-programming machinery to generate new samples for (b). Specifically, on each iteration of distribution estimation, an ILP engine is used to construct a model for good solutions. The resulting theory is then used to guide the generation of new data instances, which are now restricted to those derivable using the ILP model in conjunction with the background knowledge). We demonstrate the approach on two optimisation problems (predicting optimal depth-of-win for the KRK endgame, and job-shop scheduling). Our results are promising: (a)On each iteration of distribution estimation, samples obtained with an ILP theory have a substantially greater proportion of good solutions than samples without a theory; and (b)On termination of distribution estimation, samples obtained with an ILP theory contain more near-optimal samples than samples without a theory. Taken together, these results suggest that the use of ILP-constructed theories could be a useful technique for incorporating complex domain-knowledge into estimation distribution procedures.
BibTeX
@misc{srinivasan2016generation,
  author = {Ashwin Srinivasan and Gautam Shroff and Lovekesh Vig and Sarmimala Saikia and Puneet Agarwal},
  title = {{Generation of Near-Optimal Solutions Using ILP-Guided Sampling}},
  year = {2016},
  eprint = {1608.01093},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1608.01093},
}
Figure