Integer Linear Programming
import numpy as np import pyomo.core as pyo def ilp(a: np.ndarray, b: np.ndarray, c: np.ndarray, bound: int) -> pyo.ConcreteModel: # model constraint: a*x <= b model = pyo.ConcreteModel() assert b.ndim == c.ndim == 1 num_vars = len(c) num_constraints = len(b) assert a.shape == (num_constraints, num_vars) model.x = pyo.Var( range(num_vars), domain=pyo.NonNegativeIntegers, bounds=(0, bound) ) @model.Constraint(range(num_constraints)) def monotone_rule(model, idx): return a[idx, :] @ model.x.values() <= b[idx] # model objective: max(c * x) model.cost = pyo.Objective(expr=c @ model.x.values(), sense=pyo.maximize) return model
This function generates a PYOMO model that formulates the Integer Linear Programming problem. The problem looks for integer assignment for vector x, such that Ax <= b and Cx is maximized. A is an integer matrix, and B and C are integer vectors.
- Integer variable declaration for each entry in the vector.
- Objective rule – inner product of C and x.
- Constraint – linear inequalities based on Ax <= b.