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
[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
