User guide · 2.0 development

Building Large Problems Efficiently¶

Adding terms to a container one at a time, e.g., constraint.add(LinearTerm(...)) in a loop, reads well for a handful of terms but does not scale. add(LinearTerm(...)) merges the new term with an existing term of the same variable, and it finds that term by searching every term already in the container, so adding T terms one at a time costs on the order of T^2 operations. On a row with tens of thousands of terms that is the difference between a fraction of a second and minutes.

Every container therefore takes all of its contents at once, and a Python list is accepted wherever a container is:

Instead of	Use
`problem.addVariable(v)` in a loop	`problem.addVariables(list_of_variables)`
`problem.addConstraint(c)` in a loop	`problem.addConstraints(list_of_constraints)`
`problem.addConstraint(x <= 1, name)` in a loop	`problem.addConstraints(list_of_comparisons, list_of_names)`
`constraint.add(LinearTerm(c, v))` in a loop	`constraint.add(SHOTpy.LinearTerms(coefficients, variables))`
`constraint.add(QuadraticTerm(c, u, v))` in a loop	`constraint.add(SHOTpy.QuadraticTerms(coefficients, first, second))`

The bulk add merges the terms through a hash map in a single pass, so the result is exactly the same as adding them one at a time – only the cost differs. LinearTerms(coefficients, variables) is the cheapest form of all, since it builds the terms inside SHOT and never creates one Python object per term.

append is available on every container when the terms are not to be merged at all, and reserve takes the number of terms that will be added.

import time
import SHOTpy

N = 20000

def build(bulk):
    """Build one linear row and one quadratic row of N terms, returning the time it took."""
    solver = SHOTpy.Solver()
    problem = SHOTpy.Problem(solver)

    variables = [SHOTpy.Variable(f"x{i}", SHOTpy.VariableType.Real, 0.0, 10.0) for i in range(N)]
    coefficients = [1.0 + i for i in range(N)]

    # A list is accepted wherever a Variables container is
    problem.addVariables(variables)

    start = time.perf_counter()

    row = SHOTpy.LinearConstraint("row", 0.0, 1.0)
    quadraticRow = SHOTpy.QuadraticConstraint("qrow", -SHOTpy.SHOT_DBL_MAX, 1.0)

    if bulk:
        row.add(SHOTpy.LinearTerms(coefficients, variables))
        quadraticRow.add(SHOTpy.QuadraticTerms(coefficients, variables, variables))
    else:
        for c, v in zip(coefficients, variables):
            row.add(SHOTpy.LinearTerm(c, v))
        for c, v in zip(coefficients, variables):
            quadraticRow.add(SHOTpy.QuadraticTerm(c, v, v))

    elapsed = time.perf_counter() - start

    problem.addConstraints([row, quadraticRow])
    return elapsed, problem

singleTime, singleProblem = build(bulk=False)
bulkTime, bulkProblem = build(bulk=True)

print(f"one term at a time : {singleTime:7.3f} s")
print(f"all terms at once  : {bulkTime:7.3f} s  ({singleTime / bulkTime:.0f} times faster)")
print("the two problems are identical:", singleProblem.toString() == bulkProblem.toString())

The other ways of building a container¶

A container can also be built from a list of terms, extended with append, or handed a list directly: constraint.add([...]) converts the list and takes the whole of it in one bulk add. The terms themselves are ordinary objects, so they can be created however is convenient.

solver = SHOTpy.Solver()
problem = SHOTpy.Problem(solver)

x = SHOTpy.Variable("x", SHOTpy.VariableType.Real, 0.0, 10.0)
y = SHOTpy.Variable("y", SHOTpy.VariableType.Real, 0.0, 10.0)
problem.addVariables([x, y])

# From a list of terms
terms = SHOTpy.LinearTerms([SHOTpy.LinearTerm(2.0, x), SHOTpy.LinearTerm(3.0, y)])

# Or built up with append, which does not merge terms of the same variable
more = SHOTpy.LinearTerms()
more.reserve(2)
more.append(SHOTpy.LinearTerm(1.0, x))
more.append(SHOTpy.LinearTerm(1.0, y))

objective = SHOTpy.LinearObjectiveFunction(SHOTpy.ObjectiveDirection.Minimize)
objective.add(terms)
problem.setObjective(objective)

# A list passed straight to add is converted and added in one go
constraint = SHOTpy.LinearConstraint("c1", 1.0, SHOTpy.SHOT_DBL_MAX)
constraint.add([SHOTpy.LinearTerm(1.0, x), SHOTpy.LinearTerm(1.0, y)])
problem.addConstraints([constraint])

problem.finalize()
print(problem.toString())

Summary¶

This tutorial covered:

Basic setup - Creating a solver and a problem
Variables - Real, integer, and binary variables
Linear programming - LP formulation and solving
Mixed-integer programming - MIP problems
Quadratic programming - QP and QCQP problems
Nonlinear programming - Using exp, log, sin, cos, and other functions
File I/O - Reading problems from OSiL and GAMS files
Settings - Configuring solver parameters
Advanced features - Signomial terms, solution details, and problem properties
Callbacks - Reacting to solver events, early termination, and custom hyperplane injection
External bounds - Injecting dual bounds and primal solution candidates to accelerate convergence
ESH interior point callback - Injecting or modifying interior points for the ESH algorithm
ESH interior point via auxiliary problem - Finding a strictly interior point by minimising a slack variable μ
Building large problems efficiently - Adding all variables, constraints and terms at once instead of one at a time

Additional Resources¶

SHOT Documentation: https://shotsolver.dev
SHOT Repository: https://github.com/coin-or/SHOT
Test Files: See the test/python/ directory for more examples

Tips for Best Results¶

Follow the order: create the solver, change its settings, create the problem with SHOTpy.Problem(solver), add the variables, constraints and objective, call problem.finalize(), and then solver.setProblem(problem) and solver.solveProblem(). Nothing can be added to a problem after finalize()
Build anything but a toy model with the bulk forms, not a term at a time
Use appropriate variable bounds to help the solver
Configure MIP and NLP subsolvers based on problem characteristics
Adjust termination criteria (time limit, gap tolerances) as needed
Check the return values of setProblem() and solveProblem(), and getModelReturnStatus() and the bounds after solving