This repository contains the minimal solver implementation for reproducing the results from the paper on prioritized 2D orthogonal packing optimization. The code implements Mixed Integer Linear Programming (MILP) formulations for solving prioritized 2D orthogonal packing problems with prioritized items and offloading considerations.

Overview

The solver addresses prioritized 2D orthogonal packing problems where items with different priorities need to be packed into a bin such that the weighted Manhattan distances between items and to an offloading point are minimized. Two main solution approaches are implemented:

1. Single-shot approach: Solve the entire problem in one MILP optimization
2. Windowed approach: Solve iteratively using a sliding window of highest-priority items

Requirements

Julia Environment

• Julia 1.11.0 or later
• Required Julia packages:
  • JuMP.jl (optimization modeling)
  • Gurobi.jl (commercial solver interface)
  • JSON.jl (instance file parsing)
  • DataFrames.jl (data handling)
  • Dates.jl (timestamp generation)
  • SHA.jl (file path hashing)

Commercial Solver License

• Gurobi Optimizer with a valid license required for solver functionality

Installation

1. Install Julia (if not already installed):
   Download from https://julialang.org/downloads/

2. Start Julia and install required packages:

   julia
   using Pkg
   Pkg.add(["JuMP", "Gurobi", "JSON", "DataFrames", "Dates", "SHA"])
   

3. Configure Gurobi license:
   Follow the Gurobi installation guide to set up your license file.

Data Format

Input instances are provided as JSON files containing 2D packing problems with prioritized items organized into groups. The structure supports heterogeneous item sizes, group-based priorities, and various problem configurations. These instances are found in the data folder in the unzip_me.zip compressed file.

Basic JSON Structure

{
  "num_groups": 2,
  "num_items": 10,
  "heterogeneity_pattern": "hw",
  "group_size_pattern": "ml",
  "bin_dimensions": {"length": 2994, "width": 344},
  "groups": [
    {
      "id": 1,
      "priority": 1,
      "heterogeneity": "homogeneous",
      "size_category": "medium",
      "item_ids": [1, 2, 3, 4, 5]
    },
    {
      "id": 2,
      "priority": 2,
      "heterogeneity": "weak",
      "size_category": "large",
      "item_ids": [6, 7, 8, 9, 10]
    }
  ],
  "items": [
    {"id": 1, "length": 298, "width": 172, "priority": 1, "group_id": 1},
    {"id": 2, "length": 298, "width": 172, "priority": 2, "group_id": 1},
    ...
  ]
}

Detailed Data Dictionary

Groups

Each group represents a collection of items with shared characteristics:

• id: Unique group identifier
• priority: Group priority (lower values = higher priority)
• heterogeneity: Item size diversity within the group:
  • "homogeneous" (h): All items of identical size
  • "weak" (w): Two distinct item sizes
  • "strong" (s): No more than two items share the same size
• size_category: Group size classification:
  • "small" (s): 1-4 items
  • "medium" (m): 5-8 items
  • "large" (l): 9-12 items
• item_ids: Array of item IDs belonging to this group

Items

Individual items to be packed:

• id: Unique item identifier across the instance
• length: Item length dimension
• width: Item width dimension
• priority: Within-group priority (lower values = higher priority)
• group_id: ID of the group this item belongs to

Bin Dimensions

• length: Bin length
• width: Bin width

Global Metadata

• num_groups: Total number of groups (matches groups array length)
• num_items: Total number of items (matches items array length)
• heterogeneity_pattern: String where each character represents group heterogeneity (h/w/s)
• group_size_pattern: String where each character represents group size category (s/m/l)

Instance Naming Convention

Instance files follow the pattern: {groups}g_{items}it_{sizes}_{priorities}_{number}.json

• {groups}g: Number of priority groups (1g, 2g, 3g, 4g, 5g)
• {items}it: Number of items to pack
• {sizes}: Item size distribution pattern (combination of s/m/l)
• {priorities}: Priority distribution pattern (combination of s/h/w)
• {number}: Instance identifier (001-999)

Examples:

• 1g_10it_l_w_061.json: 1 group, 10 items, large group size, weak heterogeneity in item size
• 2g_14it_ml_sw_043.json: 2 groups, 14 items, medium+large group sizes, strong+weak heterogeneity in item size
• 5g_18it_sml_hsw_089.json: 5 groups, 18 items, small+medium+large group sizes, mixed heterogeneity in item size

Priority Interpretation

The optimization objective minimizes prioritization-weighted distances where:

• Lower priority values = Higher importance
• Group priorities determine inter-group relationships
• Item priorities determine intra-group relationships
• Higher priority items should be placed closer to the offloading point
• Items in the same high-priority group should be placed near each other (synergy)

Usage

Basic Usage from Terminal

1. Navigate to the repository directory:

   cd paper1_dryad
   

2. Start Julia:

   julia
   

3. Load the solver code:

   # Load required packages
   using JuMP, Gurobi, JSON, DataFrames, Dates, SHA
   
   # Include the solver functions
   include("prioritized_packing.jl")
   

4. Run single-shot approach on an instance:

   # Example: solve instance with single approach using 1 thread
   run_single_solve_on_instance("data/instances/1g_10it_l_w_061.json", 1)
   

5. Run windowed approach on an instance:

   # Example: solve instance with windowed approach using 8 threads, window size 7, time limit 5s
   run_windowed_solve_on_instance("data/instances/2g_10it_mm_hs_081.json", 8; 
                                  window_sizes=7:7, time_limits=(5,))
   

Example Complete Session

julia> using JuMP, Gurobi, JSON, DataFrames, Dates, SHA

julia> include("prioritized_packing.jl")

julia> # Run single approach on a 1-group instance
julia> run_single_solve_on_instance("data/instances/1g_10it_l_w_061.json", 8)

julia> # Run windowed approach on a 2-group instance with parameters
julia> run_windowed_solve_on_instance("data/instances/2g_10it_mm_hs_081.json", 8; 
                                      window_sizes=7:7, time_limits=(5,))

Advanced Usage

You can also call the core solver functions directly:

# Load instance data
L_Items, item_p, item_q, bin_L, bin_W, P, p_ig = 
    load_instance_from_json("data/instances/1g_6it_m_w_037.json")

# Solve with a single-shot approach
obj, runtime, nodes, gap, model, convergence, bound = solve_single_bin(
    L_Items, 1, item_p, item_q, bin_L, bin_W, 
    1, 0.0, bin_W[1]/2, P, zeros(Int, L_Items, 8);
    nThreads=1, nTimeLimit=300
)

println("Objective value: $obj")
println("Solution time: $runtime seconds")

Output Files

Results are saved in the results/ directory, organized by instance name:

Solution Files (.sol)

• Contains Gurobi's native solution format
• Can be loaded back into Gurobi for analysis
• Example: 1g_10it_l_w_061_single_CL_600sec.sol

Result Summaries (.json)

• Human-readable solution summary with:
  • Objective value and solve statistics
  • Item coordinates (x, xr, y, yr values)
  • Solver parameters and timestamps
• Example: 1g_10it_l_w_061_single_CL_600sec.json

Directory Structure After Running

results/
 1g_10it_l_w_061/
    1g_10it_l_w_061_single_CL_600sec.sol
    1g_10it_l_w_061_single_CL_600sec.json
    ...
 2g_10it_mm_hs_081/
    2g_10it_mm_hs_081_windowed_CL_5w_5sec.sol
    2g_10it_mm_hs_081_windowed_CL_5w_5sec.json
    ...
 ...

Citation

If you use this code or these instances in your research, please consider citing this repository and the associated paper on prioritized 2D orthogonal packing.

License

This code is provided as supplemental material for academic research purposes via the CC0 license. All data is CC0 and in the public domain.