TL;DR I built a heroku web app to solve the subset sum problem.

Intro

So my wife is an accountant and we were wondering if a subset sum algorithm would help finding suspicious ledger accounts in the trial balance. Our reasoning for using a subset sum algorithm is that given a known dollar number of credit/debit difference (sum) and a list of debit/credit values, the algorithm should be able to find some combination that make up the given (sum).

Algorithm

The standard algorithm to solve a subset-sum problem is a dynamic programming

Implementation

The web app uses Flask as an framework, which is extremely simple, lightweight and written in python.

The python implementation of subset sum algorithm is adopted from stackoverflow.

To speed up the dynamic programming algorithm, I used cython to optimized a the code, a benchmark test can be found here.

Deployment

The flask app is hosted by Heroku. The deployment is well documented on the website, codes can be push to heroku using heroku cli and git. I followed this guide.

Basically, after heroku cli is installed, do:

1. login, so you can access your data via cli

heroku login 

2. create the app, some flask-specific requirments
   • All javascripts and css files should go to a folder called static,
     • I put the whole bootstraip library into this folder
   • All html templates should go to a folder called templates

mkdir ~/subset_sum
cd ~/subset_sum
mkdir src src/templates src/static
# make some codes...
git init

3. Create a fresh new env, and install required packages

conda create -n subset_sum python=3.6 \
    cython flask    

4. Create requirement.txt so heroku knows what to install

pip freeze > requirements.txt

5. Commit all codes

git add .
git commit -m 'initialize web app'

6. Adding heroku git repo as an remote repo

heroku create subset-solver

7. Push the code to heroku

git push heroku master

8. And now you can see if the webapp is live (hint: it's not, because heroku won't know how to do/need to do flask run to run the webapp)

9. To tell heroku how to start the app

echo 'web: gunicorn app:app' > Procfile
git add Procfile
git commit -m "Added Procfile and runtime.txt files"
git push heroku master

10. Open the webapp and see if it is what it should look like

heroku open

11. This should work if cython is not being used, because heroku doesn't compile cython code by default.. The installation of gcc was done following a post on stackoverflow.
    • Now, we need to do:

    heroku update beta
    heroku plugins:install @heroku-cli/plugin-manifest
    heroku manifest:create
    

    • This will create a heroku.yml file, so now you can delete the Procfile
    • Modify the heroku.yaml into:

    setup:
    config: {}
    build:
    languages:
        - python
    packages:
        - build-essential
    run:
    web: 'gunicorn app.app:app'
    

    • And finally:

    heroku stack:set container
    git add heroku.yaml
    git commit -am 'added heroky.yml'
    git push heroku master
    

+++

Code availability

The code for building the website is deposited on github.