Knapsack Problem

https://img.shields.io/badge/AIMMS_4.87-ZIP:_Knapsack-blue https://img.shields.io/badge/AIMMS_4.87-Github:_Knapsack-blue https://img.shields.io/badge/AIMMS_Community-Forum-yellow

Story

This example introduces a knapsack problem. The example considers a data set of 16 items which can be included in the knapsack. The objective is to maximize the accumulated value of the items. The number of items is restricted by the maximum weight that can be carried in the knapsack.

Mathematical Model

In the classical knapsack problem, each item can be chosen only once. This example also considers variants of the problem in which the number of equal items is unlimited or limited to certain integers.

Knapsack Problem

Sets and indices:

\(I\), \(i \in I\)

items

Parameters:

\(rI_{i}, i \in \mathbb{I}\)

minimum quantity

\(rA_{i}, i \in \mathbb{I}\)

maximum quantity

\(V_{i} \in \mathbb{R}\)

item price

\(W_{i} \in \mathbb{R}\)

item weight

\(mW \in \mathbb{R}\)

knapsack weight

Variables:

\(X_{i} \in \{rI_{i}..rA_{i}\}\)

quantity of items placed

Constraints:

1

\(\sum_{i} X_{i} * W_{i} \leq mW\)

respect knapsack capacity

Maximize:

\(\sum_{i} (X_{i} * V_{i})\)

total accumulated value

Language

In this section a few highlights of the use of the AIMMS Language in the application are pointed out.

Let us start with modifying the type of solve, simply by modifying the bounds of the variables; in other words, three types of model can be solved by only one algebraic specification of the model.

Types of Solve

Procedure pr_solveKnapsackModel

This will solve the classic knapsack problem. Minimal range will be set as 0 and maximum will be set as 1 automatically.

1p_itemRangeMin(i_item) := 0;
2p_itemRangeMax(i_item) := 1;
Procedure pr_solveKnapsackModelUnBounded

This will solve the knapsack problem as unbounded. Minimal range will be set as 0 and maximum will be set as inf automatically.

1p_itemRangeMin(i_item) := 0;
2p_itemRangeMax(i_item) := inf;
Procedure pr_solveKnapsackModelBounded

This will solve the knapsack problem with a integer bound. Minimal range will be set as 0 and maximum will be set by the bound value.

1p_itemRangeMin(i_item) := 0;
2p_itemRangeMax(i_item) := p_itemBound(i_item);

Random Data

Procedure pr_randomizeData

In order to make the example more playful in therms of feature functionality, you can randomize data at any time. The procedure below is available on Page Actions.

1empty p_itemValue, p_itemWeight, p_itemBound;
2
3p_itemValue(i_item) := uniform(0,200)*1[$];
4p_itemWeight(i_item) := uniform(0[lb],p_maxWeightKnapsack/3);
5p_itemBound(i_item) := ceil(uniform(0,10));

Integration

On this example, AXLL library is used. You can check both import and export procedures by looking for these: pr_readAll and pr_writeAll.

WebUI Features

On inputs page, there is a ‘hidden’ feature. If you click with the right button on the table, a small menu will appear with CRUD options for that set.

The following WebUI features are used:

UI Styling

For this project, we used a main css file named colors.css, please check it out directly on the folder. Below there are the css files you will find with comments on what they change.

1:root {
2   --bg_app-logo: 15px 50% / 30px 30px no-repeat url(/app-resources/resources/images/knapsack-logo.png);
3   --spacing_app-logo_width: 45px;
4}
 1/*Change color of the active step*/
 2.workflow-panel .step-item.current,
 3.workflow-panel.collapse .step-item.current {
 4   box-shadow: inset 0.3125rem 0 0 var(--primary);
 5}
 6
 7/*Change color of the titles*/
 8.workflow-panel .step-item.active.complete .title,
 9.workflow-panel .step-item.active.incomplete .title {
10   color: var(--primaryDark);
11}
12
13/*Change color of the icons*/
14.workflow-panel .step-item.active.complete .icon,
15.workflow-panel .step-item.active.incomplete .icon {
16   color: var(--primaryDark);
17   border: 1px solid var(--primaryDark);
18}
 1/*Change table text color*/
 2.tag-table .grid-viewport .cell:not(.flag-readOnly),
 3html:not(.using-touch) .tag-table .grid-viewport .cell:not(.flag-readOnly) {
 4   color: var(--primaryDark);
 5}
 6
 7/*Change scalar text color*/
 8.tag-scalar .kpi .value {
 9   color: var(--primaryDark);
10}
11
12.tag-slider .slider-value {
13   color: var(--primaryDark);
14}
 1.page-action-v2 .page-action-menu,
 2.page-action-v2 .page-action-menu.open {
 3   background: var(--primaryDark);
 4}
 5
 6.page-action-v2 .page-action-menu:hover,
 7.page-action-v2 .page-action-menu:hover {
 8   background: var(--primary);
 9}
10
11.page-action-v2 .page-action-holder .page-action-item .page-action-icon,
12.page-action-v2 .page-action-holder .page-action-item .page-action-letter {
13   background-color: var(--primaryDark);
14}
15
16.page-action-v2 .page-action-holder .page-action-item .page-action-icon:hover,
17.page-action-v2 .page-action-holder .page-action-item .page-action-letter:hover {
18   background-color: var(--primary);
19}
 1/*Change color after tab click*/
 2.sidepanel-container .sidepanel-tab.active {
 3   background-color: var(--primaryDark);
 4}
 5
 6/*Change letter color on hover*/
 7.sidepanel-container .sidepanel-tab.active:hover {
 8   color: white;
 9}
10
11/*Change icon color*/
12.sidepanel-container .sidepanel-tab .sidepanel-icon,
13.sidepanel-container .sidepanel-tab:hover {
14   color: var(--primaryDark);
15}
16
17/*Change color after all tabs*/
18.sidepanel-container .sidepanel-tabs-container:after {
19   background: var(--primaryDark);
20}
21
22/*Change the color below sidepanel tabs*/
23.sidepanel-container {
24   background-color:   rgb(249, 249, 249);
25}
26
27.sidepanel-active .sidepanel-container {
28   background-color:   rgba(249, 249, 249, 0);
29}
 1.tag-table.focused .cell.focus-cell {
 2   box-shadow: inset 0 0 0 2px var(--primaryDark);
 3}
 4
 5.tag-table .cell.flag-number input{
 6   text-align: center;
 7}
 8
 9/*Change checkbox color*/
10input.boolean-cell-editor-contents {
11   accent-color: var(--primaryDark);
12}
1/*Change color of togglelegend of the combination chart*/
2.togglelegend-button svg{
3   fill: var(--primaryDark);
4}
5
6.togglelegend-button-active:hover svg g, .togglelegend-button-active svg g {
7   fill: var(--primary);
8}
1.theme-aimms header.tag-application {
2   border-bottom: 2px solid var(--primaryDark);
3}
1.tag-multiselect-widget .searchable-list li.active .checkbox:before{
2   border: 1px solid var(--primary);
3   background: var(--primary);
4}
5.awf-select-actions>div {
6   color: var(--primary);
7}
 1/*Add logo on the background*/
 2.scroll-wrapper--pagev2 .page-container {
 3   content: " ";
 4   background: url(img/RightBackground.png) rgb(249, 249, 249) no-repeat left/contain;
 5}
 6
 7.widgetdiv .awf-dock.top {
 8   border-bottom: 2px solid var(--primaryDark);
 9   background: var(--primaryLight);
10}

Minimal Requirements

AIMMS Community license is sufficient for working with this example.