0
# ECOS - Embedded Conic Solver
1
2
ECOS is a high-performance numerical library for solving convex second-order cone programs (SOCPs) designed specifically for embedded systems and real-time applications. The solver implements efficient algorithms for constrained optimization problems with conic constraints, supporting both continuous and mixed-integer formulations through its branch-and-bound extension (ECOS_BB).
3
4
## Package Information
5
6
- **Package Name**: ecos
7
- **Language**: C
8
- **License**: GPL-3.0
9
- **Installation**: Build from source using provided Makefile (`make all` to build libraries, `make demo` to build demo)
10
- **Dependencies**: SuiteSparse components (LDL and AMD packages are included in external/ directory)
11
12
## Core Imports
13
14
```c
15
#include "ecos.h" // Core ECOS solver
16
#include "ecos_bb.h" // Mixed-integer branch-and-bound extension
17
```
18
19
## Basic Usage
20
21
### Solving a Basic SOCP
22
23
```c
24
#include "ecos.h"
25
26
// Problem data: minimize c'*x subject to A*x = b, G*x <=_K h
27
// where K is a product of positive orthant and second-order cones
28
29
int main() {
30
// Problem dimensions
31
idxint n = 3; // number of variables
32
idxint m = 3; // number of inequality constraints
33
idxint p = 1; // number of equality constraints
34
idxint l = 1; // number of positive orthant constraints
35
idxint ncones = 1; // number of second-order cones
36
idxint q[1] = {2}; // sizes of second-order cones
37
38
// Problem data (example values)
39
pfloat c[3] = {1.0, 1.0, 0.0};
40
pfloat h[3] = {1.0, 0.0, 0.0};
41
pfloat b[1] = {1.0};
42
43
// Sparse matrices G and A (CSC format)
44
pfloat Gpr[4] = {1.0, 0.0, 0.0, 1.0};
45
idxint Gjc[4] = {0, 1, 2, 4};
46
idxint Gir[4] = {0, 1, 1, 2};
47
48
pfloat Apr[1] = {1.0};
49
idxint Ajc[4] = {0, 1, 1, 1};
50
idxint Air[1] = {0};
51
52
// Set up solver workspace
53
pwork* mywork = ECOS_setup(n, m, p, l, ncones, q,
54
Gpr, Gjc, Gir,
55
Apr, Ajc, Air,
56
c, h, b);
57
58
if (mywork) {
59
// Solve the problem
60
idxint exitflag = ECOS_solve(mywork);
61
62
// Check solution status
63
if (exitflag == ECOS_OPTIMAL) {
64
printf("Optimal solution found\\n");
65
printf("Objective value: %f\\n", mywork->info->pcost);
66
67
// Access solution
68
for (int i = 0; i < n; i++) {
69
printf("x[%d] = %f\\n", i, mywork->x[i]);
70
}
71
}
72
73
// Clean up
74
ECOS_cleanup(mywork, 0);
75
}
76
77
return 0;
78
}
79
```
80
81
### Solving Mixed-Integer Problems
82
83
```c
84
#include "ecos_bb.h"
85
86
int main() {
87
// Set up problem data (same as above)
88
// ...
89
90
// Mixed-integer specific data
91
idxint num_bool_vars = 1; // number of boolean variables
92
idxint bool_vars_idx[1] = {0}; // indices of boolean variables
93
idxint num_int_vars = 0; // number of integer variables
94
idxint* int_vars_idx = NULL; // indices of integer variables
95
96
// Set up mixed-integer solver
97
ecos_bb_pwork* mywork = ECOS_BB_setup(n, m, p, l, ncones, q,
98
Gpr, Gjc, Gir,
99
Apr, Ajc, Air,
100
c, h, b,
101
num_bool_vars, bool_vars_idx,
102
num_int_vars, int_vars_idx,
103
NULL); // use default settings
104
105
if (mywork) {
106
// Solve mixed-integer problem
107
idxint exitflag = ECOS_BB_solve(mywork);
108
109
// Check results and clean up
110
ECOS_BB_cleanup(mywork, 0);
111
}
112
113
return 0;
114
}
115
```
116
117
## Architecture
118
119
ECOS is organized into several key modules:
120
121
- **Core Solver (`ecos.h`)**: Main optimization algorithm and workspace management
122
- **Branch-and-Bound (`ecos_bb.h`)**: Mixed-integer extension with tree search
123
- **Cone Operations (`cone.h`)**: Conic constraint handling and projections
124
- **KKT System (`kkt.h`)**: Linear system factorization and solving
125
- **Sparse Linear Algebra (`spla.h`)**: Matrix-vector operations
126
- **Problem Setup**: Data preprocessing and equilibration
127
128
The solver uses interior-point methods with efficient sparse linear algebra, making it suitable for embedded applications with limited computational resources.
129
130
## Capabilities
131
132
### Core SOCP Solver
133
134
Complete interface for solving continuous second-order cone programs including problem setup, solving, and memory management.
135
136
```c { .api }
137
pwork* ECOS_setup(idxint n, idxint m, idxint p, idxint l, idxint ncones, idxint* q,
138
pfloat* Gpr, idxint* Gjc, idxint* Gir,
139
pfloat* Apr, idxint* Ajc, idxint* Air,
140
pfloat* c, pfloat* h, pfloat* b);
141
142
idxint ECOS_solve(pwork* w);
143
144
void ECOS_cleanup(pwork* w, idxint keepvars);
145
146
const char* ECOS_ver(void);
147
```
148
149
[Core SOCP Solver](./core-solver.md)
150
151
### Mixed-Integer Branch-and-Bound
152
153
Extension for solving mixed-integer and mixed-boolean second-order cone programs using branch-and-bound search.
154
155
```c { .api }
156
ecos_bb_pwork* ECOS_BB_setup(idxint n, idxint m, idxint p, idxint l, idxint ncones, idxint* q,
157
pfloat* Gpr, idxint* Gjc, idxint* Gir,
158
pfloat* Apr, idxint* Ajc, idxint* Air,
159
pfloat* c, pfloat* h, pfloat* b,
160
idxint num_bool_vars, idxint* bool_vars_idx,
161
idxint num_int_vars, idxint* int_vars_idx,
162
settings_bb* stgs);
163
164
idxint ECOS_BB_solve(ecos_bb_pwork* prob);
165
166
void ECOS_BB_cleanup(ecos_bb_pwork* prob, idxint num_vars_keep);
167
```
168
169
[Mixed-Integer Solver](./mixed-integer.md)
170
171
### Problem Data Updates
172
173
Expert-level interface for updating problem data during solve iterations without complete re-setup.
174
175
```c { .api }
176
void ecos_updateDataEntry_h(pwork* w, idxint idx, pfloat value);
177
void ecos_updateDataEntry_c(pwork* w, idxint idx, pfloat value);
178
179
void updateDataEntry_h(ecos_bb_pwork* w, idxint idx, pfloat value);
180
void updateDataEntry_c(ecos_bb_pwork* w, idxint idx, pfloat value);
181
```
182
183
[Data Updates](./data-updates.md)
184
185
### Configuration and Settings
186
187
Solver parameter configuration and default settings management.
188
189
```c { .api }
190
typedef struct settings {
191
pfloat gamma;
192
pfloat delta;
193
pfloat eps;
194
pfloat feastol;
195
pfloat abstol;
196
pfloat reltol;
197
pfloat feastol_inacc;
198
pfloat abstol_inacc;
199
pfloat reltol_inacc;
200
idxint nitref;
201
idxint maxit;
202
idxint verbose;
203
} settings;
204
205
settings_bb* get_default_ECOS_BB_settings();
206
```
207
208
[Configuration](./configuration.md)
209
210
## Types
211
212
### Core Data Types
213
214
```c { .api }
215
typedef double pfloat; // Floating point precision type
216
typedef SuiteSparse_long idxint; // Index integer type
217
218
// Sparse matrix in compressed sparse column format
219
typedef struct spmat {
220
idxint* jc; // Column pointers
221
idxint* ir; // Row indices
222
pfloat* pr; // Numerical values
223
idxint n; // Number of columns
224
idxint m; // Number of rows
225
idxint nnz; // Number of non-zeros
226
} spmat;
227
228
// Complete solver workspace
229
typedef struct pwork {
230
// Problem dimensions
231
idxint n; // Number of primal variables
232
idxint m; // Number of conically constrained variables
233
idxint p; // Number of equality constraints
234
idxint D; // Degree of the cone
235
236
// Solution variables
237
pfloat* x; // Primal variables
238
pfloat* y; // Equality constraint multipliers
239
pfloat* z; // Conic inequality multipliers
240
pfloat* s; // Slack variables
241
pfloat kap; // Homogeneous embedding parameter
242
pfloat tau; // Homogeneous embedding parameter
243
244
// Problem data
245
spmat* A; // Equality constraint matrix
246
spmat* G; // Inequality constraint matrix
247
pfloat* c; // Objective vector
248
pfloat* b; // Equality constraint RHS
249
pfloat* h; // Inequality constraint RHS
250
251
// Internal solver data
252
cone* C; // Cone structure
253
kkt* KKT; // KKT system
254
stats* info; // Solution statistics
255
settings* stgs; // Solver settings
256
} pwork;
257
258
// Solution statistics
259
typedef struct stats {
260
pfloat pcost; // Primal objective value
261
pfloat dcost; // Dual objective value
262
pfloat pres; // Primal residual
263
pfloat dres; // Dual residual
264
pfloat pinf; // Primal infeasibility measure
265
pfloat dinf; // Dual infeasibility measure
266
pfloat gap; // Duality gap
267
pfloat relgap; // Relative duality gap
268
idxint iter; // Number of iterations
269
} stats;
270
```
271
272
### Mixed-Integer Types
273
274
```c { .api }
275
// Branch-and-bound settings
276
typedef struct settings_bb {
277
idxint maxit; // Maximum iterations
278
idxint verbose; // Verbosity level
279
pfloat abs_tol_gap; // Absolute gap tolerance
280
pfloat rel_tol_gap; // Relative gap tolerance
281
pfloat integer_tol; // Integer rounding tolerance
282
} settings_bb;
283
284
// Branch-and-bound tree node
285
typedef struct node {
286
char status; // Node status
287
pfloat L; // Lower bound
288
pfloat U; // Upper bound
289
idxint split_idx; // Split variable index
290
pfloat split_val; // Split value
291
} node;
292
293
// Mixed-integer solver workspace
294
typedef struct ecos_bb_pwork {
295
// Mixed-integer data
296
idxint num_bool_vars; // Number of boolean variables
297
idxint num_int_vars; // Number of integer variables
298
idxint* bool_vars_idx; // Boolean variable indices
299
idxint* int_vars_idx; // Integer variable indices
300
301
// Core ECOS solver
302
pwork* ecos_prob; // Underlying ECOS problem
303
304
// Branch-and-bound data
305
node* nodes; // Tree nodes
306
pfloat global_U; // Global upper bound
307
pfloat global_L; // Global lower bound
308
idxint iter; // Current iteration
309
310
// Settings
311
settings* ecos_stgs; // ECOS settings
312
settings_bb* stgs; // Branch-and-bound settings
313
} ecos_bb_pwork;
314
```
315
316
## Constants and Exit Codes
317
318
```c { .api }
319
// ECOS Exit Codes
320
#define ECOS_OPTIMAL 0 // Problem solved to optimality
321
#define ECOS_PINF 1 // Found certificate of primal infeasibility
322
#define ECOS_DINF 2 // Found certificate of dual infeasibility
323
#define ECOS_MAXIT -1 // Maximum number of iterations reached
324
#define ECOS_NUMERICS -2 // Search direction unreliable
325
#define ECOS_OUTCONE -3 // Variables got outside the cone
326
#define ECOS_SIGINT -4 // Solver interrupted by signal
327
#define ECOS_FATAL -7 // Unknown problem in solver
328
329
// Mixed-Integer Exit Codes
330
#define MI_OPTIMAL_SOLN 0 // Optimal solution found
331
#define MI_MAXITER_FEASIBLE_SOLN -1 // Max iterations with feasible solution
332
#define MI_MAXITER_NO_SOLN 1 // Max iterations without solution
333
#define MI_INFEASIBLE 2 // Problem infeasible
334
335
// Default Parameter Values
336
#define MAXIT 100 // Maximum iterations
337
#define FEASTOL 1E-8 // Feasibility tolerance
338
#define ABSTOL 1E-8 // Absolute tolerance
339
#define RELTOL 1E-8 // Relative tolerance
340
#define GAMMA 0.99 // Step length scaling
341
#define VERBOSE 1 // Verbosity flag
342
```