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.
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.66667 | 2.66667 | 21.3333 |
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
Show 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.
"""
try:
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"Error: {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"Error: each row in {name} must be a non-empty list."
if cols is not None and len(row) != cols:
return f"Error: {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"Error: {name} must be numeric. Problem at row {ri+1}, column {ci+1}."
if not np.isfinite(n):
return f"Error: {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 "Error: c must contain at least one coefficient."
if A_ub is not None and b_ub is None:
return "Error: b_ub must be provided when A_ub is specified."
if b_ub is not None and A_ub is None:
return "Error: 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 "Error: 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 "Error: b_eq must be provided when A_eq is specified."
if b_eq is not None and A_eq is None:
return "Error: 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 "Error: 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 "Error: 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 "Error: each bounds entry must be a [min, max] pair."
try:
lo = float(p[0]) if p[0] is not None else None
hi = float(p[1]) if p[1] is not None else None
except Exception:
return f"Error: bounds values at index {i+1} must be numeric or None."
if lo is not None and not np.isfinite(lo):
return f"Error: bounds lower value at index {i+1} must be finite or None."
if hi is not None and not np.isfinite(hi):
return f"Error: 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"Error: 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 ("Error: linear_prog_method must be one of 'highs', 'highs-ds', 'highs-ipm', "
"'interior-point', 'revised simplex', or 'simplex'.")
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)
if not getattr(res, "success", False) or res.x is None:
msg = getattr(res, "message", "Solver failed.")
return f"Error: {msg}"
return [[float(x) for x in res.x] + [float(res.fun)]]
except Exception as e:
return f"Error: {str(e)}"