0
# Mixed-Integer Branch-and-Bound Solver
1
2
The ECOS_BB module extends the core ECOS solver with branch-and-bound capabilities for solving mixed-integer and mixed-boolean second-order cone programs (MI-SOCPs). It uses a tree search approach to handle discrete variables while leveraging the continuous SOCP solver at each node.
3
4
## Capabilities
5
6
### Mixed-Integer Problem Setup
7
8
Initializes the mixed-integer solver workspace with problem data and integer variable specifications.
9
10
```c { .api }
11
ecos_bb_pwork* ECOS_BB_setup(idxint n, idxint m, idxint p, idxint l, idxint ncones, idxint* q,
12
pfloat* Gpr, idxint* Gjc, idxint* Gir,
13
pfloat* Apr, idxint* Ajc, idxint* Air,
14
pfloat* c, pfloat* h, pfloat* b,
15
idxint num_bool_vars, idxint* bool_vars_idx,
16
idxint num_int_vars, idxint* int_vars_idx,
17
settings_bb* stgs);
18
```
19
20
**Parameters:**
21
- First 11 parameters: Same as ECOS_setup (problem data in CSC format)
22
- `num_bool_vars`: Number of boolean (binary) variables
23
- `bool_vars_idx`: Array of indices for boolean variables (length num_bool_vars)
24
- `num_int_vars`: Number of general integer variables
25
- `int_vars_idx`: Array of indices for integer variables (length num_int_vars)
26
- `stgs`: Branch-and-bound settings (NULL for defaults)
27
28
**Returns:** Pointer to mixed-integer solver workspace, or NULL on failure
29
30
**Usage Example:**
31
32
```c
33
// Mixed-integer problem with one boolean variable
34
idxint n = 3, m = 3, p = 1, l = 1, ncones = 1;
35
idxint q[1] = {2};
36
37
// Problem data (same as core solver)
38
pfloat c[3] = {1.0, 1.0, 0.0};
39
pfloat h[3] = {0.0, 0.0, 0.0};
40
// ... (G, A matrices as before)
41
42
// Integer variable specification
43
idxint num_bool_vars = 1;
44
idxint bool_vars_idx[1] = {0}; // x[0] is boolean
45
idxint num_int_vars = 0;
46
idxint* int_vars_idx = NULL;
47
48
// Use default settings
49
settings_bb* bb_settings = get_default_ECOS_BB_settings();
50
51
ecos_bb_pwork* work = ECOS_BB_setup(n, m, p, l, ncones, q,
52
Gpr, Gjc, Gir,
53
Apr, Ajc, Air,
54
c, h, b,
55
num_bool_vars, bool_vars_idx,
56
num_int_vars, int_vars_idx,
57
bb_settings);
58
```
59
60
### Mixed-Integer Problem Solving
61
62
Solves the mixed-integer optimization problem using branch-and-bound.
63
64
```c { .api }
65
idxint ECOS_BB_solve(ecos_bb_pwork* prob);
66
```
67
68
**Parameters:**
69
- `prob`: Mixed-integer solver workspace from ECOS_BB_setup
70
71
**Returns:** Exit code indicating solution status:
72
- `MI_OPTIMAL_SOLN` (0): Optimal integer solution found
73
- `MI_MAXITER_FEASIBLE_SOLN` (-1): Maximum iterations reached with feasible solution
74
- `MI_MAXITER_NO_SOLN` (1): Maximum iterations reached without feasible solution
75
- `MI_INFEASIBLE` (2): Problem is infeasible
76
77
**Usage Example:**
78
79
```c
80
idxint exitflag = ECOS_BB_solve(work);
81
82
switch (exitflag) {
83
case MI_OPTIMAL_SOLN:
84
printf("Optimal integer solution found\\n");
85
printf("Objective value: %f\\n", work->info->pcost);
86
87
// Access integer solution
88
for (int i = 0; i < work->ecos_prob->n; i++) {
89
printf("x[%d] = %f\\n", i, work->x[i]);
90
}
91
92
// Verify integer constraints
93
for (int i = 0; i < work->num_bool_vars; i++) {
94
idxint idx = work->bool_vars_idx[i];
95
printf("Boolean x[%d] = %f\\n", idx, work->x[idx]);
96
}
97
break;
98
99
case MI_MAXITER_FEASIBLE_SOLN:
100
printf("Feasible solution found (not proven optimal)\\n");
101
printf("Best objective: %f\\n", work->global_U);
102
printf("Lower bound: %f\\n", work->global_L);
103
printf("Gap: %f\\n", work->global_U - work->global_L);
104
break;
105
106
case MI_MAXITER_NO_SOLN:
107
printf("No feasible integer solution found\\n");
108
break;
109
110
case MI_INFEASIBLE:
111
printf("Problem is infeasible\\n");
112
break;
113
114
default:
115
printf("Unknown exit code: %d\\n", exitflag);
116
break;
117
}
118
```
119
120
### Mixed-Integer Memory Management
121
122
Frees mixed-integer solver workspace.
123
124
```c { .api }
125
void ECOS_BB_cleanup(ecos_bb_pwork* prob, idxint num_vars_keep);
126
```
127
128
**Parameters:**
129
- `prob`: Mixed-integer solver workspace to clean up
130
- `num_vars_keep`: Number of solution variables to preserve (0 = free all)
131
132
**Usage Example:**
133
134
```c
135
// Standard cleanup
136
ECOS_BB_cleanup(work, 0);
137
```
138
139
### Branch-and-Bound Settings
140
141
Gets default branch-and-bound configuration settings.
142
143
```c { .api }
144
settings_bb* get_default_ECOS_BB_settings();
145
```
146
147
**Returns:** Pointer to default settings structure
148
149
**Usage Example:**
150
151
```c
152
settings_bb* settings = get_default_ECOS_BB_settings();
153
154
// Customize settings
155
settings->maxit = 2000; // Increase max iterations
156
settings->abs_tol_gap = 1e-4; // Looser absolute gap tolerance
157
settings->rel_tol_gap = 1e-2; // Looser relative gap tolerance
158
settings->integer_tol = 1e-6; // Tighter integer feasibility
159
settings->verbose = 1; // Enable progress output
160
161
// Use custom settings
162
ecos_bb_pwork* work = ECOS_BB_setup(..., settings);
163
```
164
165
### Node Access Utilities
166
167
Utility functions for accessing branch-and-bound tree node data.
168
169
```c { .api }
170
static inline char* get_bool_node_id(idxint idx, ecos_bb_pwork* prob);
171
static inline pfloat* get_int_node_id(idxint idx, ecos_bb_pwork* prob);
172
```
173
174
**Parameters:**
175
- `idx`: Node index in the tree
176
- `prob`: Mixed-integer solver workspace
177
178
**Returns:** Pointer to node identifier arrays
179
180
**Usage Example:**
181
182
```c
183
// Access boolean variable assignments for a tree node
184
char* bool_assignments = get_bool_node_id(node_idx, work);
185
for (int i = 0; i < work->num_bool_vars; i++) {
186
printf("Bool var %d: %d\\n", i, bool_assignments[i]);
187
}
188
189
// Access integer variable bounds for a tree node
190
pfloat* int_bounds = get_int_node_id(node_idx, work);
191
for (int i = 0; i < work->num_int_vars; i++) {
192
printf("Int var %d: [%f, %f]\\n", i,
193
-int_bounds[2*i], int_bounds[2*i+1]);
194
}
195
```
196
197
## Branch-and-Bound Algorithm
198
199
The ECOS_BB solver implements a depth-first branch-and-bound search:
200
201
1. **Root Node**: Solve continuous relaxation of the original problem
202
2. **Branching**: For fractional integer variables, create two child nodes with added bounds
203
3. **Bounding**: Use continuous relaxation objective as lower bound
204
4. **Pruning**: Eliminate nodes that cannot improve the best known solution
205
5. **Integer Feasibility**: Check solutions against integer tolerance
206
207
### Boolean Variables
208
209
Boolean variables are constrained to take values in {0, 1}:
210
- Branch by setting variable ≤ 0 (effectively = 0) or ≥ 1 (effectively = 1)
211
- Integer feasibility checked with tolerance: |x - round(x)| ≤ integer_tol
212
213
### General Integer Variables
214
215
Integer variables are constrained to integer values:
216
- Branch by setting variable ≤ floor(x) or ≥ ceil(x)
217
- Support for bounded integer ranges through additional constraints
218
219
## Accessing Mixed-Integer Solution
220
221
After successful solve, solution data is available:
222
223
### Solution Variables
224
225
```c
226
// Best integer solution found
227
pfloat* x = work->x; // Primal variables
228
pfloat* y = work->y; // Equality multipliers
229
pfloat* z = work->z; // Inequality multipliers
230
pfloat* s = work->s; // Slack variables
231
232
// Objective bounds
233
pfloat best_obj = work->global_U; // Best feasible objective
234
pfloat lower_bound = work->global_L; // Best lower bound
235
```
236
237
### Solution Statistics
238
239
```c
240
stats* info = work->info;
241
printf("Best objective: %f\\n", info->pcost);
242
printf("Branch-and-bound iterations: %d\\n", work->iter);
243
244
// Access underlying ECOS statistics
245
stats* ecos_info = work->ecos_prob->info;
246
printf("Total ECOS solves: %d\\n", ecos_info->iter);
247
```
248
249
## Performance Considerations
250
251
- **Problem Size**: Best suited for problems with few integer variables (< 20)
252
- **Tree Depth**: Exponential growth with number of integer variables
253
- **Continuous Relaxation**: Should be tight for good performance
254
- **Tolerances**: Balance between solution accuracy and computational time
255
- **Warm Starting**: Each node uses previous solution as starting point
256
257
## Error Handling
258
259
Common issues and debugging:
260
261
```c
262
if (work == NULL) {
263
printf("Setup failed - check problem dimensions and data\\n");
264
return -1;
265
}
266
267
// Check for numerical issues in continuous relaxations
268
if (work->ecos_prob->info->iter >= work->ecos_prob->stgs->maxit) {
269
printf("Warning: ECOS hitting iteration limit\\n");
270
}
271
272
// Monitor branch-and-bound progress
273
if (work->stgs->verbose) {
274
printf("Gap: %f, Nodes explored: %d\\n",
275
work->global_U - work->global_L, work->iter);
276
}
277
```