Knapsack Problem
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--color_border_app-header-divider: var(--primaryDark); /*line color after header*/
15
16--color_bg_app-canvas: url(/app-resources/resources/images/RightBackground.png) rgb(249, 249, 249) no-repeat left/contain; /*background color*/
17--color_bg_widget-header: #95551141; /*widget header background color*/
18--border_widget-header: 2px solid var(--primaryDark); /*line color after widget header*/
19
20--color_text_edit-select-link: var(--primaryDark);
21--color_bg_button_primary: var(--primaryDark);
22--color_bg_button_primary_hover: var(--primary);
23--color_text_edit-select-link: var(--primaryDark);
24
25
26/*---------------------------------------------------------------------
27 WORKFLOW
28----------------------------------------------------------------------*/
29/* Header text*/
30--color_workflow-header: #505767;
31
32/* Step background and content (text, icon) colors for the 4 states*/
33/*current + current with error*/
34--color_bg_workflow_current: var(--primaryDark);
35--color_workflow_current: var(--color_text_inverted);
36--color_bg_workflow_error-current: #d1454b;
37
38/*active*/
39--color_bg_workflow_active: #e6edff;
40--color_workflow_active: var(--primaryDark);
41
42/*inactive*/
43--color_bg_workflow_inactive: #dde0e8;
44--color_workflow_inactive: #b0b5c2;
45
46/*error*/
47--color_bg_workflow_error: #f9e9e9;
48--color_workflow_error: #d1454b;
49
50/* Child indentation, border colors */
51--spacing_workflow-child-indent: 1rem;
52--color_workflow-item-divider: var(--primaryDark);
53
54/* Icon background, border, for non-error state */
55--color_bg_workflow-icon: #ffffff;
56--color_workflow-icon-border: var(--primaryDark);
57
58}
1.annotation-different {
2 background: #ff921e2a;
3}
1/*Link color*/
2.ql-snow a {
3 color: var(--primaryDark) !important;
4}
5
6.tag-slider .slider-value {
7 color: var(--primaryDark);
8}
9
10.status-message.clickable:hover .status-display-text{
11 color: var(--primaryDark);
12}
Minimal Requirements
AIMMS Community license is sufficient for working with this example.