Skip to main content

Project generated with PyScaffold Documentation Status codecov

👁️ ellalgo

Ellipsoid Method in Python

The Ellipsoid Method as a linear programming algorithm was first introduced by L. G. Khachiyan in 1979. It is a polynomial-time algorithm that uses ellipsoids to iteratively reduce the feasible region of a linear program until an optimal solution is found. The method works by starting with an initial ellipsoid that contains the feasible region, and then successively shrinking the ellipsoid until it contains the optimal solution. The algorithm is guaranteed to converge to an optimal solution in a finite number of steps.

The method has a wide range of practical applications in operations research. It can be used to solve linear programming problems, as well as more general convex optimization problems. The method has been applied to a variety of fields, including economics, engineering, and computer science. Some specific applications of the Ellipsoid Method include portfolio optimization, network flow problems, and the design of control systems. The method has also been used to solve problems in combinatorial optimization, such as the traveling salesman problem.

What is Parallel Cut?

In the context of the Ellipsoid Method, a parallel cut refers to a pair of linear constraints of the form aTx <= b and -aTx <= -b, where a is a vector of coefficients and b is a scalar constant. These constraints are said to be parallel because they have the same normal vector a, but opposite signs. When a parallel cut is encountered during the Ellipsoid Method, both constraints can be used simultaneously to generate a new ellipsoid. This can improve the convergence rate of the method, especially for problems with many parallel constraints.

Known limitations

  • No sparsity exploitation. The method treats the problem data as dense, so it cannot take advantage of sparse constraint matrices the way tuned interior-point/LP solvers do.
  • Iteration budget grows ~O(n²). As dimensionality grows, interior-point methods (e.g. CVXPY/CLARABEL) usually scale better than the ellipsoid method.
  • Interpreted per-iteration overhead. Each iteration runs in Python, so pure-Python overhead can reverse the ranking against compiled code, especially on small problems.
  • Positive definiteness can be lost silently. The direct Ell representation may lose positive definiteness; mitigate with Options(check_pd=True) or use EllStable.
  • Stopping threshold. An absolute stopping threshold should be paired with the stall guard (enabled by default via Options(stall_guard=True)) so the loop stops with SolverStatus.Stalled at floating-point resolution instead of spinning to max_iters.
  • Oracle correctness. Custom oracles must be verified (see ellalgo.oracle_checks: check_cut_valid, check_subgradient, check_lmi_witness).
  • Approximate oracles. Affine-arithmetic and difference-of-convex oracles carry inherent approximation error/bias.
  • Discrete/quantized design. Discretizing the design space carries sampling-grid artifacts.

EllStable is preferred in compiled code, while Ell is preferred for pure-Python prototyping.

Used by

See also

👉 Note

This project has been set up using PyScaffold 4.5. For details and usage information on PyScaffold see https://pyscaffold.org/.

Metadata

Release files for ellalgo 0.10

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for ellalgo 0.10
File Size Uploaded Provenance Actions
ellalgo-0.10.tar.gz 369.8 kB With provenance Details for ellalgo-0.10.tar.gz

Built distribution (wheel)

Table of built distributions (wheels) for ellalgo 0.10
File Interpreter ABI Platform Actions
ellalgo-0.10-py3-none-any.whl Python 3 none any Details for ellalgo-0.10-py3-none-any.whl

Total release size: 426.3 kB

Release files / ellalgo-0.10.tar.gz

Download URL ellalgo-0.10.tar.gz
Size 369.8 kB
Tags Source
SHA-256 checksum
How to use checksums
7669c267837c6615ac8baa144fe9b9a265b4e3e85c58552e999f611839bf2dfc
BLAKE2b-256 checksum
How to use checksums
386b418e3632c27e560007bb30ea06f51949d03b676490b74bd42b5e5e2e8a79
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
Yes
Uploaded via twine/7.0.0 CPython/3.13.16

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

PyPI Publish Attestation

PyPI verified that this artifact, at this checksum, originated from the publisher listed below.

Signed by GitHub Actions, verified by PyPI on Nov 20, 2026.

Transparency log

Release files / ellalgo-0.10-py3-none-any.whl

Download URL ellalgo-0.10-py3-none-any.whl
Size 56.5 kB
Tags Python 3
SHA-256 checksum
How to use checksums
3ddf115d6c64a73459f96547f8fe0741f9f9224d13e42ce2eb8863d469e959a7
BLAKE2b-256 checksum
How to use checksums
f782ba4cda8f81a93a4be53ff26f2fbdc987681cdbfd46986822e88f066376b4
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
Yes
Uploaded via twine/7.0.0 CPython/3.13.16

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

PyPI Publish Attestation

PyPI verified that this artifact, at this checksum, originated from the publisher listed below.

Signed by GitHub Actions, verified by PyPI on Nov 20, 2026.

Transparency log

Security for ellalgo 0.10

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

Full provenance

Both files in this release have been uploaded with provenance metadata.

Select from 2 files

Attestation for ellalgo-0.10.tar.gz

PyPI Publish Attestation

PyPI verified that this artifact, at this checksum, originated from the publisher listed below.

Signed by GitHub Actions, verified by PyPI on Nov 20, 2026.

Transparency log

A note on package security

PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.

To learn more about protecting yourself from malicious actors, visit our package security documentation.

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page