Skip to main content

Cardinality constrained Solver

Project description

Cardinality Constrained Quadratic Optimization Solver (cardsol)

cardsol is a small package for solving mathematical optimization problems of convex Cardinality Constrained Quadratic Optimization (CCQP) problems.

cardsol translates the CCQP problem into a Mixed-Integer Optimization Problem (MIQP) provides the following algorithms to solve it:

  1. Outer Approximation (OA) method
  2. LP/NLP based Branch and Bound method

Dependencies

  1. Scipy
  2. Numpy
  3. Gurobipy and gurobi solver

Install

pip install cardsol

Example: Random convex CCQP

Imports

from numpy.random import randn, rand
from numpy import eye
from time import time
from cardsol.problem.constraints import LinearConstraint
from cardsol.problem.functions import QuadraticForm
from cardsol.problem.model import QPModel
from cardsol.problem.objective import QPObjective
from cardsol.problem.variables import Variable
from cardsol.solver.outer_lpnlp.solver import CCQPSolver, LPNLPCCQPSolver

Define problem Data

n = ...     # number of variables
k = int(n / 2) # level of cardinality
m = 1
maxiter = 100

Q = rand(n, n) 
Q = Q + Q.T
Q = Q.T @ Q     # Hessian Matrix
c = randn(n, 1) # gradient vector   

Define the model

x = Variable(shape = (n, 1), name = "x")

obj_func = QuadraticForm(Q, c, x)

objective = QPObjective(obj_func, sense = "minimize")

constr = LinearConstraint()

model = QPModel(objective, constr)

Instantiate Solvers

multiple_tree = CCQPSolver(model)

single_tree = LPNLPCCQPSolver(model)

Solve the model

start_single = time()
obj_2 = single_tree.solve(k, m)
end_single = time() - start_single

start_multiple = time()
_, obj_1 = multiple_tree.solve(k, m, 100)
end_multiple = time() - start_multiple

Creating Docker Image

sudo docker build .

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

cardsol-0.1.2.tar.gz (6.9 kB view details)

Uploaded Source

Built Distribution

cardsol-0.1.2-py3-none-any.whl (10.2 kB view details)

Uploaded Python 3

File details

Details for the file cardsol-0.1.2.tar.gz.

File metadata

  • Download URL: cardsol-0.1.2.tar.gz
  • Upload date:
  • Size: 6.9 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.4.2 importlib_metadata/4.7.0 pkginfo/1.7.1 requests/2.26.0 requests-toolbelt/0.9.1 tqdm/4.62.2 CPython/3.8.10

File hashes

Hashes for cardsol-0.1.2.tar.gz
Algorithm Hash digest
SHA256 a4c2543f5e97aaecebb4140d96b64d16008e4ba88ed4c5208bae3db87469cd3a
MD5 d0d94545c33bb913707fa1f8da90ff91
BLAKE2b-256 1d98769991df717d7ea14052dc4cefd5b12cb475152c85516e1f2ccf1b99804b

See more details on using hashes here.

File details

Details for the file cardsol-0.1.2-py3-none-any.whl.

File metadata

  • Download URL: cardsol-0.1.2-py3-none-any.whl
  • Upload date:
  • Size: 10.2 kB
  • Tags: Python 3
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.4.2 importlib_metadata/4.7.0 pkginfo/1.7.1 requests/2.26.0 requests-toolbelt/0.9.1 tqdm/4.62.2 CPython/3.8.10

File hashes

Hashes for cardsol-0.1.2-py3-none-any.whl
Algorithm Hash digest
SHA256 b712eb8dbabbceacdfe4c05c669bd165821da54ba0277dc769de238aa8c95d1d
MD5 8e6259155a000a75d24b337ff546d8ae
BLAKE2b-256 ab5011f3f672438520079abd99626a42c6c9b754d198beb5170a73f5054e622f

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page