Multi-Objective Knapsack Problem with AMPLPY#

knapsack.ipynb Open In Colab Open In Deepnote Open In Kaggle Open In Gradient Open In SageMaker Studio Lab Powered by AMPL

Description: knapsack problem using multiple objectives, setting objective-specific options

Tags: multi-objective, multi-objective options, lexicographic objectives, knapsack, amplpy, highlights

Notebook author: Jurgen Lentz <jurgenlentz26@gmail.com>

This notebook demonstrates how to solve a multi-objective knapsack problem via amplpy. We will:

  • Set up a knapsack model with two objectives (e.g., maximize profit & minimize weight).

  • Specify different options for a specific objective, as described in https://mp.ampl.com/modeling-mo.html#options-for-each-objective.

By the end, you’ll understand how to use AMPL for multi-objective optimization and specify options for a specific objective.

# Install dependencies
%pip install -q amplpy

# Google Colab & Kaggle integration
from amplpy import AMPL, ampl_notebook

ampl = ampl_notebook(
    modules=["gurobi", "highs", "cbc"],  # modules to install
    license_uuid="default",  # license to use
)  # instantiate AMPL object and register magics

Instantiate the AMPL environment#

This cell initializes an AMPL session in amplpy, sets the solver to Gurobi but you can choose another solver (e.g., HiGHS, CBC), and activates the MP multi-objective emulation (you can set obj:multi to 1 if you want to use multi-objective functionalities of the solver).

from amplpy import AMPL

# Initialize AMPL
ampl = AMPL()

ampl.set_option("solver", "gurobi")  # or 'highs' or 'cbc'
ampl.set_option(
    "gurobi_options", "obj:multi=2 outlev=1"
)  # enable lexicographic MO support

Multi-Objective Knapsack with options for specific objective#

We create the binary knapsack model but use two different objective functions, TotalValue to maximize the total profits of the items packed in knapsack and NumItems to minimize the number of items packed in the knapsack. The suffix objpriority specifies the lexicographical order of the objective functions. You can specify options for each objective by creating a suffix in AMPL with the name starting with option_ followed by the option name as obtained by the solver. Here, we set the timelimit and mipgap of the objective TotalValue.

%%ampl_eval
suffix objpriority;
suffix option_timelimit;
suffix option_mipgap;

set ITEMS;
param weight{ITEMS};
param value{ITEMS};
param capacity;

var x{ITEMS} binary;

# Objective 1: maximize total value
maximize TotalValue:
    sum {i in ITEMS} value[i] * x[i]
    suffix objpriority 2,  # highest priority
    suffix option_timelimit 60,
    suffix option_mipgap 0.01;

# Objective 2: minimize number of items
minimize NumItems:
    sum {i in ITEMS} x[i]
    suffix objpriority 1;

subject to CapacityConstraint:
    sum {i in ITEMS} weight[i] * x[i] <= capacity;

We provide data for the set ITEMS and assign corresponding values to the parameters weight, value, and capacity.

items = ["item1", "item2", "item3", "item4", "item5"]
weights = [2, 3, 4, 5, 9]
values = [3, 4, 8, 8, 10]
capacity = 10

ampl.set["ITEMS"] = items
ampl.param["weight"] = dict(zip(items, weights))
ampl.param["value"] = dict(zip(items, values))
ampl.param["capacity"] = capacity

# Solve
ampl.solve()

Gurobi 12.0.2:   obj:multi = 2
Set parameter LogToConsole to value 1
  tech:outlev = 1

AMPL MP initial flat model has 5 variables (0 integer, 5 binary);
Objectives: 2 linear; 
Constraints:  1 linear;



==============================================================================
MULTI-OBJECTIVE MODE: starting with 2 objectives (2 combined) ...
==============================================================================
==============================================================================

AMPL MP final model has 5 variables (0 integer, 5 binary);
Objectives: 2 linear; 
Constraints:  1 linear;


Set parameter InfUnbdInfo to value 1


MULTI-OBJECTIVE MODE: objective 1 (out of 2) ...
==============================================================================

Set parameter TimeLimit to value 60
Setting timelimit to 60
Set parameter MIPGap to value 0.01
Setting mipgap to 0.01
Gurobi Optimizer version 12.0.2 build v12.0.2rc0 (linux64 - "Ubuntu 22.04.5 LTS")

CPU model: 13th Gen Intel(R) Core(TM) i7-1370P, instruction set [SSE2|AVX|AVX2]
Thread count: 20 physical cores, 20 logical processors, using up to 20 threads

Non-default parameters:
TimeLimit  60
MIPGap  0.01
InfUnbdInfo  1

Optimize a model with 1 rows, 5 columns and 5 nonzeros
Model fingerprint: 0xebe412b7
Variable types: 0 continuous, 5 integer (0 binary)
Coefficient statistics:
  Matrix range     [2e+00, 9e+00]
  Objective range  [3e+00, 1e+01]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+01, 1e+01]
Found heuristic solution: objective 15.0000000
Presolve removed 1 rows and 5 columns
Presolve time: 0.00s
Presolve: All rows and columns removed

Explored 0 nodes (0 simplex iterations) in 0.00 seconds (0.00 work units)
Thread count was 1 (of 20 available processors)

Solution count 2: 16 15 

Optimal solution found (tolerance 1.00e-02)
Best objective 1.600000000000e+01, best bound 1.600000000000e+01, gap 0.0000%


MULTI-OBJECTIVE MODE: objective 2 (out of 2) ...
==============================================================================

Set parameter TimeLimit to value 1e+100
Setting timelimit to 1e+100
Set parameter MIPGap to value 0.0001
Setting mipgap to 0.0001
Gurobi Optimizer version 12.0.2 build v12.0.2rc0 (linux64 - "Ubuntu 22.04.5 LTS")

CPU model: 13th Gen Intel(R) Core(TM) i7-1370P, instruction set [SSE2|AVX|AVX2]
Thread count: 20 physical cores, 20 logical processors, using up to 20 threads

Non-default parameters:
InfUnbdInfo  1

Optimize a model with 2 rows, 5 columns and 10 nonzeros
Model fingerprint: 0x22ffa37b
Variable types: 0 continuous, 5 integer (0 binary)
Coefficient statistics:
  Matrix range     [2e+00, 1e+01]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+01, 2e+01]

Loaded MIP start from previous solve with objective -2

Presolve removed 2 rows and 5 columns
Presolve time: 0.00s
Presolve: All rows and columns removed

Explored 0 nodes (0 simplex iterations) in 0.00 seconds (0.00 work units)
Thread count was 1 (of 20 available processors)

Solution count 1: -2 
No other solutions better than -2

Optimal solution found (tolerance 1.00e-04)
Best objective -2.000000000000e+00, best bound -2.000000000000e+00, gap 0.0000%


==============================================================================
MULTI-OBJECTIVE MODE: done.

Gurobi 12.0.2: optimal solution; objective 16
Individual objective values:
	_sobj[1] = 16
	_sobj[2] = 2
0 simplex iterations
Objective = TotalValue

# Retrieve and display results
tv = ampl.get_objective("TotalValue").value()
ni = sum(int(ampl.get_variable("x")[i].value()) for i in items)
sel = [i for i in items if int(ampl.get_variable("x")[i].value()) == 1]

print(f"🏅 TotalValue = {tv}")
print(f"🧩 NumItems = {ni}")
print("✅ Selected items:", sel)

🏅 TotalValue = 16.0
🧩 NumItems = 2
✅ Selected items: ['item3', 'item4']