moptipyapps: Applications of Metaheuristic Optimization in Python

Introduction
Installation
Applications
Unit Tests and Static Analysis
License
Contact

1. Introduction

moptipy is a library with implementations of metaheuristic optimization methods in Python 3.12 that also offers an environment for replicable experiments (flyer). moptipyapps is a collection of applications and experiments based on moptipy.

2. Installation

In order to use this package and to, e.g., run the example codes, you need to first install it using pip or some other tool that can install packages from PyPi. You can install the newest version of this library from PyPi using pip by doing

pip install moptipyapps

This will install the latest official release of our package as well as all dependencies. If you want to install the latest source code version from GitHub (which may not yet be officially released), you can do

pip install git+https://github.com/thomasWeise/moptipyapps.git

If you want to install the latest source code version from GitHub (which may not yet be officially released) and you have set up a private/public key for GitHub, you can also do:

git clone ssh://git@github.com/thomasWeise/moptipyapps
pip install moptipyapps

This may sometimes work better if you are having trouble reaching GitHub via https or http.

You can also clone the repository and then run a make build, which will automatically install all dependencies, run all the tests, and then install the package on your system, too. This will work only on Linux, though. It also installs the dependencies for building, which include, e.g., those for unit testing and static analysis. If this build completes successful, you can be sure that moptipyapps will work properly on your machine.

All dependencies for using and running moptipyapps are listed at here. The additional dependencies for a full make build, including unit tests, static analysis, and the generation of documentation are listed here.

3. Applications

Here we list the applications of moptipy. Step by step, we will add more and more interesting optimization problems. For each problem, we provide means to load the problem instances and a basic infrastructure to construct optimization algorithms for solving them.

3.1. Two-Dimensional Bin Packing Problem

In the package moptipyapps.binpacking2d, we provide tools for experimenting and playing around with the two-dimensional bin packing problem. Bin packing is a classical domain from Operations Research. The goal is to pack objects into containers, the so-called bins. We address two-dimensional rectangular bin packing. We provide the bin packing instances from 2DPackLib as resources together with this package as well as the four non-trivial "Almost Squares in Almost Squares" instances. Each such instances defines a set of n_different_items objects Oi with i from 1..n_different_objects. Each object Oi is a rectangle with a given width and height. The object occur is a given multiplicity repetitions(O_i), i.e., either only once or multiple times. The bins are rectangles with a given width and height too. The goal of tackling such an instance is to package all the objects into as few as possible bins. The objects therefore may be rotated by 90 degrees.

We address this problem by representing a packing as a signed permutation with repetitions of the numbers 1..n_different_objects, where the number i occurs repetitions(O_i) times. If an object is to be placed in a rotated way, this is denoted by using -i instead of i. Such permutations are processed from beginning to end, placing the objects into bins as they come according to some heuristic encoding. We provide two variants of the Improved Bottom Left encoding. The first one closes bins as soon as one object cannot be placed into them. The second one tries to put each object in the earliest possible bin. While the former one is faster, the latter one leads to better packings.

We can then apply a black-box metaheuristic to search in the space of these signed permutations with repetitions. The objective function would be some measure consistent with the goal of minimizing the number of bins used.

Examples:

Important work on this code has been contributed by Mr. Rui ZHAO (赵睿) during his time as Master's student at the School of Artificial Intelligence and Big Data (人工智能与大数据学院) at Hefei University (合肥学院) in Hefei, Anhui, China (中国安徽省合肥市) under the supervision of Prof. Dr. Thomas Weise (汤卫思教授), who then refined the implementations.

3.2. The Traveling Salesperson Problem (TSP)

In the package moptipyapps.tsp, we provide tools to run experiments and play around with the Traveling Salesperson Problem (TSP) . A TSP instance is defined as a fully-connected graph with n_cities nodes. Each edge in the graph has a weight, which identifies the distance between the nodes. The goal is to find the shortest tour that visits every single node in the graph exactly once and then returns back to its starting node. Then nodes are usually called cities. A tour can be represented in path representation, which means that it is stored as a permutation of the numbers 0 to n_cities-1. The number at index k identifies that k-th city to visit. So the first number in the permutation identifies the first city, the second number the second city, and so on. The length of the tour can be computed by summing up the distances from the k-th city to the k+1-st city, for k in 0..n_cities-2 and then adding the distance from the last city to the first city.

We use the TSP instances from TSPLib, the maybe most important benchmark set for the TSP. 110 of these instances are included as resources in this package.

Examples:

Important work on this code has been contributed by Mr. Tianyu Liang (梁天宇) during his time as Master's student at the School of Artificial Intelligence and Big Data (人工智能与大数据学院) at Hefei University (合肥学院) in Hefei, Anhui, China (中国安徽省合肥市) under the supervision of Prof. Dr. Thomas Weise (汤卫思教授), who then refined the implement

Moptipyapps

Install / Use

README