QuadKnap

Knapsack solver: David Pisinger, Alberto Caprara, Paolo Toth

by RichardAD

HTML

<script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script>
<script src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>
<pre>
/* ======================================================================
   QUADRATIC KNAPSACK PROBLEM  Alberto Caprara, David Pisinger, Polo Toth
   ====================================================================== */  
</pre>
<p>
<A href="http://hjemmesider.diku.dk/~pisinger/quadknap.c">Original C source code</A>
</p>

<p>

maximize \( \sum_{i=1}^{n} \sum_{j=1}^{n} p_{i,j} x_{i} x_{j} \) <br />
subject to \( \sum_{j=1}^{n} w_{j} x_{j} \leq c
            x_{j} \in \{0,1\}, j = 1,\ldots,n \)

</p>

<pre>
typedef int     boolean;
typedef int     ntype;   /* number of items          */
typedef int     itype;   /* item profits and weights */
typedef int     stype;   /* sum of profit or weight  */
typedef double  ptype;   /* product type             */
typedef float   etype;   /* efficiency type          */

class lpitem {
  constructor (e, p, w, x) {
    this.e = e;
    this.p = p;
    this.w = w;
    this.x = x;  // might become this.x = { value: x };
  }</pre>

JavaScript

// Original source: http://hjemmesider.diku.dk/~pisinger/quadknap.c
// Adapted to JavaScript: Richard DeVenezia Jan 2020.

/* ======================================================================
   QUADRATIC KNAPSACK PROBLEM  Alberto Caprara, David Pisinger, Polo Toth
   ====================================================================== */

/* This code solves the quadratic knapsack problem, which
 * asks to maximize a quadratic objective function subject
 * to a single weight constraint. 
 *
 *   maximize   \sum_{i=1}^{n} \sum_{j=1}^{n} p_{i,j} x_{i} x_{j}
 *   subject to \sum_{j=1}^{n} w_{j} x_{j} \leq c
 *              x_{j} \in \{0,1\}, j = 1,\ldots,n
 *
 * It is assumed that all coefficients are nonnegative integers.
 * A description of the code is found in the following paper:
 *
 *   A. Caprara, D. Pisinger, P. Toth, 
 *   "Exact solution of the Quadratic Knapsack Problem", 
 *   INFORMS Journal on Computing, 11, 125-137 (1999). 
 *
 * The present code is written in ANSI-C, and has been compiled with
 * the GNU-C compiler using option "-ansi -pedantic" as well as the
 * HP-UX C compiler using option "-Aa" (ansi standard).
 *
 * This file contains the callable routine quadknap with prototype
 *
 *   int quadknap(int no, int cap, int *ptab, int *wtab, int *xtab);
 * 
 * the meaning of the parameters is the following:
 *   no        Size of problem, i.e. number of items.
 *   ptab      A pointer to an integer matrix of profits p[i][j].
               It is very important to declare the matrix as
                 int ptab[MSIZE][MSIZE];
               in order to be interpreted correctly. The constant
               MSIZE is defined below.
 *   wtab      A table of weights w[i] of length at least no.
 *   xtab      A table of solutions variables x[i] of length at least no.
 * the procedure returns the optimal objective value.
 *
 * (c) Copyright, August 2000,
 *   David Pisinger                     Alberto Caprara, Paolo Toth
 *   DIKU, University of...