halfspace
is an open-source, light-weight Python module for modelling and solving mixed-integer convex optimization problems of the form:
where mip
module and uses a cutting plane algorithm to solve problems to provable optimality.
This implementation is based on the approach outlined in Chapter 6 of Boyd & Vandenberghe (2008).
Full API documentation can be found here.
You can install halfspace
using pip
as follows:
pip install halfspace-optimizer
The modelling syntax for halfspace
closely follows that of the mip
module. As an illustrative example, let's consider the toy problem:
This can be implemented as follows:
import numpy as np
from halfspace import Model
# Initialize model
model = Model()
# Define variables
x = model.add_var(lb=0, ub=1, name="x") # add a variable
y = model.add_var(var_type="B", name="y") # add a binary variable
z = model.add_var_tensor(shape=(5,), lb=0, ub=1, name="z") # add a tensor of variables
# Define objective terms (these are summed to create the objective)
model.add_objective_term(var=x, func=lambda x: (x - 1) ** 2) # add an objective term for one variable
model.add_objective_term(
var=[x, y],
func=lambda x, y: np.exp(0.2 * x + y),
) # add an objective term for multiple variables
model.add_objective_term(
var=z,
func=lambda z: -sum((i + 1) * z[i] for i in range(5)),
) # add an objective term for a tensor of variables
# Define constraints
model.add_linear_constr(model.sum(z) <= y) # add a linear constraint
model.add_nonlinear_constr(var=(x, y), func=lambda x, y: x ** 2 + y ** 2 - 1.25 ** 2) # add a nonlinear constraint
# Set initial query point (optional)
model.start = [(x, 0), (y, 0)] + [(z[i], 0) for i in range(5)]
# Solve model
status = model.optimize()
print(model.objective_value) # get the best objective value
print(model.var_value(x)) # get the value of a variable directly
print(model.var_value("y")) # get the value of a variable by name
Q: The solver is converging too slowly. What can I do to improve this?
A: Here are few tips to improve solve times:
- Improve the initial query point using problem-specific knowledge. In general, the closer the initial query point is to the optimal solution, the fewer iterations should be required for convergence.
- Tune the
smoothing
parameter, which affects query point updates. For some problems, increasing this parameter can dampen query point oscillation, thereby improving convergence. However, if this parameter is set too high, this can also slow down convergence as the updates become too conservative. Consequently, it may be necessary to experiment with a range of values. - If a feasible solution is 'good enough' for your application, specify the
max_iters_no_improvement
argument when you call theoptimize
method to prevent wasting time closing the optimality gap. - Review if any integrality constraints can be relaxed.
Q: The solution to my problem that the solver has output seems wrong. What are some common mistakes that could cause this?
A: The cutting plane algorithm only works for convex programs and mixed-integer convex programs. Double-check that the formulation of your problem is indeed convex. Otherwise, if you're computing the gradients analytically, also double-check that the formula is correct. If you believe erroneous behaviour is instead caused by a bug, please submit an issue.
Q: How can I view the solver logs in real time?
Prior to calling model.optimize()
, change the logging leve as follows:
import logging
logging.getLogger().setLevel(logging.INFO)
The logging frequency can be adjusted as desiredusing the model's log_freq
attribute.
Clone the repository using git
:
git clone https://github.com/joshivanhoe/halfspace
Create a fresh virtual environment using venv
or conda
.
Activate the environment and navigate to the cloned halfspace
directory.
Install a locally editable version of the package using pip
:
pip install -e .
To check the installation has worked, you can run the tests (with coverage metrics) using pytest
as follows:
pytest --cov=halfspace tests/
Contributions are welcome! To see our development priorities, refer to the open issues. Please submit a pull request with a clear description of the changes you've made.