C package that solves convex cone problems via operator splitting

Overview

SCS

Build Status Build status

SCS (splitting conic solver) is a numerical optimization package for solving large-scale convex cone problems, based on our paper Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding. It is written in C and can be used in other C, C++, Python, Matlab, R, Julia, and Ruby, programs via the linked interfaces. It can also be called as a solver from convex optimization toolboxes CVX (3.0 or later), CVXPY, Convex.jl, and Yalmip.

The current version is 2.1.2. If you wish to cite SCS, please use the following:

@article{ocpb:16,
    author       = {B. O'Donoghue and E. Chu and N. Parikh and S. Boyd},
    title        = {Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding},
    journal      = {Journal of Optimization Theory and Applications},
    month        = {June},
    year         = {2016},
    volume       = {169},
    number       = {3},
    pages        = {1042-1068},
    url          = {http://stanford.edu/~boyd/papers/scs.html},
}
@misc{scs,
    author       = {B. O'Donoghue and E. Chu and N. Parikh and S. Boyd},
    title        = {{SCS}: Splitting Conic Solver, version 2.1.2},
    howpublished = {\url{https://github.com/cvxgrp/scs}},
    month        = nov,
    year         = 2019
}

SCS numerically solves convex cone programs using the alternating direction method of multipliers (ADMM). It returns solutions to both the primal and dual problems if the problem is feasible, or a certificate of infeasibility otherwise. It solves the following primal cone problem:

minimize        c'x
subject to      Ax + s = b
                s in K

over variables x and s, where A, b and c are user-supplied data and K is a user-defined convex cone. The dual problem is given by

maximize        -b'y
subject to      -A'y == c
                y in K^*

over variable y, where K^* denotes the dual cone to K.

The cone K can be any Cartesian product of the following primitive cones:

  • zero cone {x | x = 0 } (dual to the free cone {x | x in R})
  • positive orthant {x | x >= 0}
  • second-order cone {(t,x) | ||x||_2 <= t}
  • positive semidefinite cone { X | min(eig(X)) >= 0, X = X^T }
  • exponential cone {(x,y,z) | y e^(x/y) <= z, y>0 }
  • dual exponential cone {(u,v,w) | −u e^(v/u) <= e w, u<0}
  • power cone {(x,y,z) | x^a * y^(1-a) >= |z|, x>=0, y>=0}
  • dual power cone {(u,v,w) | (u/a)^a * (v/(1-a))^(1-a) >= |w|, u>=0, v>=0}

The rows of the data matrix A correspond to the cones in K. The rows of A must be in the order of the cones given above, i.e., first come the rows that correspond to the zero/free cones, then those that correspond to the positive orthants, then SOCs, etc. For a k dimensional semidefinite cone when interpreting the rows of the data matrix A SCS assumes that the k x k matrix variable has been vectorized by scaling the off-diagonal entries by sqrt(2) and stacking the lower triangular elements column-wise to create a vector of length k(k+1)/2. See the section on semidefinite programming below.

At termination SCS returns solution (x*, s*, y*) if the problem is feasible, or a certificate of infeasibility otherwise. See here for more details about cone programming and certificates of infeasibility.

Anderson Acceleration

By default SCS uses Anderson acceleration (AA) to speed up convergence. The number of iterates that SCS uses in the AA calculation can be controlled by the parameter acceleration_lookback in the settings struct. It defaults to 10. AA is available as a standalone package here. More details are available in our paper on AA here.

Semidefinite Programming

SCS assumes that the matrix variables and the input data corresponding to semidefinite cones have been vectorized by scaling the off-diagonal entries by sqrt(2) and stacking the lower triangular elements column-wise. For a k x k matrix variable (or data matrix) this operation would create a vector of length k(k+1)/2. Scaling by sqrt(2) is required to preserve the inner-product.

To recover the matrix solution this operation must be inverted on the components of the vector returned by SCS corresponding to semidefinite cones. That is, the off-diagonal entries must be scaled by 1/sqrt(2) and the upper triangular entries are filled in by copying the values of lower triangular entries.

More explicitly, we want to express Tr(C X) as vec(C)'*vec(X), where the vec operation takes the k x k matrix

X = [ X11 X12 ... X1k
      X21 X22 ... X2k
      ...
      Xk1 Xk2 ... Xkk ]

and produces a vector consisting of

vec(X) = (X11, sqrt(2)*X21, ..., sqrt(2)*Xk1, X22, sqrt(2)*X32, ..., Xkk).

Linear equation solvers

Each iteration of SCS requires the solution of a set of linear equations. This package includes two implementations for solving linear equations: a direct solver which uses a cached LDL factorization and an indirect solver based on conjugate gradients. The indirect solver can be run on either the cpu or gpu.

The direct solver uses external numerical linear algebra packages:

Using SCS in C

Typing make at the command line will compile the code and create SCS libraries in the out folder. To run the tests execute:

make
make test
test/run_tests

If make completes successfully, it will produce two static library files, libscsdir.a, libscsindir.a, and two dynamic library files libscsdir.ext, libscsindir.ext (where .ext extension is platform dependent) in the same folder. It will also produce two demo binaries in the out folder named demo_socp_direct, and demo_socp_indirect. If you have a GPU and have CUDA installed, you can also execute make gpu to compile SCS to run on the GPU which will create additional libraries and demo binaries in the out folder corresponding to the gpu version. Note that the GPU version requires 32 bit ints, which can be enforced by compiling with DLONG=0.

To use the libraries in your own source code, compile your code with the linker option -L(PATH_TO_SCS_LIBS) and -lscsdir or -lscsindir (as needed). The API and required data structures are defined in the file include/scs.h. The four main API functions are:

  • ScsWork * scs_init(const ScsData * d, const ScsCone * k, ScsInfo * info);

    This initializes the ScsWork struct containing the workspace that scs will use, and performs the necessary preprocessing (e.g. matrix factorization). All inputs d, k, and info must be memory allocated before calling.

  • scs_int scs_solve(ScsWork * w, const ScsData * d, const ScsCone * k, ScsSolution * sol, ScsInfo * info);

    This solves the problem as defined by ScsData d and ScsCone k using the workspace in w. The solution is returned in sol and information about the solve is returned in info (outputs must have memory allocated before calling). None of the inputs can be NULL. You can call scs_solve many times for one call to scs_init, so long as the matrix A does not change (vectors b and c can change).

  • void scs_finish(ScsWork * w);

    Called after all solves completed to free allocated memory and other cleanup.

  • scs_int scs(const ScsData * d, const ScsCone * k, ScsSolution * sol, ScsInfo * info);

    Convenience method that simply calls all the above routines in order, for cases where the workspace does not need to be reused. All inputs must have memory allocated before this call.

The data matrix A is specified in column-compressed format and the vectors b and c are specified as dense arrays. The solutions x (primal), s (slack), and y (dual) are returned as dense arrays. Cones are specified as the struct defined in include/scs.h, the rows of A must correspond to the cones in the exact order as specified by the cone struct (i.e. put linear cones before second-order cones etc.).

Warm-start

You can warm-start SCS (supply a guess of the solution) by setting warm_start in the ScsData struct to 1 and supplying the warm-starts in the ScsSolution struct (x,y, and s). All inputs must be warm-started if any one is. These are used to initialize the iterates in scs_solve.

Re-using matrix factorization

If using the direct version you can factorize the matrix once and solve many times. Simply call scs_init once, and use scs_solve many times with the same workspace, changing the input data b and c (and optionally warm-starts) for each iteration.

Using your own linear system solver

To use your own linear system solver simply implement all the methods and the two structs in include/linsys.h and plug it in.

BLAS / LAPACK install error

If you get an error like cannot find -lblas or cannot find -llapack, then you need to install blas and lapack and / or update your environment variables to point to the install locations.

Comments
  • pip installer not working on Ubuntu

    pip installer not working on Ubuntu

    I tried the pip installer on an Ubuntu machine, and it needed a fortran compiler. Is that supposed to be the case? Even with a fortran compiler, the installation failed. Here's the error log:

    ATLAS version 3.8.4 built by ilan on Mon Jul 9 23:32:04 CDT 2012: UNAME : Linux centos5x86 2.6.18-308.el5 #1 SMP Tue Feb 21 20:06:06 EST 2012 x86_64 x86_64 x86_64 GNU/Linux INSTFLG : -1 0 -a 1 ARCHDEFS : -DATL_OS_Linux -DATL_ARCH_Corei1 -DATL_CPUMHZ=3296 -DATL_SSE3 -DATL_SSE2 -DATL_SSE1 -DATL_USE64BITS -DATL_GAS_x8664 F2CDEFS : -DAdd_ -DF77_INTEGER=int -DStringSunStyle CACHEEDGE: 524288 F77 : gfortran, version GNU Fortran (GCC) 4.1.2 20080704 (Red Hat 4.1.2-52) F77FLAGS : -O -fPIC -m64 SMC : gcc, version gcc (GCC) 4.1.2 20080704 (Red Hat 4.1.2-52) SMCFLAGS : -fomit-frame-pointer -mfpmath=sse -msse3 -O2 -fno-schedule-insns2 -fPIC -m64 SKC : gcc, version gcc (GCC) 4.1.2 20080704 (Red Hat 4.1.2-52) SKCFLAGS : -fomit-frame-pointer -mfpmath=sse -msse3 -O2 -fno-schedule-insns2 -fPIC -m64 In file included from /home/travis/anaconda/include/python2.7/Python.h:8:0, from include/glbopts.h:12, from linsys/direct/external/SuiteSparse_config.h:45, from linsys/direct/external/amd.h:46, from linsys/direct/external/amd_internal.h:168, from linsys/direct/external/amd_dump.c:16: /home/travis/anaconda/include/python2.7/pyconfig.h:1179:0: warning: "_POSIX_C_SOURCE" redefined [enabled by default] /usr/include/features.h:215:0: note: this is the location of the previous definition In file included from /home/travis/anaconda/lib/python2.7/site-packages/numpy/core/include/numpy/ndarraytypes.h:1728:0, from /home/travis/anaconda/lib/python2.7/site-packages/numpy/core/include/numpy/ndarrayobject.h:17, from /home/travis/anaconda/lib/python2.7/site-packages/numpy/core/include/numpy/arrayobject.h:15, from scsmodule.c:6: /home/travis/anaconda/lib/python2.7/site-packages/numpy/core/include/numpy/npy_deprecated_api.h:11:2: warning: #warning "Using deprecated NumPy API, disable it by #defining NPY_NO_DEPRECATED_API NPY_1_7_API_VERSION" [-Wcpp] In file included from /home/travis/anaconda/include/python2.7/Python.h:8:0, from include/glbopts.h:12, from linsys/direct/external/SuiteSparse_config.h:45, from linsys/direct/external/amd.h:46, from linsys/direct/external/amd_internal.h:168, from linsys/direct/external/amd_aat.c:18: /home/travis/anaconda/include/python2.7/pyconfig.h:1179:0: warning: "_POSIX_C_SOURCE" redefined [enabled by default] /usr/include/features.h:215:0: note: this is the location of the previous definition In file included from /home/travis/anaconda/include/python2.7/Python.h:8:0, from include/glbopts.h:12, from linsys/direct/external/SuiteSparse_config.h:45, from linsys/direct/external/amd.h:46, from linsys/direct/external/amd_internal.h:168, from linsys/direct/external/amd_preprocess.c:19: /home/travis/anaconda/include/python2.7/pyconfig.h:1179:0: warning: "_POSIX_C_SOURCE" redefined [enabled by default] /usr/include/features.h:215:0: note: this is the location of the previous definition In file included from /home/travis/anaconda/include/python2.7/Python.h:8:0, from include/glbopts.h:12, from linsys/direct/external/SuiteSparse_config.h:45, from linsys/direct/external/amd.h:46, from linsys/direct/external/amd_internal.h:168, from linsys/direct/external/amd_post_tree.c:13: /home/travis/anaconda/include/python2.7/pyconfig.h:1179:0: warning: "_POSIX_C_SOURCE" redefined [enabled by default] /usr/include/features.h:215:0: note: this is the location of the previous definition In file included from /home/travis/anaconda/include/python2.7/Python.h:8:0, from include/glbopts.h:12, from linsys/direct/external/amd_global.c:12: /home/travis/anaconda/include/python2.7/pyconfig.h:1179:0: warning: "_POSIX_C_SOURCE" redefined [enabled by default] /usr/include/features.h:215:0: note: this is the location of the previous definition linsys/direct/external/amd_global.c:76:41: warning: initialization from incompatible pointer type [enabled by default] In file included from /home/travis/anaconda/include/python2.7/Python.h:8:0, from include/glbopts.h:12, from linsys/direct/external/SuiteSparse_config.h:45, from linsys/direct/external/amd.h:46, from linsys/direct/external/amd_internal.h:168, from linsys/direct/external/amd_info.c:15: /home/travis/anaconda/include/python2.7/pyconfig.h:1179:0: warning: "_POSIX_C_SOURCE" redefined [enabled by default] /usr/include/features.h:215:0: note: this is the location of the previous definition In file included from /home/travis/anaconda/include/python2.7/Python.h:8:0, from include/glbopts.h:12, from linsys/direct/external/SuiteSparse_config.h:45, from linsys/direct/external/amd.h:46, from linsys/direct/external/amd_internal.h:168, from linsys/direct/external/amd_control.c:16: /home/travis/anaconda/include/python2.7/pyconfig.h:1179:0: warning: "_POSIX_C_SOURCE" redefined [enabled by default] /usr/include/features.h:215:0: note: this is the location of the previous definition In file included from /home/travis/anaconda/include/python2.7/Python.h:8:0, from include/glbopts.h:12, from linsys/direct/external/SuiteSparse_config.h:45, from linsys/direct/external/amd.h:46, from linsys/direct/external/amd_internal.h:168, from linsys/direct/external/amd_1.c:27: /home/travis/anaconda/include/python2.7/pyconfig.h:1179:0: warning: "_POSIX_C_SOURCE" redefined [enabled by default] /usr/include/features.h:215:0: note: this is the location of the previous definition In file included from /home/travis/anaconda/include/python2.7/Python.h:8:0, from include/glbopts.h:12, from linsys/direct/external/SuiteSparse_config.h:45, from linsys/direct/external/amd.h:46, from linsys/direct/external/amd_internal.h:168, from linsys/direct/external/amd_postorder.c:13: /home/travis/anaconda/include/python2.7/pyconfig.h:1179:0: warning: "_POSIX_C_SOURCE" redefined [enabled by default] /usr/include/features.h:215:0: note: this is the location of the previous definition In file included from /home/travis/anaconda/include/python2.7/Python.h:8:0, from include/glbopts.h:12, from linsys/direct/external/SuiteSparse_config.h:45, from linsys/direct/external/amd.h:46, from linsys/direct/external/amd_internal.h:168, from linsys/direct/external/amd_valid.c:36: /home/travis/anaconda/include/python2.7/pyconfig.h:1179:0: warning: "_POSIX_C_SOURCE" redefined [enabled by default] /usr/include/features.h:215:0: note: this is the location of the previous definition In file included from /home/travis/anaconda/include/python2.7/Python.h:8:0, from include/glbopts.h:12, from linsys/direct/external/SuiteSparse_config.h:45, from linsys/direct/external/amd.h:46, from linsys/direct/external/amd_internal.h:168, from linsys/direct/external/amd_2.c:16: /home/travis/anaconda/include/python2.7/pyconfig.h:1179:0: warning: "_POSIX_C_SOURCE" redefined [enabled by default] /usr/include/features.h:215:0: note: this is the location of the previous definition In file included from /home/travis/anaconda/include/python2.7/Python.h:8:0, from include/glbopts.h:12, from linsys/direct/external/SuiteSparse_config.h:45, from linsys/direct/external/amd.h:46, from linsys/direct/external/amd_internal.h:168, from linsys/direct/external/amd_order.c:15: /home/travis/anaconda/include/python2.7/pyconfig.h:1179:0: warning: "_POSIX_C_SOURCE" redefined [enabled by default] /usr/include/features.h:215:0: note: this is the location of the previous definition In file included from /home/travis/anaconda/include/python2.7/Python.h:8:0, from include/glbopts.h:12, from linsys/direct/external/SuiteSparse_config.h:45, from linsys/direct/external/amd.h:46, from linsys/direct/external/amd_internal.h:168, from linsys/direct/external/amd_defaults.c:15: /home/travis/anaconda/include/python2.7/pyconfig.h:1179:0: warning: "_POSIX_C_SOURCE" redefined [enabled by default] /usr/include/features.h:215:0: note: this is the location of the previous definition In file included from /home/travis/anaconda/lib/python2.7/site-packages/numpy/core/include/numpy/ndarraytypes.h:1728:0, from /home/travis/anaconda/lib/python2.7/site-packages/numpy/core/include/numpy/ndarrayobject.h:17, from /home/travis/anaconda/lib/python2.7/site-packages/numpy/core/include/numpy/arrayobject.h:15, from scsmodule.c:6: /home/travis/anaconda/lib/python2.7/site-packages/numpy/core/include/numpy/npy_deprecated_api.h:11:2: warning: #warning "Using deprecated NumPy API, disable it by #defining NPY_NO_DEPRECATED_API NPY_1_7_API_VERSION" [-Wcpp]

    opened by SteveDiamond 42
  • scs windows 32-bit and 64 -bit installation

    scs windows 32-bit and 64 -bit installation

    Hello.

    I have been using cvx for almost 4 months, and I wanted to add the scs to the cvx solver list. I downdloaded the whole zip file of scs and copied the unzipped file into the cvx directory. I then copied cvx_scs into cvx shim folder and I ran the cvx_install_scs. I get the following error: Error using mex (line 206) Unable to complete successfully. Error in compile_direct (line 24) eval(cmd); Error in make_scs (line 10) compile_direct(flags); Error in cvx_install_scs (line 2) make_scs

    Please help

    opened by bolcah 25
  • set eps not working for SCS

    set eps not working for SCS

    Hi, I am experimenting with SCS. A couple issues occured to me last few days:

    1). Since the default eps for SCS is only 1e-3, I tried to set eps = 1e-6 and also set verbose = True. But when the job was finished, the output shows that the eps is still 1e-3!

    2). I have a constraints [x >= 1e-8], where x is the cvx variables.of dimension 79x1 and I tried to solve cvx.sum_entries(cvx.square(A*x - b)), where A is a 100,000x79 matrix, and b is 100,000x1 matrix. But in the final results, I see lot components of x have values of around -1e-3, or even -1e-2! So many negative coeffs!

    Jimmy

    opened by jimmyyu0 23
  • scs, windows 8 and anaconda

    scs, windows 8 and anaconda

    This might not be bug in scs but a problem due to using prebuilt blas and lapack libraries. I am using windows 8.1 and anaconda. I downloaded the prebuilt 64bit libs and dlls for blas and lapack from http://icl.cs.utk.edu/lapack-for-windows/lapack/#libraries_mingw. I modified the site.cfg in C:\Anaconda\Lib\site-packages\numpy\distutils accordingly and called python setup.py install to build scs. Everything seemed fine. Then I copied the libblas.dll and liblapack.dll into C:\Anaconda\DLLs directory. When I call import scs, it doesn't give me any error however when I tried to use it like

    import numpy as np import cvxpy as cp kD=3 vS=cp.semidefinite(kD) pS=cp.Parameter(kD,kD) obj=cp.norm(vS-pS) prob=cp.Problem(cp.Minimize(obj)) pS.value=np.identity(kD) prob.solve(verbose=True,solver=cp.SCS)

    ipython crashes. As far as I can see it is actually the scs that crashes. I guess it has something to do with the prebuilt lib and dll files that makes scs crash. Do you know what is the cause of the problem and how can I fix it ?

    Regards, Caglar

    opened by ncroc 23
  • Symmetricity of SDP

    Symmetricity of SDP

    Unless we(SCS.jl) are doing something wrong, it seems possible that SCS can return semi-definite matrices that are not symmetric.

    using Convex, SCS
    set_default_solver(SCSSolver())
    
    y = Variable((2, 2), :Semidefinite)
    p = minimize(y[1, 1], y[1, 2] == 1)
    solve!(p)
    y.value
       0           1.0    
     -1.0         0.58682
    

    Is there a reason why it is possible for SDP matrices to not be symmetric? The README seems to say positive semidefinite cone { X | min(eig(X)) >= 0, X = X^T } in which case the matrix should be symmetric.

    Here is the data in raw format:

    A = [
     0.0 0.0 1.0 0.0;
     -1.0 0.0 0.0 0.0;
     0.0 -1.0 0.0 0.0;
     0.0 0.0 -1.0 0.0;
     0.0 0.0 0.0 -1.0]
    c = [1.0,0.0,0.0,0.0]
    b = [1.0,0.0,0.0,0.0,0.0]
    f = 1
    s = [2]
    ssize = 1
    
    opened by karanveerm 21
  • a bug in SCS when i solving SOCP problems

    a bug in SCS when i solving SOCP problems

    HI: I find a problem when i using scs to solve a SOCP problems. I use scs with cxvpy and solve use: "solver=cp.SCS", (SCS version:2,1,1) some of my code: w = cp.Variable(n) constraints = [w >= 0.0, w <= 1.0] constraints.append(1. == cp.sum(w, keepdims=False)) constraints.append(w - w_max <= 0) # all member of w_max is less than 1.0 constraints.append(w - w_min >= 0) and i add some other SOC constraints。 but the solution dones't satisfied my constraints and the status of result is "optimal_inaccurate". I tried to set max_iters=1e6, but it not works. but it was right solved when i set: solver=cp.MOSEK. and when i remove the constraints of " w <= 1.0", the solution of scs is right. I am confused,because all member of w_max is less than 1.0。why it's not solved when i add as constraints of " w <= 1.0"。

    opened by Cra2yM1nd 18
  • SCS taking hours to set up

    SCS taking hours to set up

    I have a an optimization program with 11M data points taking over 20hours to run the first iteration. smaller datasets with 7M data points run in significantly shorter time. Is there anyway I could investigate why it takes such long time?

    Following is the problem statement printed by SCS:

    Lin-sys: sparse-direct, nnz in A = 326795355 eps = 1.00e-03, alpha = 1.50, max_iters = 200, normalize = 1, scale = 1.00 Variables n = 53115585, constraints m = 117868881 Cones: primal zero / dual free vars: 1 linear vars: 39616055 exp vars: 78252825, dual exp vars: 0

    opened by btabibian 17
  • Windows 64-bit compile failure

    Windows 64-bit compile failure

    Sorry if I am submitting this a second time (I touched a button and issue seemed to go away). CVX installation script fails to complete on my windows 64-bit windows machine using MATLAB recommended SDK version 7 compiler. One hypothesis this compiler requires strict C89 ANSI standard. Similar problem was recently fixed in the PDOS distribution. Any ideas or help would be greatly appreciated.

    opened by mountcastle-zz 17
  • SCS with GPU support

    SCS with GPU support

    I noticed there is a GPU support for SCS now in master. I tried it but failed to install.

    After running make purge && make && make gpu and compiling gpu component I run setup.py with GPU=True. However, I get following error:

    /usr/bin/ld: cannot find -lscsgpu
    /usr/bin/ld: skipping incompatible /usr/local/cuda/lib/libcudart.so when searching for -lcudart
    /usr/bin/ld: cannot find -lcudart
    /usr/bin/ld: skipping incompatible /usr/local/cuda/lib/libcublas.so when searching for -lcublas
    /usr/bin/ld: cannot find -lcublas
    /usr/bin/ld: skipping incompatible /usr/local/cuda/lib/libcusparse.so when searching for -lcusparse
    /usr/bin/ld: cannot find -lcusparse
    collect2: error: ld returned 1 exit status
    /usr/bin/ld: cannot find -lscsgpu
    /usr/bin/ld: skipping incompatible /usr/local/cuda/lib/libcudart.so when searching for -lcudart
    /usr/bin/ld: cannot find -lcudart
    /usr/bin/ld: skipping incompatible /usr/local/cuda/lib/libcublas.so when searching for -lcublas
    /usr/bin/ld: cannot find -lcublas
    /usr/bin/ld: skipping incompatible /usr/local/cuda/lib/libcusparse.so when searching for -lcusparse
    /usr/bin/ld: cannot find -lcusparse
    collect2: error: ld returned 1 exit status
    

    Any suggestions why this may happen?

    opened by btabibian 15
  • SCS warning

    SCS warning

    I am using SCS in CVXPY for solving a mars landing problem. I could get the optimal solution, but i getting a warning WARN: aa_init returned NULL, no acceleration applied.

    what does it mean?

    opened by dinesh286 14
  • valgrind openblas issues

    valgrind openblas issues

    I've been trying to figure out why SCS has been randomly failing JuMP's SDP unit tests. Here's an example failure:

    Lin-sys: sparse-direct, nnz in A = 60
    eps = 1.00e-06, alpha = 1.80, max_iters = 20000, normalize = 1, scale = 5.00
    Variables n = 26, constraints m = 46
    Cones:  primal zero / dual free vars: 12
        linear vars: 4
        soc vars: 14, soc blks: 2
        sd vars: 16, sd blks: 2
    Setup time: 1.63e-04s
    ----------------------------------------------------------------------------
     Iter | pri res | dua res | rel gap | pri obj | dua obj | kap/tau | time (s)
    ----------------------------------------------------------------------------
         0|      inf       inf      -nan      -inf       inf       inf  7.85e-05 
       100|      inf       inf      -nan       inf       inf       inf  1.93e-03 
       200|      inf       inf      -nan      -inf       inf       inf  3.82e-03 
       220|      inf       inf      -nan      -inf       inf       inf  4.21e-03 
    ----------------------------------------------------------------------------
    

    and then if you run it again, you might get the right solution:

    Lin-sys: sparse-direct, nnz in A = 60
    eps = 1.00e-06, alpha = 1.80, max_iters = 20000, normalize = 1, scale = 5.00
    Variables n = 26, constraints m = 46
    Cones:  primal zero / dual free vars: 12
        linear vars: 4
        soc vars: 14, soc blks: 2
        sd vars: 16, sd blks: 2
    Setup time: 1.68e-04s
    ----------------------------------------------------------------------------
     Iter | pri res | dua res | rel gap | pri obj | dua obj | kap/tau | time (s)
    ----------------------------------------------------------------------------
         0|      inf       inf      -nan      -inf      -inf       inf  8.67e-05 
       100| 2.78e-04  2.73e-04  5.18e-04 -2.72e+00 -2.72e+00  7.40e-17  1.23e-03 
       200| 3.43e-06  1.03e-05  4.96e-06 -2.72e+00 -2.72e+00  1.23e-16  2.35e-03 
       260| 2.46e-07  7.22e-07  3.62e-07 -2.72e+00 -2.72e+00  1.23e-16  3.02e-03 
    ----------------------------------------------------------------------------
    Status: Solved
    Timing: Total solve time: 3.03e-03s
    

    Interestingly, I can only reproduce the issue if SCS is used to solve a number of SDPs before this one in the same session.

    So anyway I ran this under valgrind. I get some messages like this:

    Status: Solved/Inaccurate
    Hit max_iters, solution may be inaccurate
    Timing: Total solve time: 6.96e+01s
        Lin-sys: nnz in L factor: 150, avg solve time: 4.39e-05s
        Cones: avg projection time: 3.35e-03s
    ----------------------------------------------------------------------------
    Error metrics:
    ==27222== Invalid read of size 16
    ==27222==    at 0xCC815AC: daxpy_k_SANDYBRIDGE (in /mnt/hdd/mlubin/julia-0.4/usr/lib/libopenblas.so)
    ==27222==    by 0xBC3350C: syr_kernel (in /mnt/hdd/mlubin/julia-0.4/usr/lib/libopenblas.so)
    ==27222==    by 0xBE04488: exec_blas (in /mnt/hdd/mlubin/julia-0.4/usr/lib/libopenblas.so)
    ==27222==    by 0xBC336FA: dsyr_thread_L (in /mnt/hdd/mlubin/julia-0.4/usr/lib/libopenblas.so)
    ==27222==    by 0xBBEE521: dsyr_64_ (in /mnt/hdd/mlubin/julia-0.4/usr/lib/libopenblas.so)
    ==27222==    by 0x13A3F6B7: projSemiDefiniteCone (cones.c:530)
    ==27222==    by 0x13A3F6B7: projDualCone (cones.c:667)
    ==27222==    by 0x13A38109: getDualConeDist (scs.c:500)
    ==27222==    by 0x13A3A9E9: printFooter (scs.c:570)
    ==27222==    by 0x13A3A9E9: scs_solve (scs.c:802)
    ==27222==    by 0x1706F176: ???
    ==27222==    by 0x1706EC5E: ???
    ==27222==    by 0x1706E604: ???
    ==27222==    by 0x4F15354: jl_apply (julia.h:1263)
    ==27222==    by 0x4F15354: jl_apply_generic (gf.c:1675)
    ==27222==  Address 0x12604c60 is 192 bytes inside a block of size 200 alloc'd
    ==27222==    at 0x4C2DC90: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
    ==27222==    by 0x13A3E444: initCone (cones.c:378)
    ==27222==    by 0x13A3AF55: initWork (scs.c:695)
    ==27222==    by 0x13A3AF55: scs_init (scs.c:849)
    ==27222==    by 0x1706EB66: ???
    ==27222==    by 0x1706E604: ???
    ==27222==    by 0x4F15354: jl_apply (julia.h:1263)
    ==27222==    by 0x4F15354: jl_apply_generic (gf.c:1675)
    ==27222==    by 0x1706B875: ???
    ==27222==    by 0x1706CF8B: ???
    ==27222==    by 0x1706CD99: ???
    ==27222==    by 0x1706AE3C: ???
    ==27222==    by 0x1706A8B9: ???
    ==27222==    by 0x1706A6DB: ???
    ==27222== 
    

    On v1.1.5, cones:378 is where the Z vector for eigenvectors is allocated. In this case, it's a 5*5 SDP constraint, so Z has 5*5*8=200 bytes. For some reason, openblas is trying to read the last elements and goes off past the end. If I explicitly add 16 bytes padding to the calloc call, then the error goes away, but doesn't resolve the random failures. It doesn't help to use posix_memalign instead of malloc. This is maybe completely unrelated to the failures above, maybe not.

    @bodono, any debugging tips?

    CC @joehuchette @IainNZ @madeleineudell @tkelman

    opened by mlubin 14
  • Optimization is not solved because of

    Optimization is not solved because of "FATAL: syev failure, info = -5"

    Good evening, I am currently trying to solve an optimization problem with the solver scs (I am currently using it inside the YALMIP toolbox) but at the first iteration I get the following output:

    ------------------------------------------------------------------
    	       SCS v3.2.0 - Splitting Conic Solver
    	(c) Brendan O'Donoghue, Stanford University, 2012
    ------------------------------------------------------------------
    problem:  variables n: 7708, constraints m: 12772
    cones: 	  z: primal zero / dual free vars: 4368
    	  l: linear vars: 1584
    	  q: soc vars: 6820, qsize: 3
    	  s: psd vars: 0, ssize: 1
    settings: eps_abs: 1.0e-04, eps_rel: 1.0e-04, eps_infeas: 1.0e-07
    	  alpha: 1.50, scale: 5.00e+00, adaptive_scale: 1
    	  max_iters: 2500, normalize: 1, rho_x: 1.00e-03
    	  acceleration_lookback: 10, acceleration_interval: 10
    lin-sys:  sparse-direct
    	  nnz(A): 24362733, nnz(P): 0
    FATAL: syev failure, info = -5
    ERROR: init_cone failure
    Failure:could not initialize work
    

    I have tried to fix this issue by myself but I have not found anything related to this problem.

    opened by fraricca 4
  • Solution not found on sparse quadratic program

    Solution not found on sparse quadratic program

    Specifications

    • OS: Ubuntu 20.04 LTS
    • SCS Version: 3.2.2
    • Compiler: (installed from PyPI)

    Description

    SCS does not find a solution to the attached problem: scs_dump.zip.

    This problem should be feasible, with an objective value at the optimum around 562.443e9.

    How to reproduce

    The problem was generated by the following script:

    import numpy as np
    import scipy.sparse as spa
    from qpsolvers import solve_ls
    
    def generate_problem(n: int):
        # minimize || x - s ||^2
        R = spa.eye(n, format="csc")
        s = np.array(range(n), dtype=float)
        # such that G * x <= h
        G = spa.diags(
            diagonals=[
                [1.0 if i % 2 == 0 else 0.0 for i in range(n)],
                [1.0 if i % 3 == 0 else 0.0 for i in range(n - 1)],
                [1.0 if i % 5 == 0 else 0.0 for i in range(n - 1)],
            ],
            offsets=[0, 1, -1],
            format="csc",
        )
        h = np.ones(G.shape[0])
        # such that sum(x) == 42
        A = spa.csc_matrix(np.ones((1, n)))
        b = np.array([42.0]).reshape((1,))
        # such that x >= 0
        lb = np.zeros(n)
        return R, s, G, h, A, b, lb
    
    if __name__ == "__main__":
        R, s, G, h, A, b, lb = generate_problem(n=15000)
        x = solve_ls(R, s, G, h, A, b, lb, solver="scs", verbose=False, write_data_filename="scs_dump")
        assert x is not None
    

    Additional information

    I tried varying the problem size n and comparing to other solvers:

    | Solver | n | Objective at returned solution | |--|--|--| | CVXOPT | 1,500 | 561874994.0 | | HiGHS | 1,500 | 561874994.0 | | OSQP | 1,500 | 561875870.1 | | ProxQP | 1,500 | 561874993.6 | | SCS | 1,500 | 561874991.4 | | CVXOPT | 15,000 | 562443121619.2 | | HiGHS | 15,000 | 562443121619.0 | | OSQP | 15,000 | 562443434746.2 | | ProxQP | 15,000 | 562443121598.1 | | SCS | 15,000 | not found (this issue) |

    (All solvers use their default settings. The objective is $1/2 \Vert x - s \Vert^2$ at the returned solution $x$.)

    The conversion from (R, s, G, h, A, b, lb) to SCS cone, data works for smaller values of n, but this doesn't mean it is clear of all suspicion. Hoping scs_dump.zip helps investigate.

    Output

    ------------------------------------------------------------------
    	       SCS v3.2.2 - Splitting Conic Solver
    	(c) Brendan O'Donoghue, Stanford University, 2012
    ------------------------------------------------------------------
    problem:  variables n: 15000, constraints m: 30002
    cones: 	  z: primal zero / dual free vars: 1
    	  l: linear vars: 15000
    	  b: box cone vars: 15001
    settings: eps_abs: 1.0e-04, eps_rel: 1.0e-04, eps_infeas: 1.0e-07
    	  alpha: 1.50, scale: 1.00e-01, adaptive_scale: 1
    	  max_iters: 100000, normalize: 1, rho_x: 1.00e-06
    	  acceleration_lookback: 10, acceleration_interval: 10
    lin-sys:  sparse-direct-amd-qdldl
    	  nnz(A): 45500, nnz(P): 15000
    ------------------------------------------------------------------
     iter | pri res | dua res |   gap   |   obj   |  scale  | time (s)
    ------------------------------------------------------------------
         0| 3.52e+04  1.39e+04  2.97e+11 -2.30e+11  1.00e-01  5.38e-02 
    ------------------------------------------------------------------
    status:  unbounded
    timings: total: 5.42e-02s = setup: 4.87e-02s + solve: 5.42e-03s
    	 lin-sys: 5.40e-04s, cones: 4.99e-04s, accel: 4.40e-08s
    ------------------------------------------------------------------
    objective = -inf
    ------------------------------------------------------------------
    
    opened by stephane-caron 1
  • Iteration callback for early stopping

    Iteration callback for early stopping

    Specifications

    • OS: Windows
    • SCS Version: 3.2.1
    • Compiler: Microsoft C++

    Description

    It would be nice to be able to stop SCS early. One way to implement this could be be passing a function pointer in the ScsSettings that is called on each iteration. This would also allow to report the progress back to the caller. Right now SCS writes directly to SCS and there is no way for the caller to monitor optimization progress.

    opened by gkronber 1
  • Failed to build - possible BLAS issue

    Failed to build - possible BLAS issue

    Hello, I'm trying to pip install scs on macOS Moneterey, M1 chip via the installation guide, but I keep getting the error below.

     blas_mkl_info:
            NOT AVAILABLE
          blis_info:
            NOT AVAILABLE
          openblas_info:
              libraries = ['openblas', 'openblas']
              library_dirs = ['/opt/arm64-builds/lib']
              language = c
              define_macros = [('HAVE_CBLAS', None)]
              runtime_library_dirs = ['/opt/arm64-builds/lib']
          blas_opt_info:
              libraries = ['openblas', 'openblas']
              library_dirs = ['/opt/arm64-builds/lib']
              language = c
              define_macros = [('HAVE_CBLAS', None)]
              runtime_library_dirs = ['/opt/arm64-builds/lib']
          lapack_mkl_info:
            NOT AVAILABLE
          openblas_lapack_info:
              libraries = ['openblas', 'openblas']
              library_dirs = ['/opt/arm64-builds/lib']
              language = c
              define_macros = [('HAVE_CBLAS', None)]
              runtime_library_dirs = ['/opt/arm64-builds/lib']
          lapack_opt_info:
              libraries = ['openblas', 'openblas']
              library_dirs = ['/opt/arm64-builds/lib']
              language = c
              define_macros = [('HAVE_CBLAS', None)]
              runtime_library_dirs = ['/opt/arm64-builds/lib']
          {'libraries': ['openblas', 'openblas'], 'library_dirs': ['/opt/homebrew/opt/openblas/lib'], 'language': 'c', 'define_macros': [('HAVE_CBLAS', None)], 'runtime_library_dirs': ['/opt/homebrew/opt/openblas/lib']}
          {'libraries': ['openblas', 'openblas'], 'library_dirs': ['/opt/homebrew/opt/openblas/lib'], 'language': 'c', 'define_macros': [('HAVE_CBLAS', None)], 'runtime_library_dirs': ['/opt/homebrew/opt/openblas/lib']}
          error: Command "clang -Wno-unused-result -Wsign-compare -Wunreachable-code -DNDEBUG -g -fwrapv -O3 -Wall -I/Library/Developer/CommandLineTools/SDKs/MacOSX12.1.sdk/usr/include -I/Library/Developer/CommandLineTools/SDKs/MacOSX12.1.sdk/usr/include -DPYTHON -DCTRLC=1 -DDLONG=1 -DUSE_LAPACK -DHAVE_CBLAS -DHAVE_CBLAS -Iscs/include -Iscs/linsys -Iscs/linsys/cpu/direct/ -Iscs/linsys/external/amd -Iscs/linsys/external/dqlql -I/private/var/folders/69/zykcchfx29s95t3v93270g140000gn/T/pip-build-env-adc48o08/overlay/lib/python3.9/site-packages/numpy/core/include -I/Users/killian/.pyenv/versions/3.9.9/include/python3.9 -c scs/linsys/scs_matrix.c -o build/temp.macosx-12.2-arm64-cpython-39/scs/linsys/scs_matrix.o -O3" failed with exit status 1
    

    I have BLAS, OPENBLAS and LAPACK all installed via brew. I'm not quite sure from the error if this is a OPENBLAS issue or Command Line Tools. In either case, I've installed and updated the latest versions of both. Is there something else I can do here to fix this? Thanks

    opened by ktattan 17
  • NotImplementedError when using SCS with GPU

    NotImplementedError when using SCS with GPU

    Specifications

    • OS: Windows 10
    • SCS Version: 3.1.0
    • Compiler: Python

    Description

    I'm trying to use SCS using the GPU. I am using it along with CVXPY. When solving on CPU, I encounter no problems. When I add the parameter "gpu" = True, I encounter the following error: "NotImplementedError: GPU direct solver not yet available, passuse_indirect=True."

    How to reproduce

    I installed SCS using the steps in the documentation:

    git clone --recursive https://github.com/bodono/scs-python.git
    cd scs-python
    python setup.py install --scs --gpu
    

    installation was able to complete.

    I have CUDA installed and an environment variable "CUDA_PATH" pointing to its directory.

    Additional information

    While I understand that CPU may be faster, I am hoping to integrate SCS in an end to end learning framework that is on the GPU.

    Output

    File ~\anaconda3\lib\site-packages\cvxpy\problems\problem.py:473, in Problem.solve(self, *args, **kwargs)
        471 else:
        472     solve_func = Problem._solve
    --> 473 return solve_func(self, *args, **kwargs)
    
    File ~\anaconda3\lib\site-packages\cvxpy\problems\problem.py:975, in Problem._solve(self, solver, warm_start, verbose, gp, qcp, requires_grad, enforce_dpp, **kwargs)
        971     s.LOGGER.info(
        972             'Invoking solver %s  to obtain a solution.',
        973             solving_chain.reductions[-1].name())
        974 start = time.time()
    --> 975 solution = solving_chain.solve_via_data(
        976     self, data, warm_start, verbose, kwargs)
        977 end = time.time()
        978 self._solve_time = end - start
    
    File ~\anaconda3\lib\site-packages\cvxpy\reductions\solvers\solving_chain.py:343, in SolvingChain.solve_via_data(self, problem, data, warm_start, verbose, solver_opts)
        307 def solve_via_data(self, problem, data, warm_start: bool = False, verbose: bool = False,
        308                    solver_opts={}):
        309     """Solves the problem using the data output by the an apply invocation.
        310 
        311     The semantics are:
       (...)
        341         a Solution object.
        342     """
    --> 343     return self.solver.solve_via_data(data, warm_start, verbose,
        344                                       solver_opts, problem._solver_cache)
    
    File ~\anaconda3\lib\site-packages\cvxpy\reductions\solvers\conic_solvers\scs_conif.py:321, in SCS.solve_via_data(self, data, warm_start, verbose, solver_opts, solver_cache)
        318         solver_opts['eps_abs'] = solver_opts.get('eps_abs', 1e-5)
        319         solver_opts['eps_rel'] = solver_opts.get('eps_rel', 1e-5)
    --> 321     results = scs.solve(args, cones, verbose=verbose, **solver_opts)
        322     status = self.STATUS_MAP[results["info"]["status_val"]]
        324 if solver_cache is not None and status == s.OPTIMAL:
    
    File ~\anaconda3\lib\site-packages\scs\__init__.py:133, in solve(probdata, cone, **kwargs)
        131 if kwargs.pop('gpu', False):  # False by default
        132   if not kwargs.pop('use_indirect', _USE_INDIRECT_DEFAULT):
    --> 133     raise NotImplementedError(
        134         'GPU direct solver not yet available, pass `use_indirect=True`.')
        135   import _scs_gpu
        136   return _scs_gpu.csolve((m, n), Adata, Aindices, Acolptr, Pdata, Pindices,
        137                          Pcolptr, b, c, cone, warm, **kwargs)
    
    NotImplementedError: GPU direct solver not yet available, pass `use_indirect=True`.
    

    Thank you, your help is appreciated.

    opened by hassanis 3
  • slow/no convergence of SCS on a tiny problem

    slow/no convergence of SCS on a tiny problem

    Specifications

    • OS: julia distribution of SCS
    • SCS Version: 3.2.0
    • Compiler: gcc

    Description

    SCS-3.2.0 fails to converge.

    How to reproduce

    the attached file contains a problem that scs struggles to solve. Fixing max_iters=10_000 and grid search on acceleration_lookback = -20:1:20 and alpha = 0.1:0.05:1.99 the problem is solved successfully only 13 times.

    Additional information

    The correct objective value is 3825 / 4096 ≈ 0.933837890625. The problem is tiny: when solved, it's <2000 iterations, runs in 0.05s so it's easy to experiment. It's somehow difficult to explain as it is a symmetric reformulation of sum of squares problem here: https://github.com/kalmarek/SymbolicWedderburn.jl/blob/master/test/action_dihedral.jl

    here is the write_data_filename: https://cloud.impan.pl/s/HeOfF5dZyG4SO3N

    Output

    e.g. unsuccessful solve:

    ------------------------------------------------------------------
               SCS v3.2.0 - Splitting Conic Solver
        (c) Brendan O'Donoghue, Stanford University, 2012
    ------------------------------------------------------------------
    problem:  variables n: 12, constraints m: 17
    cones:    z: primal zero / dual free vars: 6
          s: psd vars: 11, ssize: 4
    settings: eps_abs: 1.0e-06, eps_rel: 1.0e-06, eps_infeas: 1.0e-07
          alpha: 1.70, scale: 1.00e-01, adaptive_scale: 1
          max_iters: 5000, normalize: 1, rho_x: 1.00e-06
          acceleration_lookback: 8, acceleration_interval: 10
    lin-sys:  sparse-direct
          nnz(A): 25, nnz(P): 0
    ------------------------------------------------------------------
     iter | pri res | dua res |   gap   |   obj   |  scale  | time (s)
    ------------------------------------------------------------------
         0| 1.86e+01  1.00e+00  1.90e+01 -1.11e+01  1.00e-01  4.25e-05 
       250| 1.33e-02  1.60e-03  2.19e-02  5.87e-01  3.26e-01  2.27e-03 
       500| 9.43e-03  6.44e-04  9.17e-03  7.05e-01  3.26e-01  4.48e-03 
       750| 5.02e-02  6.61e-02  4.98e-04  9.23e-01  3.26e-01  6.75e-03  ← notice this jump in obj/gap/res
      1000| 6.27e-03  3.55e-04  4.54e-03  7.83e-01  3.26e-01  9.04e-03 
      1250| 5.43e-03  2.95e-04  3.67e-03  8.03e-01  3.26e-01  1.13e-02 
      1500| 4.81e-03  2.53e-04  3.10e-03  8.18e-01  3.26e-01  1.35e-02 
      1750| 4.32e-03  2.23e-04  2.69e-03  8.29e-01  3.26e-01  1.58e-02 
      2000| 3.93e-03  1.99e-04  2.37e-03  8.38e-01  3.26e-01  1.80e-02 
      2250| 3.61e-03  1.80e-04  2.13e-03  8.46e-01  3.26e-01  2.01e-02 
      2500| 3.34e-03  1.65e-04  1.93e-03  8.52e-01  3.26e-01  2.23e-02 
      2750| 3.12e-03  1.52e-04  1.77e-03  8.57e-01  3.26e-01  2.45e-02 
      3000| 2.07e-02  2.72e-02  1.59e-04  9.30e-01  3.26e-01  2.67e-02  ← notice this jump in obj/gap/res
      3250| 2.74e-03  1.31e-04  1.52e-03  8.66e-01  3.26e-01  2.89e-02 
      3500| 2.59e-03  1.23e-04  1.42e-03  8.70e-01  3.26e-01  3.11e-02 
      3750| 2.46e-03  1.16e-04  1.33e-03  8.73e-01  3.26e-01  3.33e-02 
      4000| 2.34e-03  1.10e-04  1.25e-03  8.76e-01  3.26e-01  3.55e-02 
      4250| 2.23e-03  1.04e-04  1.19e-03  8.79e-01  3.26e-01  3.78e-02 
      4500| 2.13e-03  9.91e-05  1.12e-03  8.81e-01  3.26e-01  4.00e-02 
      4750| 2.04e-03  9.45e-05  1.07e-03  8.83e-01  3.26e-01  4.22e-02 
      5000| 1.95e-03  9.03e-05  1.02e-03  8.85e-01  3.26e-01  4.45e-02 
    ------------------------------------------------------------------
    status:  solved (inaccurate - reached max_iters)
    timings: total: 4.46e-02s = setup: 1.27e-04s + solve: 4.45e-02s
         lin-sys: 6.74e-03s, cones: 1.53e-02s, accel: 5.34e-03s
    ------------------------------------------------------------------
    objective = 0.885423 (inaccurate)
    ------------------------------------------------------------------
    

    and a successful one:

    ------------------------------------------------------------------
               SCS v3.2.0 - Splitting Conic Solver
        (c) Brendan O'Donoghue, Stanford University, 2012
    ------------------------------------------------------------------
    problem:  variables n: 12, constraints m: 17
    cones:    z: primal zero / dual free vars: 6
          s: psd vars: 11, ssize: 4
    settings: eps_abs: 1.0e-06, eps_rel: 1.0e-06, eps_infeas: 1.0e-07
          alpha: 1.95, scale: 1.00e-01, adaptive_scale: 1
          max_iters: 5000, normalize: 1, rho_x: 1.00e-06
          acceleration_lookback: -15, acceleration_interval: 10
    lin-sys:  sparse-direct
          nnz(A): 25, nnz(P): 0
    ------------------------------------------------------------------
     iter | pri res | dua res |   gap   |   obj   |  scale  | time (s)
    ------------------------------------------------------------------
         0| 1.86e+01  1.00e+00  1.90e+01 -1.11e+01  1.00e-01  5.57e-05 
       250| 6.75e-03  1.28e-02  4.90e-02  5.95e-01  1.43e+00  3.09e-03 
       500| 4.02e-03  4.41e-03  1.24e-02  7.90e-01  1.43e+00  6.15e-03 
       750| 3.35e-04  1.94e-03  3.59e-08  9.34e-01  1.43e+00  9.32e-03 
      1000| 2.57e-06  8.33e-06  9.52e-06  9.34e-01  1.43e+00  1.25e-02 
      1125| 1.65e-06  1.62e-06  8.76e-07  9.34e-01  1.43e+00  1.40e-02 
    ------------------------------------------------------------------
    status:  solved
    timings: total: 1.42e-02s = setup: 1.26e-04s + solve: 1.40e-02s
         lin-sys: 1.96e-03s, cones: 5.33e-03s, accel: 1.82e-03s
    ------------------------------------------------------------------
    objective = 0.933804
    ------------------------------------------------------------------
    
    opened by kalmarek 3
Releases(3.2.0)
Owner
Stanford University Convex Optimization Group
Stanford University Convex Optimization Group
Muriqui Optimizer - A convex mixed integer nonlinear programming solver

Muriqui Optimizer Muriqui Optimizer is a solver for convex Mixed Integer Nonlinear Programming (MINLP) problems. For more informations and user manual

null 5 Oct 4, 2022
A 2D Physics Engine written in C++, supporting circles and orientable, non-regular convex polygons.

PhysicsEngine A basic physics engine supporting circles and orientable non-regular convex polygons. Oh, and it has undamped springs and strings. Demo

ThePythonator 3 Mar 19, 2022
Library that solves the exact cover problem using Dancing Links, also known as DLX.

The DLX Library The DLX library The DLX library solves instances of the exact cover problem, using Dancing Links (Knuth’s Algorithm X). Also included

Ben Lynn 44 Dec 18, 2022
Solves a given NxN wordsearch in under 0.3 seconds at most using Rabin-Karp string algorithm.

ASSIGNMENT 2 The Information of the Creator: ASSIGNMENT 2 Author: Lukas Waschuk CCID: lwaschuk Date: 03-20-2021 The Purpose of Your Program: This prog

Lukas Waschuk 0 May 17, 2022
Based on the spatial resection theory, the algorithm solves the camera position by solving the homography matrix.

Based on the spatial resection theory, the algorithm solves the camera position by solving the homography matrix.

null 1 Nov 13, 2021
Nameof operator for modern C++, simply obtain the name of a variable, type, function, macro, and enum

_ _ __ _____ | \ | | / _| / ____|_ _ | \| | __ _ _ __ ___ ___ ___ | |_ | | _| |

Daniil Goncharov 1.5k Jan 4, 2023
Nameof operator for modern C++, simply obtain the name of a variable, type, function, macro, and enum

_ _ __ _____ | \ | | / _| / ____|_ _ | \| | __ _ _ __ ___ ___ ___ | |_ | | _| |

Daniil Goncharov 1.5k Jan 8, 2023
Provide sample code of efficient operator implementation based on the Cambrian Machine Learning Unit (MLU) .

Cambricon CNNL-Example CNNL-Example 提供基于寒武纪机器学习单元(Machine Learning Unit,MLU)开发高性能算子、C 接口封装的示例代码。 依赖条件 操作系统: 目前只支持 Ubuntu 16.04 x86_64 寒武纪 MLU SDK: 编译和

Cambricon Technologies 1 Mar 7, 2022
An optimized neural network operator library for chips base on Xuantie CPU.

简介 CSI-NN2 是 T-HEAD 提供的一组针对无剑 SoC 平台的神经网络库 API。抽象了各种常用的网络层的接口,并且提供一系列已优化的二进制库。 CSI-NN2 的特性: 开源 c 代码版本的参考实现。 提供玄铁 CPU 的汇编优化实现。

T-Head Semiconductor Co., Ltd. 32 Jan 5, 2023
A LLVM-based static analyzer to produce PyTorch operator dependency graph.

What is this? This is a clone of the deprecated LLVM-based static analyzer from the PyTorch repo, which can be used to produce the PyTorch operator de

Jiakai Liu 5 Dec 15, 2021
Improved Fractions Calculator using structures, user input parsing, and dynamic operator switching

Improved Fractions Calculator Program Structure: Main File: Runs fnctions from various header files. IO.h Header file containing IO functions, Interfa

Colin McCormack 1 Dec 5, 2021
MissionImpossible - A concise C++17 implementation of automatic differentiation (operator overloading)

Mission : Impossible (AutoDiff) Table of contents What is it? News Compilation Meson CMake Examples Jacobian example Complex number example Hessian ac

pixor 18 Oct 13, 2022
Spack is a package manager, and package managers should be trivial to install.

?? Spack with batteries included (linux/x86_64) Spack is a package manager, and package managers should be trivial to install. This repo offers a sing

Harmen Stoppels 22 Dec 1, 2022
BakePKG is a package archive that can install itself without without a package manager.

BakePKG A bad way of packaging applications. Introduction BakePKG is a package archive that can install itself without without a package manager. The

bread 3 Sep 3, 2022
RNNLIB is a recurrent neural network library for sequence learning problems. Forked from Alex Graves work http://sourceforge.net/projects/rnnl/

Origin The original RNNLIB is hosted at http://sourceforge.net/projects/rnnl while this "fork" is created to repeat results for the online handwriting

Sergey Zyrianov 879 Dec 26, 2022
180+ Algorithm & Data Structure Problems using C++

180+ Algorithm & Data Structure Problems using C++

Ravi Mandliya 5.2k Jan 8, 2023
Data Structure and Algorithms problems across various platforms.

Covering various practice problems of Arrays, Stacks, queue, tree, graph and different Algorithms. A collection of solutions for Data Structure and Algorithms problems across various platforms in different languages.

Nivedita Singh 42 Oct 29, 2022
Repository of problems and solutions of labsheets used for Data Structures and Algorithms (CS F211) in Semester 2, 2020-21 at BITS Pilani - Hyderabad Campus.

CS F211 Data Structures and Algorithms (BITS Pilani - Hyderabad Campus) This repository contains the problems, solution approaches & explanations and

Rohit Dwivedula 27 Oct 31, 2022
Solutions for problems given in ETH course Algorithms Lab in Fall 2020

Algolab2020 Solutions for problems given in ETH course Algorithms Lab in Fall 2020. The code for these problems is written with the following in mind:

null 45 Jan 3, 2023
LeetCode Coding Problems

LeetCode LeetCode Coding Problems Author: Abhishek Kumar My C++ Code for LeetCode OJ. Please give this repo a ⭐️ if it inspires you. Thanks. ☺️ # Titl

Abhishek kumar 3 Jan 7, 2022