Knapsack Models

LOGOS contains a set of knapsack models that can be used in combination with RAVEN when the desired optimization problem requires specific models to generate the knapsack parameters. More specifically, all these models can be included in a RAVEN <EnsembleModel>, and RAVEN optimization methods (e.g., genetic algorithms) can then be employed to find the optimal solution.

Simple Knapsack Model

This model corresponds to the classical knapsack problem, characterized by a set of elements that can be chosen (or not). The goal is to maximize the sum of the chosen element values, subject to the constraint that the sum of their cost values does not exceed a capacity constraint (specified via a variable defined in the node).

The IDs of the variables representing cost, value, and choice of each element are indicated in the node. The model generates two variables:

• the validity of the chosen solution (specified in the node): either valid (0) or invalid (1) if the capacity constraint is not satisfied;

• totalValue (specified in the node): the sum of the values of the chosen elements.

When calculating the objective variable, if the constraint is not satisfied, then the variable is penalized by multiplying the project value by -1.

Example LOGOS input XML for SimpleKnapsackModel:

<ExternalModel name="knapsack" subType="LOGOS.SimpleKnapsackModel">
  <variables>element1Status,element2Status,element3Status,
             element4Status,element5Status,element1Val,
             element2Val,element3Val,element4Val,
             element5Val,element1Cost,element2Cost,
             element3Cost,element4Cost,element5Cost,
             validity,totalValue,capacityID</variables>
  <capacity>capacityID</capacity>
  <penaltyFactor>1.</penaltyFactor>
  <outcome>validity</outcome>
  <choiceValue>totalValue</choiceValue>
  <map value="element1Val" cost="element1Cost">element1Status</map>
  <map value="element2Val" cost="element2Cost">element2Status</map>
  <map value="element3Val" cost="element3Cost">element3Status</map>
  <map value="element4Val" cost="element4Cost">element4Status</map>
  <map value="element5Val" cost="element5Cost">element5Status</map>
</ExternalModel>

MultipleKnapsack Model

This model considers the multiple knapsack problem, characterized by a set of elements that can be chosen (or not) across multiple knapsacks. The goal is to maximize the sum of the chosen element values, subject to the capacity constraints of each knapsack.

The capacity of each knapsack is defined in the node.

As before, the IDs of the variables that represent cost, value, and choice of each element are indicated in the node. The model generates two variables:

• the validity of the chosen solution (specified in the node): either valid (0) or invalid (1) if any capacity constraint is not satisfied;

• totalValue (specified in the node): the sum of the values of the chosen elements.

When calculating the objective variable, if any capacity constraint is not satisfied, then the variable is penalized by multiplying the project value by -1.

Example LOGOS input XML for MultipleKnapsackModel:

<Models>
  <ExternalModel name="knapsack" subType="LOGOS.MultipleKnapsackModel">
    <variables>e1Status,e2Status,e3Status,e4Status,e5Status,
               e1Val   ,e2Val   ,e3Val   ,e4Val   ,e5Val,
               e1Cost  ,e2Cost  ,e3Cost  ,e4Cost  ,e5Cost,
               validity,totalValue,
               K1_cap,K2_cap,K3_cap</variables>
    <knapsack ID="1">K1_cap</knapsack>
    <knapsack ID="2">K2_cap</knapsack>
    <knapsack ID="3">K3_cap</knapsack>
    <penaltyFactor>1.</penaltyFactor>
    <outcome>validity</outcome>
    <choiceValue>totalValue</choiceValue>
    <map value="e1Val" cost="e1Cost">e1Status</map>
    <map value="e2Val" cost="e2Cost">e2Status</map>
    <map value="e3Val" cost="e3Cost">e3Status</map>
    <map value="e4Val" cost="e4Cost">e4Status</map>
    <map value="e5Val" cost="e5Cost">e5Status</map>
  </ExternalModel>
</Models>