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.