Knapsack problem (guided)

Collaboration Knapsack_problem

Given a set of items, each having a specifed weight and value, and a knapsack with limited capacity, the Knapsack problem can be described as the problem of finding a selection of items to be included in the knapsack such that

• the total weight of the selected items does not exceed the capacity of the knapsack, and
• the total value of the selected items is maximised.

The model contains guidance on the sequence in which items are considered for inclusion.

Diagram

Process ItemProcess

The Item process starts with sending a request messsage including the item identifier, its weight and its value. Depending on whether the knapsack reject or accepts the item for inclusion, the respective end event is reached.

<bpmn2:extensionElements>
    <bpmnos:status>
        <bpmnos:attributes>
            <bpmnos:attribute id="Timestamp" name="timestamp" type="decimal">
            </bpmnos:attribute>
            <bpmnos:attribute id="Value" name="value" type="decimal">
            </bpmnos:attribute>
            <bpmnos:attribute id="Weight" name="weight" type="decimal">
            </bpmnos:attribute>
        </bpmnos:attributes>
    </bpmnos:status>
</bpmn2:extensionElements>

DataObject DataObject_1xt50y3

<bpmn2:extensionElements>
    <bpmnos:attributes>
        <bpmnos:attribute id="Instance" name="instance" type="string">
        </bpmnos:attribute>
    </bpmnos:attributes>
</bpmn2:extensionElements>

Task SendRequestTask

<bpmn2:extensionElements>
    <bpmnos:messages>
        <bpmnos:message name="Request">
            <bpmnos:content attribute="instance" key="Item">
            </bpmnos:content>
            <bpmnos:content attribute="value" key="Value">
            </bpmnos:content>
            <bpmnos:content attribute="weight" key="Weight">
            </bpmnos:content>
        </bpmnos:message>
    </bpmnos:messages>
</bpmn2:extensionElements>

Event CatchAcceptanceMessage

<bpmn2:extensionElements>
    <bpmnos:message name="Acceptance">
    </bpmnos:message>
</bpmn2:extensionElements>

Event CatchRejectionMessage

<bpmn2:extensionElements>
    <bpmnos:message name="Rejection">
    </bpmnos:message>
</bpmn2:extensionElements>

Process KnapsackProcess

The Knapsack process awaits requests for inclusion and spawns an event-subprocess for each item requesting inclusion.

It has a data object containing the capacityas well as the total_weight and total_value of all items included.

Moreover, it has an input attribute items representing the total number of items to be considered, and an attribute handled indicating the number of items handled.

<bpmn2:extensionElements>
    <bpmnos:status>
        <bpmnos:attributes>
            <bpmnos:attribute id="Timestamp" name="timestamp" type="decimal">
            </bpmnos:attribute>
        </bpmnos:attributes>
    </bpmnos:status>
</bpmn2:extensionElements>

DataObject DataObject_0vq7lh8

<bpmn2:extensionElements>
    <bpmnos:attributes>
        <bpmnos:attribute id="Capacity" name="capacity" type="decimal">
        </bpmnos:attribute>
        <bpmnos:attribute id="TotalWeight" name="total_weight := 0" type="decimal">
        </bpmnos:attribute>
        <bpmnos:attribute id="TotalValue" name="total_value := 0" objective="maximize" type="decimal" weight="1">
        </bpmnos:attribute>
        <bpmnos:attribute id="Items" name="items" type="integer">
        </bpmnos:attribute>
        <bpmnos:attribute id="HandledItems" name="handled := 0" type="integer">
        </bpmnos:attribute>
    </bpmnos:attributes>
</bpmn2:extensionElements>

DataObject DataObject_2xt50y3

<bpmn2:extensionElements>
    <bpmnos:attributes>
        <bpmnos:attribute id="Instance" name="instance" type="string">
        </bpmnos:attribute>
    </bpmnos:attributes>
</bpmn2:extensionElements>

Task WaitActivity

The activity must not be exited before all requests have been received.

<bpmn2:extensionElements>
    <bpmnos:guidance type="exit">
        <bpmnos:restrictions>
            <bpmnos:restriction expression="handled == items" id="ExitRestriction" scope="exit">
            </bpmnos:restriction>
        </bpmnos:restrictions>
    </bpmnos:guidance>
</bpmn2:extensionElements>

Event-SubProcess EventSubProcess

<bpmn2:extensionElements>
    <bpmnos:status>
        <bpmnos:attributes>
            <bpmnos:attribute id="Item" name="item" type="string">
            </bpmnos:attribute>
            <bpmnos:attribute id="Weight" name="weight" type="decimal">
            </bpmnos:attribute>
            <bpmnos:attribute id="Value" name="value" type="decimal">
            </bpmnos:attribute>
        </bpmnos:attributes>
        <bpmnos:operators>
            <bpmnos:operator expression="handled += 1" id="Operator_25omagu">
            </bpmnos:operator>
        </bpmnos:operators>
    </bpmnos:status>
</bpmn2:extensionElements>

Ad-hoc SubProcess AdHocSubProcess

The adhoc-subprocess ensures that the Handle item activities of all event-subprocesses are executed sequentially.

It increments the counter of the items handled by the knapsack.

<bpmn2:extensionElements>
    <bpmnos:status>
    </bpmnos:status>
</bpmn2:extensionElements>

SubProcess HandleItemActivity

This activity checks whether the item can be included in the knapsack without exceeding its capacity and rejects or accepts the item accordingly.

Moreover, it has a guiding operator determining the value to weight ratio.

The activity must not be entered before all requests have been received, to ensure that the best item can be handled first.

<bpmn2:extensionElements>
    <bpmnos:guidance type="entry">
        <bpmnos:attributes>
            <bpmnos:attribute id="Ratio" name="ratio := weight / value" objective="minimize" type="decimal" weight="1">
            </bpmnos:attribute>
        </bpmnos:attributes>
        <bpmnos:restrictions>
            <bpmnos:restriction expression="handled == items" id="EntryRestriction" scope="entry">
            </bpmnos:restriction>
        </bpmnos:restrictions>
    </bpmnos:guidance>
</bpmn2:extensionElements>

SequenceFlow Flow_0y2js91

<bpmn2:extensionElements>
    <bpmnos:restrictions>
        <bpmnos:restriction expression="total_weight + weight > capacity" id="Restriction_222eo7i">
        </bpmnos:restriction>
    </bpmnos:restrictions>
</bpmn2:extensionElements>

SequenceFlow Flow_1r0tr4t

<bpmn2:extensionElements>
    <bpmnos:restrictions>
        <bpmnos:restriction expression="total_weight + weight  <= capacity" id="Restriction_1g0l6u8">
        </bpmnos:restriction>
    </bpmnos:restrictions>
</bpmn2:extensionElements>

Event ThrowRejectionMessage

<bpmn2:extensionElements>
    <bpmnos:message name="Rejection">
        <bpmnos:parameter name="recipient" value="item">
        </bpmnos:parameter>
    </bpmnos:message>
</bpmn2:extensionElements>

Task IncludeItemActivity

<bpmn2:extensionElements>
    <bpmnos:status>
        <bpmnos:operators>
            <bpmnos:operator expression="total_value += value" id="Operator_30a3lhs">
            </bpmnos:operator>
            <bpmnos:operator expression="total_weight += weight" id="Operator_33i1d3i">
            </bpmnos:operator>
        </bpmnos:operators>
    </bpmnos:status>
</bpmn2:extensionElements>

Event ThrowAcceptanceMessage

<bpmn2:extensionElements>
    <bpmnos:message name="Acceptance">
        <bpmnos:parameter name="recipient" value="item">
        </bpmnos:parameter>
    </bpmnos:message>
</bpmn2:extensionElements>

Event CatchRequestMessage

<bpmn2:extensionElements>
    <bpmnos:message name="Request">
        <bpmnos:content attribute="item" key="Item">
        </bpmnos:content>
        <bpmnos:content attribute="weight" key="Weight">
        </bpmnos:content>
        <bpmnos:content attribute="value" key="Value">
        </bpmnos:content>
    </bpmnos:message>
</bpmn2:extensionElements>