Branch-and-Bound-for-Multiple-Knapsack-Problem

KO | EN

gitlite — search

#python #hacktoberfest #ai #go #golang #machine-learning #macos #nodejs #windows #cli #vue #pytorch #security #ios

Branch-and-Bound-for-Multiple-Knapsack-Problem

(★ 20)

A Python implementation of a branch-and-bound approach (plus a simple greedy heuristic) to solve a variation of the multiple knapsack problem where items have both individual and pairwise benefits.

Branch-and-Bound-for-Multiple-Knapsack-Problem 최신버젼 다운로드

최종 버전 다운로드 (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# 🎒 Branch and Bound for Quadratic Multiple Knapsack Problem (QMKP) with Pairwise Benefits

This repository contains a Python implementation of a **branch-and-bound** approach (plus a simple greedy heuristic) to solve a variation of the Quadratic Multiple Knapsack Problem (QMKP) where items have both individual and pairwise benefits.

## 🚀Features

- **🧳Multiple knapsacks** – each with a fixed capacity.
- **🤝Pairwise benefits** – placing items (i,j) together yields an extra benefit.
- **🌲Branch-and-bound** – systematically builds a search tree, with a simple bounding approach.
- **⚙️Greedy heuristic** – as a fallback or initial solution (sort items by benefit/weight).
- **⏱️Time limit** – automatically stops branching after the user-defined time in each instance.

## 📄File Formats

Each instance file must have:

1. **First line**: `I B C T`  
   - `I`: number of items  
   - `B`: number of backpacks  
   - `C`: capacity per backpack  
   - `T`: max time (seconds) for the search  
2. **Second line**: list of `I` item weights.  
3. **Third line**: list of `I` item benefits.  
4. **Subsequent lines**: the pairwise-benefits matrix, typically forming a triangular or row-based structure.

---

## 🛠️Usage

1. **Clone or Download** the repository:
```bash
git clone https://github.com/RenatoMaynard/quadratic-multi-knapsack-b&b.py.git
```

---

## 🤝Contributing
Feel free to open issues or create pull requests:
  1. Fork the repository.
  2. Create a new branch.
  3. Commit changes.
  4. Push to the branch.
  5. Create a Pull Request.

---

## ⚠️Disclaimer
This project is for educational purposes only. Errors may exist. Please report issues or contribute improvements via pull requests.

---

## License
This project is open-sourced under the MIT license.

Branch-and-Bound-for-Multiple-Knapsack-Problem

Branch-and-Bound-for-Multiple-Knapsack-Problem 최신버젼 다운로드

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

Branch-and-Bound-for-Multiple-Knapsack-Problem

Branch-and-Bound-for-Multiple-Knapsack-Problem 최신버젼 다운로드

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

Download README