Skip to content

Self-guided tutorial on combinatorial optimization, the bin packing problem, and constructive heuristics, suitable for use as course assignments, or by self-directed learners.

License

Notifications You must be signed in to change notification settings

cicirello/InteractiveBinPacking

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Interactive Bin Packing

Interactive Bin Packing

Copyright (C) 2008, 2010, 2020-2023 Vincent A. Cicirello.

Publications About the Application DOI
Packages and Releases Maven Central GitHub release (latest by date)
Build Status build CodeQL
JaCoCo Test Coverage coverage branches
Security Snyk security score Snyk Known Vulnerabilities
DOI DOI
Other Information License style

How to Cite

If you have reason to cite this application in an article, please cite the following:

Cicirello, V.A., (2022). Interactive Bin Packing: A Java Application for Learning Constructive Heuristics for Combinatorial Optimization. Journal of Open Source Education, 5(49), 140, https://doi.org/10.21105/jose.00140.

Overview

Interactive Bin Packing provides a self-guided tutorial on combinatorial optimization, the bin packing problem, and constructive heuristics for bin packing. It also enables the user to interact with bin packing instances to explore their own problem solving strategies, or to test their knowledge of the various constructive heuristics covered by the tutorial. The application is not a solver for bin packing. Interactive Bin Packing is a tool for learning about the bin packing problem, as well as for learning about heuristic techniques for solving instances of the problem.

The objectives of Interactive Bin Packing include:

  • gaining an understanding of the bin packing problem, and more generally how the bin packing problem is an example of a combinatorial optimization problem;
  • learning about constructive heuristics;
  • learning about the most common constructive heuristics for the bin packing problem, including first-fit, best-fit, first-fit decreasing, and best-fit decreasing; and
  • serving as an interactive environment for students (whether in the formal context of a class, or just for informal self-guided learning) to explore potential problem solving methods for combinatorial optimization.

In addition to the Interactive Bin Packing application source code, this repository also contains example assignments. Specifically, the assignments directory contains example assignments that can either be used by self-guided learners, or which can be adapted and used by instructors in courses, such as within courses on discrete mathematics, algorithms, or artificial intelligence.

First time users should start by taking a look at the sections below on User Documentation as well as Installing and Running the Application. We also recommend that first time users (whether students in courses or self-learners) work through the first of the example assignments.

Java 11+

The prebuilt jar of the application is built with the OpenJDK 11.

Example Assignments

In addition to the Interactive Bin Packing application, the repository contains a directory of Example Assignments that utilize the application. Self-directed learners may begin with assignments/1; while course instructors may prefer to assign their students assignments/2, which utilizes the Session Log functionality introduced in version 3.1.0 to make it easy for instructors to validate students' work.

User Documentation

All user documentation is contained within the application itself, which you can access via two commands in the Info menu:

  • The Tutorial command in the Info menu opens a self-guided tutorial on combinatorial optimization, the bin packing problem, and constructive heuristics for bin packing. It will also walk you through using the application, and all of its functionality.
  • The Help command (also in the Info menu) provides documentation of all menu functions and other user interface elements.
  • We recommend that instructors take a look at the documentation of the commands of the Session menu (see the Help command), which enables having students save session logs, and also provides functionality for validating the session logs they submit to you to confirm successful completion of assignments that utilize the application.

The first time that you use the application, we recommend that you begin by choosing the Tutorial command from the Info menu, and working your way through the self-guided tutorial.

Installing and Running the Application

Installing == Downloading

The Interactive Bin Packing application is available as a prebuilt, executable jar file from a variety of sources. The filename of the jar is of the form interactive-bin-packing-X.Y.Z.jar, where X.Y.Z is the version number.

To install, simply download the jar of the latest release by doing any of the following:

  • From the command line via Maven Central:
    curl -O -J -L  "https://repository.sonatype.org/service/local/artifact/maven/content?r=central-proxy&g=org.cicirello&a=interactive-bin-packing&e=jar&v=LATEST"
  • From Maven Central repository website: Select versions tab, and then the browse link, and download the jar.
  • From the GitHub Package Registry: Select the most recent release, and download the jar of the application.
  • From GitHub releases: Simply download the jar from the most recent release.
  • Building from the source: See the section on this below.

Running

The jar file that you downloaded above is an executable jar. To run, assuming that you have a Java runtime environment (JRE version 11 or higher) installed on your system, then do any of the following:

  • Simply double click the jar file.
  • From the command line (assuming your current directory is that of the jar file), you can run with: interactive-bin-packing-X.Y.Z.jar. Just replace the X.Y.Z with the version number that you downloaded.
  • Or from the command line, you can similarly run with: java -jar interactive-bin-packing-X.Y.Z.jar.

Building and Testing the Application (with Maven)

The Interactive Bin Packing Application is built using Maven, which you can download and install from the official Apache Maven website.

The root of the repository contains a Maven pom.xml. To build the library, execute mvn package at the root of the repository, which will compile all classes, run all tests, and generate jar files of the application, the sources, and the javadocs. The file names make this distinction explicit. All build artifacts will then be found in the directory target.

To include generation of a code coverage report during the build, execute mvn package -Pcoverage at the root of the repository to enable a Maven profile that executes JaCoCo during the test phase.

To run all static analysis tools (i.e., SpotBugs, Find Security Bugs, refactor-first), execute mvn package -Panalysis to enable a Maven profile that executes the various static analysis tools that we are using. The SpotBugs html report will be found in the target directory, or you can use the SpotBugs GUI with: mvn spotbugs:gui -Panalysis. The refactor-first report will be found in the target/site directory.

To run all of the above: mvn package -P "analysis,coverage".

The jar file of the application is executable, so you then simply double click it to run.

License

The Interactive Bin Packing Application is licensed under the GNU General Public License 3.0.

Contribute

Report bugs, suggestions, feature requests, etc via the issues tracker. If you would like to contribute to Interactive Bin Packing in any way, such as reporting bugs, suggesting new functionality, or code contributions such as bug fixes or implementations of new functionality, then start by reading the contribution guidelines. This project has adopted the Contributor Covenant Code of Conduct.

Support and Discussion

To obtain support from the maintainers or from other community members, or to discuss ideas for potential new functionality, we are using GitHub Discussions. For support, start a new discussion with the Q&A category. If you would like to discuss ideas for new functionality before submitting an issue, you can start a discussion with the Ideas category. You can use the General category for any other community discussions.