LINEAR_PROG

Overview

The LINEAR_PROG function solves linear programming (LP) problems, which involve minimizing a linear objective function subject to linear equality and inequality constraints. Linear programming is one of the most widely used optimization techniques in operations research, economics, logistics, and engineering for resource allocation, production planning, and scheduling problems.

This implementation uses SciPy’s linprog function from the scipy.optimize module. The standard form of a linear programming problem is:

\begin{aligned}
\min_{x} \quad & c^T x \\
\text{subject to} \quad & A_{ub} x \leq b_{ub} \\
& A_{eq} x = b_{eq} \\
& l \leq x \leq u
\end{aligned}

where x is the vector of decision variables, c contains the objective function coefficients, A_{ub} and b_{ub} define inequality constraints, A_{eq} and b_{eq} define equality constraints, and l and u specify variable bounds.

The function supports multiple solver algorithms. The default highs method automatically selects between HiGHS dual simplex (highs-ds) and interior-point (highs-ipm) solvers—these are high-performance C++ implementations that are particularly efficient for large, sparse problems. Legacy methods including interior-point, revised simplex, and simplex (Dantzig’s original tableau method) are also available.

The simplex algorithm, introduced by George Dantzig in 1947, traverses vertices of the feasible polytope to find the optimal solution. Interior-point methods take a different approach, moving through the interior of the feasible region using techniques derived from barrier functions. For most practical applications, the HiGHS solvers provide the best performance and numerical stability.

The function returns the optimal values of decision variables along with the minimized objective function value. For more details on the underlying algorithms and parameters, see the SciPy linprog documentation and the HiGHS project.

This example function is provided as-is without any representation of accuracy.

Excel Usage

=LINEAR_PROG(c, A_ub, b_ub, A_eq, b_eq, bounds, linear_prog_method)

c (list[list], required): Objective function coefficients as a 2D list (row or column vector).
A_ub (list[list], optional, default: null): Coefficient matrix for inequality constraints (A_ub @ x <= b_ub).
b_ub (list[list], optional, default: null): Right-hand side vector for inequality constraints.
A_eq (list[list], optional, default: null): Coefficient matrix for equality constraints (A_eq @ x = b_eq).
b_eq (list[list], optional, default: null): Right-hand side vector for equality constraints.
bounds (list[list], optional, default: null): Variable bounds as [lower, upper] pairs per variable. Use null for unbounded.
linear_prog_method (str, optional, default: “highs”): Solver algorithm to use.

Returns (list[list]): 2D list [[x1, x2, …, objective]], or error message string.

Examples

Example 1: Maximization with inequality constraints and bounds

Inputs:

c		A_ub		b_ub	bounds		linear_prog_method
3	5	-1	-2	-8	0	100	highs-ipm
		-2	-1	-8	0	100

Excel formula:

=LINEAR_PROG({3,5}, {-1,-2;-2,-1}, {-8;-8}, {0,100;0,100}, "highs-ipm")

Expected output:

Result
2.666666666666667	2.6666666666666665	21.333333333333332

Example 2: Minimization with single inequality constraint

Inputs:

c		A_ub		b_ub
-1	-1	1	2	10

Excel formula:

=LINEAR_PROG({-1,-1}, {1,2}, 10)

Expected output:

Result
10	0	-10

Example 3: Single variable linear program

Inputs:

c	A_ub	b_ub
2	-1	-4

Excel formula:

=LINEAR_PROG(2, -1, -4)

Expected output:

Result
4	8

Example 4: Two independent inequality constraints

Inputs:

c		A_ub		b_ub
1	1	1	0	5
		0	1	3

Excel formula:

=LINEAR_PROG({1,1}, {1,0;0,1}, {5;3})

Expected output:

Result
0	0	0

Python Code

import numpy as np
from scipy.optimize import linprog as scipy_linprog

def linear_prog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, bounds=None, linear_prog_method='highs'):
    """
    Solve a linear programming problem using SciPy's `linprog` function.

    See: https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html

    This example function is provided as-is without any representation of accuracy.

    Args:
        c (list[list]): Objective function coefficients as a 2D list (row or column vector).
        A_ub (list[list], optional): Coefficient matrix for inequality constraints (A_ub @ x <= b_ub). Default is None.
        b_ub (list[list], optional): Right-hand side vector for inequality constraints. Default is None.
        A_eq (list[list], optional): Coefficient matrix for equality constraints (A_eq @ x = b_eq). Default is None.
        b_eq (list[list], optional): Right-hand side vector for equality constraints. Default is None.
        bounds (list[list], optional): Variable bounds as [lower, upper] pairs per variable. Use null for unbounded. Default is None.
        linear_prog_method (str, optional): Solver algorithm to use. Valid options: HiGHS, HiGHS Dual Simplex, HiGHS Interior Point, Interior Point, Revised Simplex, Simplex. Default is 'highs'.

    Returns:
        list[list]: 2D list [[x1, x2, ..., objective]], or error message string.
    """
    def to2d(x):
        return [[x]] if not isinstance(x, list) else x

    def conv(mat, name, cols=None):
        if mat is None:
            return None
        if not isinstance(mat, list) or len(mat) == 0:
            return f"Invalid input: {name} must be a 2D list with at least one row."
        out = []
        for ri, row in enumerate(mat):
            if not isinstance(row, list) or len(row) == 0:
                return f"Invalid input: each row in {name} must be a non-empty list."
            if cols is not None and len(row) != cols:
                return f"Invalid input: {name} must have {cols} columns to match the number of variables."
            r = []
            for ci, v in enumerate(row):
                try:
                    n = float(v)
                except Exception:
                    return f"Invalid input: {name} must be numeric. Problem at row {ri+1}, column {ci+1}."
                if not np.isfinite(n):
                    return f"Invalid input: {name} must contain finite values. Problem at row {ri+1}, column {ci+1}."
                r.append(n)
            out.append(r)
        return np.asarray(out, dtype=float)

    c = to2d(c)
    A_ub = to2d(A_ub) if A_ub is not None else None
    b_ub = to2d(b_ub) if b_ub is not None else None
    A_eq = to2d(A_eq) if A_eq is not None else None
    b_eq = to2d(b_eq) if b_eq is not None else None

    cv = conv(c, "c")
    if isinstance(cv, str):
        return cv
    c_vec = cv.flatten()
    if c_vec.size == 0:
        return "Invalid input: c must contain at least one coefficient."

    if A_ub is not None and b_ub is None:
        return "Invalid input: b_ub must be provided when A_ub is specified."
    if b_ub is not None and A_ub is None:
        return "Invalid input: A_ub must be provided when b_ub is specified."

    A_ub_m = conv(A_ub, "A_ub", cols=c_vec.size)
    if isinstance(A_ub_m, str):
        return A_ub_m
    if b_ub is not None:
        bv = conv(b_ub, "b_ub")
        if isinstance(bv, str):
            return bv
        if A_ub_m is not None and A_ub_m.shape[0] != bv.flatten().size:
            return "Invalid input: Number of rows in A_ub must equal the length of b_ub."
        b_ub_v = bv.flatten()
    else:
        b_ub_v = None

    if A_eq is not None and b_eq is None:
        return "Invalid input: b_eq must be provided when A_eq is specified."
    if b_eq is not None and A_eq is None:
        return "Invalid input: A_eq must be provided when b_eq is specified."

    A_eq_m = conv(A_eq, "A_eq", cols=c_vec.size)
    if isinstance(A_eq_m, str):
        return A_eq_m
    if b_eq is not None:
        bev = conv(b_eq, "b_eq")
        if isinstance(bev, str):
            return bev
        if A_eq_m is not None and A_eq_m.shape[0] != bev.flatten().size:
            return "Invalid input: Number of rows in A_eq must equal the length of b_eq."
        b_eq_v = bev.flatten()
    else:
        b_eq_v = None

    bounds_seq = None
    if bounds is not None:
        if not isinstance(bounds, list) or len(bounds) != c_vec.size:
            return "Invalid input: bounds must supply one [min, max] pair per variable."
        bb = []
        for i, p in enumerate(bounds):
            if not isinstance(p, list) or len(p) != 2:
                return "Invalid input: each bounds entry must be a [min, max] pair."
            lo = float(p[0]) if p[0] is not None else None
            hi = float(p[1]) if p[1] is not None else None
            if lo is not None and not np.isfinite(lo):
                return f"Invalid input: bounds lower value at index {i+1} must be finite or None."
            if hi is not None and not np.isfinite(hi):
                return f"Invalid input: bounds upper value at index {i+1} must be finite or None."
            if lo is not None and hi is not None and lo > hi:
                return f"Invalid input: lower bound must not exceed upper bound for variable {i+1}."
            bb.append((lo, hi))
        bounds_seq = tuple(bb)

    solver = linear_prog_method.lower() if isinstance(linear_prog_method, str) else "highs"
    valid = {"highs", "highs-ds", "highs-ipm", "interior-point", "revised simplex", "simplex"}
    if solver not in valid:
        return ("Invalid input: linear_prog_method must be one of 'highs', 'highs-ds', 'highs-ipm', "
                "'interior-point', 'revised simplex', or 'simplex'.")

    try:
        res = scipy_linprog(c=c_vec, A_ub=A_ub_m, b_ub=b_ub_v, A_eq=A_eq_m, b_eq=b_eq_v, bounds=bounds_seq, method=solver)
    except Exception as e:
        return f"linear_prog error: {e}"

    if not getattr(res, "success", False) or res.x is None:
        msg = getattr(res, "message", "Solver failed.")
        return f"linear_prog failed: {msg}"

    return [[float(x) for x in res.x] + [float(res.fun)]]

Overview

Excel Usage

Examples

Python Code

Online Calculator