👁️ ellalgo-cpp
Ellipsoid Algorithm in Modern C++ The Ellipsoid Method as a linear programming algorithm was first introduced by L. G. Khachiyan in 1979. It is a polynomial-time algorithm that uses ellipsoids to iteratively reduce the feasible region of a linear program until an optimal solution is found. The method works by starting with an initial ellipsoid that contains the feasible region, and then successively shrinking the ellipsoid until it contains the optimal solution. The algorithm is guaranteed to converge to an optimal solution in a finite number of steps.
The method has a wide range of practical applications in operations research. It can be used to solve linear programming problems, as well as more general convex optimization problems. The method has been applied to a variety of fields, including economics, engineering, and computer science. Some specific applications of the Ellipsoid Method include portfolio optimization, network flow problems, and the design of control systems. The method has also been used to solve problems in combinatorial optimization, such as the traveling salesman problem.
What is 🪜 Parallel Cut?
In the context of the Ellipsoid Method, a parallel cut refers to a pair of linear constraints of the form aTx <= b and -aTx <= -b, where a is a vector of coefficients and b is a scalar constant. These constraints are said to be parallel because they have the same normal vector a, but opposite signs. When a parallel cut is encountered during the Ellipsoid Method, both constraints can be used simultaneously to generate a new ellipsoid. This can improve the convergence rate of the method, especially for problems with many parallel constraints.
✨ Features
- Support parallel cut.
- Support discrete optimization.
- Support traditional or stable version.
- Modern CMake practices
- Suited for single header libraries and projects of any scale
- Clean separation of library and executable code
- Integrated test suite
- Continuous integration via GitHub Actions
- Code coverage via codecov
- Code formatting enforced by clang-format
- Reproducible dependency management via FetchContent
- Installable target with
find_packagesupport - Automatic documentation and deployment with Doxygen and GitHub Pages
- Optional clang-tidy static analysis
Usage
Adjust the template to your needs
- Use this repo as a template.
- Replace all occurrences of "EllAlgo" in the relevant CMakeLists.txt with the name of your project
- Capitalization matters here:
EllAlgomeans the name of the project, whileellalgois used in file names. - Remember to rename the
include/ellalgodirectory to use your project's lowercase name and update all relevant#includes accordingly.
- Capitalization matters here:
- Replace the source files with your own
- Add your project's codecov token to your project's github secrets under
CODECOV_TOKEN - Happy coding!
Eventually, you can remove any unused files, such as the standalone directory or irrelevant github workflows for your project. Feel free to replace the License with one suited for your project.
A single CMakeLists.txt at the project root defines the library, tests, standalone executable and optional targets. During development it is usually convenient to build everything at once.
Build and run the standalone target
Use the following commands from the project's root directory to build and run the executable target.
Build and run test suite
Use the following commands from the project's root directory to run the test suite.
To collect code coverage information, run CMake with the -DELLALGO_ENABLE_COVERAGE=1 option and build the coverage target (GCC/Clang, requires gcovr).
Run clang-format
Use the following command from the project's root directory to fix C++ source style. This requires clang-format to be installed on the current system.
Build the documentation
The documentation is automatically built and published whenever a GitHub Release is created. To manually build documentation, call the following command.
To build the documentation locally, you will need Doxygen and Graphviz installed on your system.
Build everything at once
A single build configuration from the project root builds the library, tests and standalone together. This is useful during development, as it exposes all targets to your IDE and avoids redundant builds of the library.
Additional tools
The following optional tools can be enabled through CMake configuration arguments.
clang-tidy
Static analysis with clang-tidy can be enabled by configuring CMake with -DELLALGO_ENABLE_CLANG_TIDY=ON and building the clang-tidy target:
Code coverage
Coverage reporting (GCC/Clang, requires gcovr) can be enabled with -DELLALGO_ENABLE_COVERAGE=1:
❓ FAQ
Can I use this for header-only libraries?
Yes, however you will need to change the library type to an INTERFACE library (empty sources, all PUBLIC flags) in CMakeLists.txt. See here for an example header-only library based on the template.
I don't need a standalone target / documentation. How can I get rid of it?
Simply remove the standalone / documentation directory and according github workflow file.
Can I build the standalone and tests at the same time? / How can I tell my IDE about all subprojects?
All targets are defined in the single root CMakeLists.txt, so a single cmake -B build configuration exposes the library, tests and standalone to your IDE at once.
I see you are using
GLOBto add source files in CMakeLists.txt. Isn't that evil?
Glob is considered bad because any changes to the source file structure might not be automatically caught by CMake's builders and you will need to manually invoke CMake on changes. I personally prefer the GLOB solution for its simplicity, but feel free to change it to explicitly listing sources.
I want create additional targets that depend on my library. Should I modify the main CMakeLists to include them?
Avoid including derived projects from the libraries CMakeLists (even though it is a common sight in the C++ world), as this effectively inverts the dependency tree and makes the build system hard to reason about. Instead, create a new directory or project with a CMakeLists that adds the library as a dependency (e.g. like the test_installed directory). Depending type it might make sense move these components into a separate repositories and reference a specific commit or version of the library. This has the advantage that individual libraries and components can be improved and updated independently.
You recommend to add external dependencies using FetchContent. Will this force users of my library to use FetchContent as well?
FetchContent is part of CMake itself, so users only need a recent CMake version. If problems do arise, users can always opt-out by defining the CMake or env variable FETCHCONTENT_FULLY_DISCONNECTED or by providing the dependencies through FETCHCONTENT_SOURCE_DIR_<UPPERCASE_NAME>. This should also enable users to use the project with their favorite external C++ dependency manager, such as vcpkg or Conan.
Can I configure and build my project offline?
No internet connection is required for building the project, however when using FetchContent missing dependencies are downloaded at configure time. To avoid redundant downloads, it's highly recommended to point FETCHCONTENT_SOURCE_DIR_* at local checkouts of the dependencies (e.g. FETCHCONTENT_SOURCE_DIR_SPDLOG=$HOME/git/spdlog). This will enable offline configurations when dependencies are already available locally.
Can I use CPack to create a package installer for my project?
As there are a lot of possible options and configurations, this is not (yet) in the scope of this template. See the CPack documentation for more information on setting up CPack installers.
This is too much, I just want to play with C++ code and test some libraries.
Perhaps the MiniCppStarter is something for you!
Related projects and alternatives
- ellalgo-simple: Simplified header-only variant (xmake/CMake, lighter CI)
- ModernCppStarter & PVS-Studio Static Code Analyzer: Official instructions on how to use the ModernCppStarter with the PVS-Studio Static Code Analyzer.
- cpp-best-practices/gui_starter_template: A popular C++ starter project, created in 2017.
- filipdutescu/modern-cpp-template: A recent starter using a more traditional approach for CMake structure and dependency management.
- vector-of-bool/pitchfork: Pitchfork is a Set of C++ Project Conventions.
Star History
