What is OSPF?

OSPF is a solution and development component for modeling and coding processes in complex operations research optimization algorithms. OSPF aims to provide a modeling approach based on Domain-Driven Design (DDD), enabling users to simply and efficiently develop and maintain mathematical models, solution algorithms, and their implementation code throughout the entire software lifecycle.

Reading paths

Start with Getting Started to run a complete model, then read The Language of Operations Research, The Modeling and Solving Workflow, and Understanding Solver Results. These explain why intermediates belong to the modeling language, how a model is assembled, and what its results mean.

For complex business organization, continue with DDD Architecture. For the path from expressions to different backends, read Symbolic Expressions and Compiler-Like Architecture. The discussion below explains OSPF's role through the motivation for abstraction and contrasting model examples.

Implementations for various host languages can be found in the following code repository directories:

• C++: https://github.com/fuookami/ospf-cpp
• C#: https://github.com/fuookami/ospf-csharp
• Kotlin: https://github.com/fuookami/ospf-kotlin
• Python: https://github.com/fuookami/ospf-python
• Rust: https://github.com/fuookami/ospf-rust

Introduction

When software engineers build complex systems, they consciously or unconsciously apply numerous cognitive models. It is these effective cognitive models that help us construct today's incredibly complex information systems, ushering us into the digital intelligence era. These cognitive models include but are not limited to: abstraction, layering, divide and conquer, evolution, protocols, etc., which are already pervasive in the architectural design of our various information systems.

During the execution of cognitive tasks, we certainly need to temporarily store and process information resources. This process utilizes what cognitive psychology calls working memory, the human cognitive center. However, working memory has capacity limitations, meaning we can only simultaneously cognize a limited number of things, generally considered to be at most 4 "chunks". These "chunks" can be numbers, letters, words, or other forms. However, if we master a mathematical or scientific technique, or a concept, it occupies less space in working memory. The freed brain space then allows us to more easily handle other ideas.

So how is abstraction applied to our software structure design? Simply put, abstraction is assembling some basic elements into a composite element, then directly using that composite element. We can see the following three code segments, which express the same semantics: comparing the area sizes of two rectangles. Their abstraction level gradually increases.

Procedural 1:

fn main() {
    let length1: f64 = 10.;
    let width1: f64 = 8.;
    let area1 = length1 * width1;
    let length2: f64 = 11.;
    let width2: f64 = 7.;
    let area2 = length2 * width2;
    assert (area1 > area2);
}

Procedural 2:

fn area(length: f64, width: f64) -> f64 {
    length * width
}

fn bigger_than(length1: f64, width1: f64, length2: f64, width: f64) -> bool {
    area(length1, width1) > area(length2, width2)
}

fn main() {
    let length1: f64 = 10.;
    let width1: f64 = 8.;
    let length2: f64 = 11.;
    let width2: f64 = 7.;
    assert (bigger_than(length1, width1, length2, width2));
}

Object-Oriented:

struct Rectangle {
    length: f64,
    width: f64
}

impl Rectangle {
    fn new(l: f64, w: f64) -> Self {
        Self {
            length: l,
            width: w
        }
    }

    fn area(&self) -> f64 {
        self.length * self.width
    }

    fn bigger_than(&self, rhs: &Self) -> bool {
        self.area() > rhs.area()
    }
}

fn main() {
    let r1 = Rectangle::new(10., 8.);
    let r2 = Rectangle::new(11., 7.);
    assert (r1.bigger_than(&r2));
}

The first segment has no abstraction at all. The second segment abstracts the computation process and then uses these computation processes, which we generally call procedural programming. The third segment abstracts both the concept of a rectangle and the computation processes around rectangles, then uses this concept and these computation processes, which we generally call object-oriented programming.

As the abstraction level increases, we can easily see that the code volume in the main function gradually decreases, and the semantic level gradually improves. Even though the actual code volume of the last segment is the largest, in modern times, essentially all programmers would use the writing style of the third segment. We can rely on the compiler to translate it into the same machine code, so naturally, during the coding process, we would choose a more human-oriented writing style.

Traditional operations research algorithm development lacks abstraction methods. The lack of abstraction methods leads to poor communication between product engineers and algorithm engineers, and between algorithm engineers themselves, due to the absence of a unified common language. Simultaneously, because various software structure design techniques cannot be applied in development practice, the implementation code of mathematical models is difficult to reuse. In large-scale operations research algorithm development, significant human-hours are consumed in repetitive work. Additionally, the code style of mathematical model implementation code is heavily influenced by individual algorithm engineers, making collaboration between algorithm engineers difficult.

Intermediate Values

An intermediate value gives an expression a business name so constraints, objectives, and reports can share its definition. Compartment weight, for example, can serve capacity, area-loading, and line-loading rules without repeating the aggregation in each rule.

Arithmetic intermediates encapsulate arithmetic relationships; function intermediates encapsulate functions with explicit mathematical semantics. They can compose like variables at reference sites, but are not freely selectable values or process-global objects. A solver representation may expand expressions or introduce auxiliary variables and constraints.

The Language of Operations Research explains primitives, composition, and abstraction. Compiler-Like Architecture explains semantic preservation during conversion. Individual function-symbol pages provide their definitions and actual constraints.

The example below contrasts traditional modeling with intermediate-value abstraction to show how it supports maintenance.

Changes in Modeling with OSPF

Problem Description

In a given telecommunications network structure, to quickly and cost-effectively deliver video content to each residential area, video content storage servers need to be placed near some network nodes in this given network structure.

Currently known:

1. Each link has bandwidth $Bandwidt{h}^{Max}$ and bandwidth cost $Cos{t}^{Bandwidth}$;
2. Each server has load capacity $Capacity$ and usage cost $Cos{t}^{Service}$;
3. Each consumer node has demand $Demand$.

Determine the placement locations for video content storage servers and bandwidth links to minimize server usage cost and link usage cost, while satisfying the following conditions:

1. Each node can deploy at most one server;
2. Each server can be deployed to at most one node;
3. Meet all residential area video playback demands;
4. Transit node traffic must be balanced.

Traditional Mathematical Model

Sets

$N$: Set of nodes.

$N^N$: Set of normal (non-client) nodes.

$N^C$: Set of user nodes.

$S$: Set of servers.

$E$: Set of links.

Constants

$Cos{t}_s^{Service}$: Usage cost of server $s$.

$Cos{t}_{e_{ij}}^{Bandwidth}$: Unit bandwidth usage cost of the link between node $i$ and node $j$.

$Bandwidt{h}_{e_{ij}}^{Max}$: Maximum bandwidth of the link between node $i$ and node $j$.

$Capacit{y}_s$: Carrying capacity of server $s$.

$Deman{d}_i$: Bandwidth demand of node $i$.

Variables

$x_{is}$: Deploy server $s$ at normal node $i$.

$y_{e_{ij},s}$: Bandwidth occupied by server $s$ on the link between normal node $i$ and node $j$.

Optimization Objective

$$\begin{array}{}\text{(1)}& min& \sum _{s\in S}Cos{t}_s^{Service}\cdot \sum _{i\in N^N}{x}_{is}\text{(2)}& & +\sum _{i\in N^N}\sum _{j\in N^N}Cos{t}_{e_{ij}}^{Bandwidth}\cdot \sum _{s\in S}{y}_{e_{ij},s}\end{array}$$

Where $(1)$ is server usage cost, and $(2)$ is bandwidth usage cost.

Constraints

$$\begin{array}{}\text{(3)}& \text{s.t.}& \sum _{s\in S}{x}_{is}\le 1,& \mathrm{\forall }i\in N^N\text{(4)}& & \sum _{i\in N^N}{x}_{is}\le 1,& \mathrm{\forall }s\in S\text{(5)}& & y_{e_{ij},s}\le Bandwidt{h}_{e_{ij}}^{Max}\cdot \sum _{i\in N^N}{x}_{is},& \mathrm{\forall }i\in N^N,\mathrm{\forall }j\in N,\mathrm{\forall }s\in S\text{(6)}& & \sum _{s\in S}\sum _{i\in N^N}{y}_{e_{ij},s}\ge Deman{d}_i,& \mathrm{\forall }j\in N^C\text{(7)}& & \sum _{j\in N}{y}_{e_{ij},s}-\sum _{j\in N^N}{y}_{e_{ji},s}\le \sum _{j\in N}Bandwidt{h}_{e_{ij}}^{Max}\cdot \sum _{s\in S}{x}_{js},& \mathrm{\forall }i\in N^N\text{(8)}& & \sum _{j\in N}{y}_{e_{ij},s}-\sum _{j\in N^N}{y}_{e_{ji},s}\le Capacit{y}_s\cdot x_{is},& \mathrm{\forall }i\in N^N,\mathrm{\forall }s\in S\text{(9)}& & x_{is}\in \{0,1\},& \mathrm{\forall }i\in N^N,\mathrm{\forall }s\in S\text{(10)}& & y_{e_{ij},s}\in R^{\ast },& \mathrm{\forall }i\in N^N,\mathrm{\forall }j\in N,\mathrm{\forall }s\in S\end{array}$$

Where $(3)$ constrains each node to deploy at most one server, $(4)$ constrains each server to be deployed to at most one node, $(5)$ constrains link used bandwidth not to exceed link maximum, and only servers can use bandwidth, $(6)$ constrains meeting consumer node demands, $(7)$ constrains transit node traffic to be balanced, $(8)$ constrains server node net output not to exceed server capacity, $(9)$ and $(10)$ constrain the value ranges of decision variables.

Modeling with OSPF: Using Intermediate Values to Abstract and Encapsulate Duplicate Parts

Overview

The mathematical model design method based on large-scale reuse is essentially using intermediate value-based abstraction design and modularization of mathematical models. The intermediate values refined in each bounded context are the interfaces of that context to the outside, and other contexts can use these interfaces.

In this problem, we can easily identify two dependent business domains: routing and bandwidth. The routing domain describes whether servers are used and where they are deployed if used; the bandwidth domain, based on the routing domain, describes the bandwidth occupied on each link if the server cluster is deployed this way. Next, we will perform mathematical modeling using this bounded context division method.

Routing Context

Variables

$x_{is}\in \{0,1\}$: Deploy server $s$ at normal node $i$.

Intermediate Values

1. Whether Server is Deployed at Node

$${\text{Assignment}}_i^{\text{Node}}=\sum _{s\in S}{x}_{is},\mathrm{\forall }i\in N^N$$

2. Whether Server is Deployed

$${\text{Assignment}}_s^{\text{Service}}=\sum _{i\in N^N}{x}_{is},\mathrm{\forall }s\in S$$

Objective Function

1. Minimize Server Deployment Cost

Description: Server usage cost should be as low as possible.

$$min\sum _{s\in S}{\text{Cost}}_s^{\text{Service}}\cdot {\text{Assignment}}_s^{\text{Service}}$$

Constraints

1. Node Deployment Constraint

Description: Each node can deploy at most one server.

$$\text{s.t.}{\text{Assignment}}_i^{\text{Node}}\le 1,\mathrm{\forall }i\in N^N$$

2. Server Deployment Constraint

Description: Each server can be deployed to at most one node.

$$\text{s.t.}{\text{Assignment}}_s^{\text{Service}}\le 1,\mathrm{\forall }s\in S$$

Bandwidth Context

Variables

$y_{e_{ij},s}\in R^{\ast }$: Bandwidth occupied by server $s$ on the link from normal node $i$ to node $j$.

Intermediate Values

1. Used Bandwidth

$${\text{Bandwidth}}_{e_{ij}}=\sum _{s\in S}{y}_{e_{ij},s},\mathrm{\forall }i\in N^N,\mathrm{\forall }j\in N$$

2. Incoming Bandwidth

$${\text{Bandwidth}}_{js}^{\text{Indegree, Service}}=\sum _{i\in N^N}{y}_{e_{ij},s},\mathrm{\forall }j\in N,\mathrm{\forall }s\in S$$$${\text{Bandwidth}}_j^{\text{Indegree, Node}}=\sum _{s\in S}{\text{Bandwidth}}_{js}^{\text{Indegree, Service}},\mathrm{\forall }j\in N$$

3. Outgoing Bandwidth

$${\text{Bandwidth}}_{is}^{\text{Outdegree, Service}}=\sum _{j\in N}{y}_{e_{ij},s},\mathrm{\forall }i\in N^N,\mathrm{\forall }s\in S$$$${\text{Bandwidth}}_i^{\text{Outdegree, Node}}=\sum _{s\in S}{\text{Bandwidth}}_{js}^{\text{Outdegree, Service}},\mathrm{\forall }i\in N^N$$

4. Net Outflow Bandwidth

$${\text{Bandwidth}}_{is}^{\text{OutFlow, Service}}={\text{Bandwidth}}_{is}^{\text{Outdegree, Service}}-{\text{Bandwidth}}_{is}^{\text{Indegree, Service}},\mathrm{\forall }i\in N^N,\mathrm{\forall }s\in S$$$${\text{Bandwidth}}_i^{\text{OutFlow, Node}}=\sum _{s\in S}{\text{Bandwidth}}_{is}^{\text{OutFlow, Service}},\mathrm{\forall }i\in N^N$$

Objective Function

1. Minimize Link Bandwidth Usage Cost

Description: Link bandwidth usage cost should be as low as possible.

$$min\sum _{i\in N^N}\sum _{j\in N^N}{\text{Cost}}_{e_{ij}}^{\text{Bandwidth}}\cdot {\text{Bandwidth}}_{e_{ij}}$$

Constraints

1. Link Bandwidth Constraint

Description: Link used bandwidth does not exceed link maximum, and only servers can use bandwidth.

$$\text{s.t.}{y}_{e_{ij},s}\le {\text{Bandwidth}}_{e_{ij}}^{Max}\cdot {\text{Assignment}}_s^{\text{Service}},\mathrm{\forall }i\in N^N,\mathrm{\forall }j\in N,\mathrm{\forall }s\in S$$

2. Terminal Node Demand Constraint

Description: Must satisfy consumer node demands.

$$\text{s.t.}{\text{Bandwidth}}_i^{\text{Indegree, Node}}\ge {\text{Demand}}_i,\mathrm{\forall }i\in N^C$$

3. Transit Node Traffic Constraint

Description: Transit node traffic must be balanced.

$$\text{s.t.}{\text{Bandwidth}}_i^{\text{OutFlow, Node}}\le {\text{Bandwidth}}_i^{Max,Outdegree}\cdot {\text{Assignment}}_i^{\text{Node}},\mathrm{\forall }i\in N^N$$

Where:

$${\text{Bandwidth}}_i^{Max,Outdegree}=\sum _{j\in N}{\text{Bandwidth}}_{e_{ij}}^{Max},\mathrm{\forall }i\in N^N$$

4. Server Capacity Constraint

Description: Server node net output does not exceed server capacity.

$$\text{s.t.}{\text{Bandwidth}}_{is}^{\text{OutFlow, Service}}\le {\text{Capacity}}_s\cdot x_{is},\mathrm{\forall }i\in N^N,\mathrm{\forall }s\in S$$

Code Implementation

Code implementation can be referenced: Example Page

Business Architecture and Integration Architecture

The mathematical model design method based on large-scale reuse divides the mathematical model into two parts: routing context and bandwidth context. In fact, it also divides the entire server placement business into two themes: routing and bandwidth. The final delivered algorithm application is responsible for combining these two parts to provide a complete algorithm service. This process is generally called mapping problem space to solution space. It brings a characteristic that the domain layer and application layer of the integration architecture have the same structure as the business architecture.

If we have different users with multi-active requirements on these basic businesses, we can similarly decompose the multi-active business and implement it as a multi-active context. By constructing an algorithm application that simultaneously integrates routing context, bandwidth context, and multi-active context, we can relatively quickly deliver this multi-active algorithm application compared to re-implementation, while reusing the routing context and bandwidth context.

Generally speaking, if we can carefully plan and implement the division of contexts in the domain layer, constructing an operations research mathematical model library similar to a knowledge base, we can integrate based on these bounded contexts and quickly deliver the algorithm applications required by users. The process of constructing these library components is generally called domain engineering.

Components

OSPF adopts the form of internal Domain-Specific Language (DSL) for design and implementation. Except for some public components, the rest are implemented on the target host language.

Public Components

• examples: Examples, used to demonstrate how to use OSPF for modeling and solving.

• framework: Common components for development packages targeting specific problems, including result visualization tools.

• remote: Remote solver scheduler and server, used to run solvers on servers and obtain results through network interfaces.

Host Language Implementation Components

Each OSPF implementation includes the following components:

• utils: Toolset, containing classes and functions required to implement OSPF DSL.
• core: Core components, containing core functions such as modeling, solver interfaces, result processing, etc.
  • core-plugin-XXX: Solver plugins, used to implement solver interfaces for specific solvers.
  • core-plugin-heuristic: Meta-heuristic algorithm plugins, containing implementations of many common meta-heuristic algorithms.
• framework: Framework for specific problems, containing implementations of data processing, mathematical models, and solution algorithms for specific problems. All designs and implementations are non-intrusive. Users can either use them out-of-the-box or extend based on the framework, seamlessly integrating with other frameworks or components.
  • framework-plugin-XXX: Framework plugins, used to implement functions requiring middleware participation, such as data persistence, asynchronous message communication.
  • bpp1d: One-dimensional bin packing problem development package, containing implementations of data processing, mathematical models, and solution algorithms for many one-dimensional bin packing problems.
  • bpp2d: Two-dimensional bin packing problem development package, containing implementations of data processing, mathematical models, and solution algorithms for many two-dimensional bin packing problems.
  • bpp3d: Three-dimensional bin packing problem development package, containing implementations of data processing, mathematical models, and solution algorithms for many three-dimensional bin packing problems.
  • csp1d: One-dimensional cutting stock problem development package, containing implementations of data processing, mathematical models, and solution algorithms for many one-dimensional cutting stock problems.
  • csp2d: Two-dimensional cutting stock problem development package, containing implementations of data processing, mathematical models, and solution algorithms for many two-dimensional cutting stock problems.
  • gantt-scheduling: Gantt chart scheduling problem development package, containing implementations of data processing, mathematical models, and solution algorithms for many Gantt chart scheduling problems. Can be used for similar scheduling and planning problems like production scheduling (APS), batch production (LSP), etc.
  • network-scheduling: Network scheduling problem development package, containing implementations of data processing, mathematical models, and solution algorithms for many network scheduling problems. Can be used for similar scheduling and planning problems like vehicle routing (VRP), facility location (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	❌	❌	❌	❌	❌
CP	❌	❌	✔️	❌	✔️
Solver Interfaces
COPIN-OR	❗	❌	❗	❌	❗
COPT	❌	❌	✔️	❌	❌
CPLEX	❗	❌	✔️	❌	❗
GUROBI	❗	❌	✔️	❌	✔️
GUROBI-11+	❗	❌	✔️	❌	✔️
HEXALY	❗	❌	✔️	❌	❗
LINGO	❗	❌	❗	❌	❗
MINDOPT	❗	❌	✔️	❌	❗
MOSEK	❗	❌	✔️	❌	❗
OPTVERSE	❗	❌	❗	❌	❗
SCIP	❗	❌	✔️	❌	✔️
Others	Planned
Meta-Heuristic Algorithms
PSO	❗	❌	✔️	❌	✔️
GA	❗	❌	✔️	❌	✔️
MVO	❗	❌	✔️	❌	✔️
SAA	❗	❌	✔️	❌	✔️
HCA	❗	❌	❗	❌	❗
NMS	❗	❌	❗	❌	❗
Others	Planned

Framework

Feature	C++	C#	Kotlin	Python	Rust	Visualization
Basic Framework	❗	❌	✔️	❌	✔️
Algorithm Capabilities/Frameworks
IIS	❗	❌	✔️	❌	✔️
Column Generation	❗	❌	✔️	❌	✔️
Automatic Benders Decomposition (Linear)	❗	❌	✔️	❌	✔️
Automatic Benders Decomposition (Quadratic)	❗	❌	❗	❌	❗
Application Frameworks
1D Bin Packing	❌	❌	❌	❌	❌	❌
2D Bin Packing	❌	❌	❌	❌	❌	❌
3D Bin Packing	❌	❌	✔️	❌	✔️	✔️
1D Cutting Stock	❌	❌	✔️	❌	✔️	✔️
2D Cutting Stock	❌	❌	❌	❌	❌	❌
Gantt Scheduling	❌	❌	✔️	❌	✔️	✔️
Network Flow Scheduling	❌	❌	✔️	❌	✔️	❌
Others	Planned

Remote

Feature
Solver Server	✔️
Meta-Heuristic Algorithm Server	❌
Scheduler	✔️
Time Slice Round Robin	❌