Knapsack Problem

https://img.shields.io/badge/AIMMS_4.93-ZIP:_Knapsack-blue https://img.shields.io/badge/AIMMS_4.93-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}\)

maximum knapsack weight

\(mI \in \mathbb{I}\)

maximum knapsack item

Variables:

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

quantity of items placed

Constraints:

1

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

respect knapsack weight capacity

2

\(\sum_{i} X_{i} \leq mI\)

respect knapsack item 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));

See also

In this article you will find more details about how to randomize your data.

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/*---------------------------------------------------------------------
 3      COLORS
 4----------------------------------------------------------------------*/
 5   --primary: #FF941E;
 6   --primaryDark: #955511;
 7   --primaryLight: #fff4e9;
 8
 9/*---------------------------------------------------------------------
10      LOGO
11----------------------------------------------------------------------*/
12   --bg_app-logo: 15px 50% / 30px 30px no-repeat url(/app-resources/resources/images/knapsack-logo.png);
13   --spacing_app-logo_width: 45px;
14
15   --color_bg_button_primary: var(--primaryDark);
16   --color_bg_button_primary_hover: var(--primary);
17   --color_text_edit-select-link: var(--primaryDark);
18
19
20/*---------------------------------------------------------------------
21      WORKFLOW
22----------------------------------------------------------------------*/
23   /* Header text*/
24   --color_workflow-header: #505767;
25
26   /* Step background and content (text, icon) colors for the 4 states*/
27   /*current + current with error*/
28   --color_bg_workflow_current: var(--primaryDark);
29   --color_workflow_current: var(--color_text_inverted);
30   --color_bg_workflow_error-current: #d1454b;
31
32   /*active*/
33   --color_bg_workflow_active: #e6edff;
34   --color_workflow_active: var(--primaryDark);
35
36   /*inactive*/
37   --color_bg_workflow_inactive: #dde0e8;
38   --color_workflow_inactive: #b0b5c2;
39
40   /*error*/
41   --color_bg_workflow_error: #f9e9e9;
42   --color_workflow_error: #d1454b;
43
44   /*Child indentation, border colors*/
45   --spacing_workflow-child-indent: 1rem;
46   --color_workflow-item-divider: var(--primaryDark);
47
48   /*Icon background, border, for non-error state*/
49   --color_bg_workflow-icon: #ffffff;
50   --color_workflow-icon-border: var(--primaryDark);
51}
1.annotation-different {
2   background: #ff921e2a;
3}
 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/*Link color*/
13.ql-snow a {
14   color: var(--primaryDark) !important;
15}
16
17/*Change table default text color*/
18.tag-table .grid-viewport .cell.flag-default,
19html:not(.using-touch) .tag-table .grid-viewport .cell.flag-default {
20   color: white;
21}
22
23.tag-slider .slider-value {
24   color: var(--primaryDark);
25}
26
27.status-message.clickable:hover .status-display-text{
28   color: var(--primaryDark);
29}
 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}
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.