ospf

Introduction

ospf is a solution for the modeling and coding process in developing complex operational research algorithm software, along with its development components. It aims to provide a modeling approach based on Domain Driven Design (DDD), enabling users to efficiently develop and maintain mathematical models, solution algorithms, and their implementation code throughout the entire software lifecycle. For more detailed information, design or documentation, please refer to the documentation page:

ospf: https://github.com/fuookami/ospf

🇺🇸 English | 🇨🇳 简体中文

Intermediate Expression

ospf introduces a concept called "intermediate expression" to facilitate DDD-based modeling. Intermediate expressions are used in mathematical models to represent intermediate results of computations, aiming to simplify the representation of the model and make it easier to understand and maintain. Intermediate expressions possess the following characteristics:

• they refer to named polynomials that are stored.
• they are semantically equivalent to anonymous polynomials.
• they are grammatically equivalent to variables, having a global scope and static lifetime.
• they can be constructed through an anonymous polynomial.

Arithmetic Intermediate Expression:

The initial purpose of designing intermediate expressions was to reduce redundancy in mathematical models. Therefore, the most basic arithmetic intermediate expressions are constructed using a polynomial, allowing users to replace all identical polynomials with this intermediate expression anywhere in the model.

$$ ExprSymbol = \sum_{i} x_{i} $$

$$ min \quad ExprSymbol $$

$$ s.t. \quad ExprSymbol \leq 1 $$

ospf automatically replaces each arithmetic intermediate expressions with specific polynomials when translating the model into interfaces for specific solvers. This translation process is transparent to the user, so the user does not need to know how the arithmetic intermediate expressions are implemented through which variables and operations.

Thus, we can divide the maintainers of mathematical models into two roles: "intermediate expressions maintainer" and "user of intermediate expressions". The intermediate expressions maintainers are responsible for defining and implementing intermediate expressions, while users of intermediate expressions do not concern themselves with the implementation of intermediate expresssions. They only focus on the definition and behavior of intermediate expressions and use these intermediate expressions to describe business logic in mathematical models.

This engineering practice is similar to Object-Oriented Design (OOD), where defining a class encapsulates variables and functions with the same semantics, and users only need to focus on their behavior without concerning themselves with their implementation. With such a foundation, we can then begin to introduce DDD.

Functional Intermediate Expression:

Building upon the concept of arithmetic intermediate expressions, ospf can also encapsulate non-arithmetic expressions such as logical operations into intermediate expressions.

$$ FuncSymbol = \bigvee_{i} x_{i} = Or(x_{1}, \, x_{2}, \, .. \, , \, x_{i}) $$

$$ s.t. \quad FuncSymbol = 1 $$

When ospf translates the model into interfaces for specific solvers, it automatically adds the intermediate variables and constraints required for each intermediate expressions. This translation process is transparent to the users, so the users don't need to know how the intermediate expressions are implemented through which intermediate variables and constraints. For example, the expression $FuncSymbol = \bigvee_{i} x_{i}$ will be translated as follows:

$$ s.t. \quad y = 1 $$

$$ \begin{cases} y \geq \frac{x_{i}}{\sup_{\leq}(x_{i})}, & \sup_{\leq}(x_{i}) > 1 \\\\ y \geq x_{i}, & else \end{cases} $$

$$ y \leq \sum_{i} x_{i} $$

$$ y \in \{ 0, 1 \} $$

Of course, you can also extend these intermediate expressions according to your own business requirements. At this point, you need to implement some interfaces to let ospf know which intermediate variables and constraints need to be added for these intermediate expressions.

The ospf-core only maintains arithmetic and logical functions. In fact, we can design and implement functional intermediate expressions based entirely on the domain, as part of domain engineering. For specific references, you can refer to the development package for specific problem domains in the ospf-framework.

Components

ospf is designed and implemented using an internal Domain Specific Language (DSL) format. Apart from some shared components, the rest are implemented in the target host language.

Shared Components

• examples: examples demonstrating how to use ospf for modeling and solving.

• framework: a set of common components developed for specific problem domains, including visualization tools for results.

• remote: a remote solver scheduler and server used to execute solvers on a server and retrieve results through a network interface.

Components In Host Language Implementation

each ospf implementation consists of the following components:

• utils: utilities containing classes and functions required for implementing ospf DSL.
• core: core components containing essential functionalities such as modeling, solver interfaces, result processing, etc.
  • core-plugin-XXX: solver plugins implementing solver interfaces for specific solvers.
  • core-plugin-heuristic: meta-heuristic algorithm plugins containing implementations of various common meta-heuristic algorithms.
• framework: problem-specific frameworks containing implementations of data processing, mathematical models, and solving algorithms tailored to specific problems. All designs and implementations are non-intrusive, allowing users to use them out of the box or extend them seamlessly, integrating with other frameworks or components.
  • framework-plugin-XXX: framework plugins implementing functionalities requiring middleware involvement, such as data persistence, asynchronous message communication.
  • bpp1d: 1D Bin Packing Problem (BPP) development package containing implementations of data processing, mathematical models, and solving algorithms for various 1D BPPs.
  • bpp2d: 2D Bin Packing Problem (BPP) development package containing implementations of data processing, mathematical models, and solving algorithms for various 2D BPPs.
  • bpp3d: 3D Bin Packing Problem (BPP) development package containing implementations of data processing, mathematical models, and solving algorithms for various 3D BPPs.
  • csp1d: 1D Cutting Stock Problem (CSP) development package containing implementations of data processing, mathematical models, and solving algorithms for various 1D CSPs.
  • csp2d: 2D Cutting Stock Problem (CSP) development package containing implementations of data processing, mathematical models, and solving algorithms for various 2D CSPs.
  • gantt-scheduling: gantt scheduling problem development package containing implementations of data processing, mathematical models, and solving algorithms for various Gantt chart scheduling problems. It can be used for scheduling and planning problems such as Advanced Production Scheduling (APS), Lot Scheduling Problem (LSP), etc.
  • network-scheduling: network scheduling problem development package containing implementations of data processing, mathematical models, and solving algorithms for various network scheduling problems. It can be used for scheduling and planning problems such as Vehicle Routing Problem (VRP), Facility Location Problem (FLP), etc.

Features And Progress

• ✔️：Stable version.
• ⭕：Development completed, unstable version.
• ❗：Under development, incomplete version.
• ❌：Planned, not started.

Core

Feature	C++	C#	Kotlin	Python	Rust
Modeling Language
MILP	❗	❌	✔️	❌	❗
MIQCQP	❌	❌	✔️	❌	❌
MINLP	❌	❌	❌	❌	❌
Solver Wrapper
GUROBI	❗	❌	✔️	❌	❗
GUROBI-11	❗	❌	✔️	❌	❗
CPLEX	❗	❌	✔️	❌	❗
COPT	❌	❌	❌	❌	❌
SCIP	❗	❌	✔️	❌	❗
COPIN-OR	❗	❌	❗	❌	❗
else	planing
Meta-Heuristic Algorithm
PSO	❗	❌	✔️	❌	❗
GA	❗	❌	❗	❌	❗
SAA	❗	❌	❗	❌	❗
HCA	❗	❌	❗	❌	❗
NMS	❗	❌	❗	❌	❗
else	planing

Framework

Feature	C++	C#	Kotlin	Python	Rust	Visualization
Basic Framework	❗	❌	✔️	❌	❗
bpp1d	❌	❌	❌	❌	❌	❌
bpp2d	❌	❌	❌	❌	❌	❌
bpp3d	❌	❌	⭕	❌	❌	✔️
csp1d	❌	❌	⭕	❌	❌	✔️
csp2d	❌	❌	❌	❌	❌	❌
gantt-scheduling	❌	❌	✔️	❌	❌	✔️
network-scheduling	❌	❌	❌	❌	❌	❌
else	planing

Remote

Feature
Solver Serivce	❗
Meta-Heuristic Algorithm Service	❌
Dispatcher	❗
Time Slice Cycle	❌