I recently posted a series of eight articles on my GitHub Pages blog.

[Here is the general introduction to the articles…]

The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

The knapsack problem and many other problems in combinatorial optimization require the selection of a subset of items to maximize an objective function subject to constraints. A common approach to solving these problems algorithmically involves recursively generating sequences of items of increasing length in a search for the best subset that meets the constraints.

I applied this kind of approach using SQL for a number of problems, starting in January 2013 with A Simple SQL Solution for the Knapsack Problem (SKP-1), and I wrote a summary article, Knapsacks and Networks in SQL
, in December 2017 when I put the code onto GitHub, sql_demos – Brendan’s repo for interesting SQL.

Here is a series of eight articles that aim to provide a more formal treatment of algorithms for item sequence generation and optimization, together with practical implementations, examples and verification techniques in SQL and PL/SQL.

List of Articles

• OPICO 1: Algorithms for Item Sequence Generation
• OPICO 2: SQL for Item Sequence Generation
• OPICO 3: Algorithms for Item/Category Optimization
• OPICO 4: Recursive SQL for Item/Category Optimization
• OPICO 5: Tuning Recursive SQL for Item/Category Optimization
• OPICO 6: Mixed SQL and PL/SQL Methods for Item/Category Optimization
• OPICO 7: Verification
• OPICO 8: Automation

GitHub

Twitter

[Here is the conclusion to the articles…]

We can list here some of the features and concepts considered in the whole series.

Sequence Generation

• 4 types of sequence defined
• sequence generation explained via recursion…
• …implemented by recursion and by iteration

Optimization Problems

• sequence truncation using simple maths
• value filtering techniques with approximation and bounding
• two-level iterative refinement methods

SQL

• recursive SQL
• materializing subqueries via hints or use of temporary tables
• cycles and some anomalies
• storing sequences of items in SQL by concatenation, nested tables, and linking tables
• index organised tables
• partitioned outer joins
• splitting concatenated lists into items via row-generation
• combining lists of items into concatenated strings by aggregation
• passing bind variables into views via system contexts
• automated generation of execution plans

PL/SQL

• PL/SQL with embedded SQL as alternative solution methods to recursive SQL…
• …with sequence generation by both recursion and iteration, with performance comparisons
• use of arrays and temporary tables for intermediate storage, with performance comparisons
• methods for compact storage of sequences of items
• use of PL/SQL functions in SQL and performance effects of context switching
• automated code timing

Verification Techniques

• problem abstraction
• maths
• multiple datasets
• multiple solution methods
• perturbation analysis
• unit testing, with The Math Function Unit Testing Design Pattern

Automation

• installation
• running the solution methods
• code instrumentation
• unit testing
• blog internal links hierarchy