micheleurbani/albp

A solver for Assembly Line Balancing Problems (ALBP)

albp's Issues

Observation function

Observation function

An observation function is an Ecole environment that returns features of the actions in the action set.

The set of features depends on the problem representation we want to use.

Direct problem representation

Use problem attributes directly as in the canonical form {min cx, Ax <= b}.
Variable features are harder to characterize according to the problem under study. An example of generic features is that provided by Khalil.

Indirect problem representation

A solution to the problem is described as a partition of the set of tasks, where each element corresponds to the set of tasks assigned to a station.

Features are easier to figure out than with the direct representation.

Information extraction from ecole.scip.Model

We need a fast and reliable way to extract the indirect solution representation from the ecole.scip.Model (direct representation). The availability of problem information would help the extraction of variable values. For example, by providing the number of activities and the type of problem, it is possible to understand which variables have been used and how they are indexed, hence retrieving their value and computing, e.g., the list of unassigned tasks or the list of empty stations.

The problem can be divided into two subproblems: the first concerns retrieving information about the problem and it is tackled in the issue #4, whereas accessing information from the ecole.scip.Model concerns accessing the model at runtime and is tackled in the following.

Depending on the programming language, I see two possible ways to access information from ecole.scip.Model.

Python observation function

Exploiting the model name to retrieve the type of the problem, it is possible to access variables correctly due to the different MILP formulations that were adopted.

C++ observation function

ALBP file reader

ALBP file reader

Accessing ALBP information directly to guide the search process is necessary because retrieving them from the ecole.scip.Model is pretty inconvenient. The assumption of having all the problem information available is largely accepted in the literature and is a basic assumption in all papers.

Inherit from FileGenerator class

The ecole.instance.FileGenerator iterates over a folder and its subfolders to find .mps and .lp files.
The class is written in C++ and could be used to read row ALBP files, retrieve the information, and create a scip.Model which stores ALBP information directly.

A list of possible issues is the following:

• Each problem presents a different dataset structure and a switch statement would be required to differentiate the procedure for all of them.

Python objects and .lp model

pyscipopt.Model objects are not serializable, therefore it is impossible to rely on these only.

Problem data are stored as plain Python dictionaries using pickle. The instance generator iterates over .lp problem files, reads the model, initializes a pyscipopt.Model, reads model data, and appends this to the data attribute of the pyscipopt.Model object.

Randomization of results

The ecole.RandomGenerator class controls the fetching process.

Benchmark results

Results for benchmarking

• How to organize results to be complete and easy to use?
• Link results to a problem type and to the source where they were collected.

Problem generator

Complete code to write LPs of:

• SALBP 1 and 2
• PALBP
• TALBP
• UALBP
• ErgoALBP
• VWALBP
• ARALBP