Help
Table of Contents
The remainder of this tutorial is organized as follows:
Just below the menu bar of the application, is a panel that displays a
list of all of the items that must be packed into bins in the current
problem instance. Each item has a simple single character name, and the number
in parentheses is the size of that item. For example, if an item is listed
as "A(10)" it means that item A is of size 10. Below the list of items
is a list of the bins where you can place the items. These are all initially empty.
As you place items in bins, the list will update the amount of space already
used for each bin.
The panel at the bottom of the application has the controls for
interacting with the current bin packing instance. The Move button
moves the selected item into the selected bin, provided that there
is enough space at the destination, and that the move is consistent
with the chosen Mode. If you are in one of the
heuristic modes, and attempt to perform an action that is inconsistent
with the chosen heuristic, then you will get a message with an explanation.
See the Tutorial, accessible from the
Info Menu, for details on
the various constructive heuristics.
The Reset button removes all items from bins, and returns them to
their original order. It otherwise does not
affect either your chosen mode or the problem instance.
Return to Top or Table of Contents.
The Mode menu enables switching among the five modes of the
application, which are as follows:
- Practice: This is the default mode, which allows open-ended
interaction with the instance of the Bin Packing problem. The
user is free to move items around among bins in any order they wish,
provided that the destination bin has sufficient remaining space
for the item.
- First-Fit: In this mode, the user must use the first-fit heuristic
to choose each item and each destination bin. See the Tutorial feature
within the Info Menu for an explanation of this heuristic. The application
will give the user feedback on their choices, and will disallow any action
that violates the chosen heuristic. This mode disables the sorting commands in
the Operations Menu.
- First-Fit Decreasing: In this mode, the user must use the first-fit decreasing
heuristic to choose each item and each destination bin. See the Tutorial feature
within the Info Menu for an explanation of this heuristic. The application
will give the user feedback on their choices, and will disallow any action
that violates the chosen heuristic.
- Best-Fit: In this mode, the user must use the best-fit heuristic
to choose each item and each destination bin. See the Tutorial feature
within the Info Menu for an explanation of this heuristic. The application
will give the user feedback on their choices, and will disallow any action
that violates the chosen heuristic. This mode disables the sorting commands in
the Operations Menu.
- Best-Fit Decreasing: In this mode, the user must use the best-fit decreasing
heuristic to choose each item and each destination bin. See the Tutorial feature
within the Info Menu for an explanation of this heuristic. The application
will give the user feedback on their choices, and will disallow any action
that violates the chosen heuristic.
Switching into any mode other than Practice removes all items from bins.
If you switch into Practice mode, any items already in bins will remain.
Return to Top or Table of Contents.
Problem Menu
The Problem menu enables the user to generate a new problem instance
that they can solve. There are three commands in this menu.
- Default Instance: This command returns the application to its
initial state with the default problem instance. This is the instance
the application always begins with.
- Random Instance: This command generates a new random problem instance
for the user to solve.
- Select Instance Number: This command generates a new random problem instance,
but requests an integer seed from the user. In this way, if the user would
like to retry a problem instance they previously solved, they can do so using the
same seed.
Return to Top or Table of Contents.
Operations Menu
The Operations Menu has the following three commands:
- Sort Decreasing: Sorts the list of items that are not
yet assigned to bins in decreasing order by size.
This command is only enabled when the application is in
one of the following modes: Practice, First-Fit Decreasing, and Best-Fit Decreasing.
It is disabled for the First-Fit and Best-Fit modes. See the
Mode Menu documentation for more information.
- Sort Increasing: Sorts the list of items that are not
yet assigned to bins in increasing order by size.
This command is only enabled when the application is in
one of the following modes: Practice, First-Fit Decreasing, and Best-Fit Decreasing.
It is disabled for the First-Fit and Best-Fit modes. See the
Mode Menu documentation for more information.
- Compute Lower Bound: Computes a lower bound on the number of
bins for the optimal solution. It may or may not be possible to pack the
items into this number of bins, but you definitely can't do it with fewer
bins.
Return to Top or Table of Contents.
Session Menu
The Session Menu has the following three commands:
- View Current Session Log: This command opens a dialog
window containing a human-readable summary of the user's activity
from the current session, including data such as time started, total
time in session, number of moves in each of the heuristic modes,
a list of problem instances that were solved using correct application
of the chosen heuristic, a detailed list of session activity, and
possibly a list of alerts. If the session log has not been modified
outside of the application, then there shouldn't be any alerts.
- Save Current Session Log: This command saves the current session
log to a file. The intended
purpose of the session log files is to enable instructors to validate that
a student has completed an assignment.
The file can be used to create the log as viewed in the
application with the View Current Session Log command, but it is not
in that format. It is in a format vaguely resembling XML, but it is not
true XML. See the note on alerts below. Do not attempt to manually alter
the contents of a session log file outside of the application. The file
extension is *.ibp. If you change the extension, the load command will
refuse to open the session log.
- Load Session Log: This command loads a session log file for
a previous session and presents it to the user in a summary format. It is
just like the View Current Session Log command, but for session logs
previously saved to files rather than the current session.
Session Logs Compatibility: Session Log files may or may not
be compatible with later or earlier versions of the application, so it is important
that you follow any directions from your instructor on what version to
use.
An important note on the Alerts: The purpose
of the alerts is for instructor use, such as to detect if a session log
has been tampered with, falsified, etc. If you know you haven't altered
a session log and discover alerts due to a bug, please consider submitting
an issue on GitHub, including the faulty session log file (use the Save Current
Session Log command). There is no personally identifiable information
in the session log files, which you can easily verify as the session
log files are plain text. The format will appear to you to be XML, but it is not
true XML. For example, fields are expected to be in a certain order,
in some cases spacing and new lines matter, among other things. This is all
on purpose to make manually changing the session log files harder to do.
So don't attempt to manually change the session log files. Even small
changes that wouldn't meaningfully alter XML, will potentially lead to
alerts when the session log is viewed by an instructor.
Return to Top or Table of Contents.
Info Menu
The Info Menu has the following three commands:
- Tutorial: This command will open a window containing a tutorial
on combinatorial optimization, bin packing, and in particular constructive
heuristics for the bin packing problem. First time users should start there.
- Help: This command opens this Help window.
- About: This command displays the copyright and license notices.
Return to Top or Table of Contents.
