moptipy is a library with implementations of metaheuristic optimization methods in Python 3.10 that also offers an environment for replicable experiments (flyer).
moptipyapps is a collection of applications and experiments based on moptipy.
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 moptipyappsThis 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.gitIf 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://[email protected]/thomasWeise/moptipyapps
pip install moptipyappsThis 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.
Here we list the applications.
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.
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:
- plot a packing chart
- apply a randomized local search to one 2D bin packing instance
- measure the runtime of the different encodings for the 2D bin packing problem
The encodings were originally implemented by Mr. Rui ZHAO (赵睿), [email protected], a Master's student of the Institute of Applied Optimization (应用优化研究所, http://iao.hfuu.edu.cn) of 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.
When developing and applying randomized algorithms, proper testing and checking of the source code is of utmost importance. If we apply a randomized metaheuristic to an optimization problem, then we usually do not which solution quality we can achieve. Therefore, we can usually not know whether we have implemented the algorithm correctly. In other words, detecting bugs is very hard. Unfortunately, this holds also for the components of the algorithms, such as the search operators, especially if they are randomized as well. A bug may lead to worse results and we might not even notice that the worse result quality is caused by the bug. We may think that the algorithm is just not working well on the problem.
Therefore, we need to test all components of the algorithm as far as we can. We can try check, for example, if a randomized nullary search operator indeed creates different solutions when invoked several times. We can try to check whether an algorithm fails with an exception. We can try to check whether the search operators create valid solutions and whether the algorithm passes valid solutions to the objective function. We can try to whether an objective function produces finite objective values and if bounds are specified for the objective values, we can check whether they indeed fall within these bounds. Now we cannot prove that there are no such bugs, due to the randomization. But by testing a few hundred times, we can at least detect very obvious and pathological bugs.
To ease such testing for you, we provide a set of tools for testing implemented algorithms, spaces, and operators in the package moptipyapps.tests.
Here, you can find functions where you pass in instances of your implemented components and they are checked for compliance with the moptipy API and the problem setups defined in moptipyapps.
In other words, if you go and implement your own algorithms, operators, and optimization problems, you can use our pre-defined unit tests to give them a thorough check before using them in production.
Again, such tests cannot prove the absence of bugs.
But they can at least give you a fair shot to detect pathological errors before wasting serious experimentation time.
We also try to extensively test our own code, see the coverage report of moptipy and moptipyapps.
Another way to try to improve and maintain code quality is to use static code analysis and type hints where possible and reasonable. A static analysis tool can inform you about, e.g., unused variables, which often result from a coding error. It can tell you if the types of expressions do not match, which usually indicates a coding error, too. It can tell you if you perform some security-wise unsafe operations (which is less often a problem in optimization, but it does not hurt to check). Code analysis tools can also help you to enforce best practices, which are good for performance, readability, and maintainability. They can push you to properly format and document your code, which, too, improve readability, maintainability, and usability. They even can detect a set of well-known and frequently-occurring bugs. We therefore also run a variety of such tools on our code base, including (in alphabetical order):
autoflake, a tool for finding unused imports and variablesbandit, a linter for finding security issuesdodgy, for checking for dodgy looking values in the codeflake8, a collection of lintersflake8-bugbear, for finding common bugsflake8-eradicate, for finding commented-out codeflake8-use-fstring, for checking the correct use of f-stringsmypy, for checking types and type annotationspycodestyle, for checking the formatting and coding style of the sourcepydocstyle, for checking the format of the docstringspyflakes, for detecting some errors in the codepylint, another static analysis toolpyroma, for checking whether the code complies with various best practicesruff, a static analysis tool checking a wide range of coding conventionssemgrep, another static analyzer for finding bugs and problemstryceratops, for checking against exception handling anti-patternsunimport, for checking against unused import statementsvulture, for finding dead code
On git pushes, GitHub also automatically runs CodeQL to check for common vulnerabilities and coding errors. We also turned on GitHub's private vulnerability reporting and the Dependabot vulnerability and security alerts.
Using all of these tools increases the build time. However, combined with thorough unit testing and documentation, it should help to prevent bugs, to improve readability, maintainability, and usability of the code. It does not matter whether we are doing research or try to solve practical problems in the industry — we should always strive to make good software with high code quality.
Often, researchers in particular think that hacking something together that works is enough, that documentation is unimportant, that code style best practices can be ignored, and so on. And then they wonder why they cannot understand their own code a few years down the line (at least, this happened to me in the past…). Or why no one can use their code to build atop of their research (which is the normal case for me).
Improving code quality can never come later.
We always must maintain high coding and documentation standards from the very beginning.
While moptipy may still be far from achieving these goals, at least we try to get there.
Anyway, you can find our full make build running all the tests, doing all the static analyses, creating the documentation, and creating and packaging the distribution files here.
Besides the basic moptipyapps dependencies, it requires a set of additional dependencies.
These are all automatically installed during the build procedure.
The build only works under Linux.
moptipyapps is a library for implementing, using, and experimenting with metaheuristic optimization algorithms.
Our project is developed for scientific, educational, and industrial applications.
Copyright (C) 2023 Thomas Weise (汤卫思教授)
Dr. Thomas Weise (see Contact) holds the copyright of this package except for the data of the benchmark sets we imported from other sources.
moptipyapps is provided to the public as open source software under the GNU GENERAL PUBLIC LICENSE, Version 3, 29 June 2007.
Terms for other licenses, e.g., for specific industrial applications, can be negotiated with Dr. Thomas Weise (who can be reached via the contact information below).
This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see https://www.gnu.org/licenses/.
Please visit the contributions guidelines for moptipy if you would like to contribute to our package.
If you have any concerns regarding security, please visit our security policy.
- The included benchmark instance data of the two-dimensional bin packing is taken from 2DPackLib. It has been stored in a more size-efficient way and some unnecessary information has been stripped from it (as we really only need the raw bin packing data). Nevertheless, the copyright of the original data lies with the authors 2DPackLib or the original authors of the datasets used by them.
If you have any questions or suggestions, please contact Prof. Dr. Thomas Weise (汤卫思教授) of the Institute of Applied Optimization (应用优化研究所, IAO) of the School of Artificial Intelligence and Big Data (人工智能与大数据学院) at Hefei University (合肥学院) in Hefei, Anhui, China (中国安徽省合肥市) via email to [email protected] with CC to [email protected].