Optimization Problems with Items and Categories in Oracle – Intro

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.

  • Knapsack problem
  • 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

    GitHub

  • Optimization Problems with Items and Categories in Oracle
  • Twitter

  • Thread with Short Recordings
  • [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

    Automation

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






    Unit Testing, Scenarios and Categories: The SCAN Method – Intro

    The art of unit testing lies in choosing a set of scenarios that will produce a high degree of confidence in the functioning of the unit under test across the often very large range of possible inputs.

    This article, Unit Testing, Scenarios and Categories: The SCAN Method, posted on my new GitHub blog, discusses how to do this, and proposes a method introduced in a recent GitHub project, called Scenario Category ANalysis, or SCAN for short.

    It begins with a section on background that includes a link to a 2018 presentation on unit testing that introduced the concept of domain partitioning as a way of breaking infinite input spaces into a finite set of subspaces. This concept is explained here, followed by a discussion of how domain categories can form the basis for a practical approach to breaking up the input space. There is a section with examples of use of category sets to develop unit test scenarios taken from a range of my own Oracle GitHub projects.

    Next, Scenario Category ANalysis (SCAN) is outlined as a systematic method for deriving unit test scenarios. We conclude with a section showing the application of the method to three examples using base code from third-party articles, taken from the GitHub project on the SCAN method.


    Scanners IMDB

    There is an mp4 recording briefly (2m13s) going through the sections of the blog post:

    Twitter recording

    Contents

    The contents of the article are listed below. Click on the link above to access the article.






    SQL for Recursive Generation of Item Sequences

    Oracle introduced recursive subquery factoring in version 11.2 of its database software. This offered a new way to write hierarchical queries, in addition to its Connect By clause, for navigating tree structures, such as an HR employee management hierarchy. It also offered the possibility to solve a wider range of problems using its more powerful form of recursion, including combinatorial optimization problems such as bin fitting (or knapsack) problems. I used the new technique to solve a number of such problems on this blog, starting in January 2013 with A Simple SQL Solution for the Knapsack Problem (SKP-1).

    In this article, I focus on how the technique may be used to generate the sequences of items that form the basis of the solutions for the larger problems. In general we assume that we have a set of n items with unique identifiers, from which we want to form sequences of r items. Here are some definitions from Wikipedia to help us classify the different types of sequence possible:

    Set (mathematics)

    In mathematics, a set is a well-defined collection of distinct objects, considered as an object in its own right

    Multiset

    In mathematics, a multiset (aka bag or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements

    Permutation

    In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order

    Combination

    In mathematics, a combination is a selection of items from a collection, such that (unlike permutations) the order of selection does not matter

    We can look for all sequences of r items from n, of four different types, based on the concepts above of:

    1. Set/Permutation – items may not repeat and order matters
    2. Set/Combination – items may not repeat and order does not matter
    3. Multiset/Permutation – items may repeat and order matters
    4. Multiset/Combination – items may repeat and order does not matter

    Set/Permutation – items may not repeat and order matters

    Suppose we have SP(r-1), the set of all (r-1)-tuples of type Set/Permutation, we can generate SP(r) by forming a set of new r-tuples from each (r-1)-tuple t(r-1)(j):

    For each item i, add i on to t(r-1)(j):

    t(r)(ij) = (t(r-1)(j), i)

    Set/Combination – items may not repeat and order does not matter

    Multiset/Permutation – items may repeat and order matters

    Multiset/Combination – items may repeat and order does not matter

    First we define the different types of sequences that are possible.

    Initially we want to generate a set of all sequences satisfying certain generic conditions.
    The combination of kratom and weed has very good benefits for you health in kratommasters.com you can find more info about this two products