-
Notifications
You must be signed in to change notification settings - Fork 123
/
ecos_bb.h
244 lines (203 loc) · 6.53 KB
/
ecos_bb.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
/*
* ECOS - Embedded Conic Solver.
* Copyright (C) 2012-2015 A. Domahidi [domahidi@embotech.com],
* Automatic Control Lab, ETH Zurich & embotech GmbH, Zurich, Switzerland.
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
/*
* The branch and bound module is (c) Han Wang, Stanford University,
* [hanwang2@stanford.edu]
*
* Extended with improved branching rules by Pascal Lüscher, student of FHNW
* [luescherpascal@gmail.com]
*/
#ifndef __ecos_bb_H__
#define __ecos_bb_H__
#include "ecos.h"
#include "spla.h"
#include "glblopts.h"
/* Print verbosity */
#define MI_PRINTLEVEL (1)
/* ecos_bb configuration settings */
#define MI_ABS_EPS (1E-6)
#define MI_REL_EPS (1E-3)
#define MI_MAXITER (1000)
#define MI_INT_TOL (FTOL_INACC)
/* Flags */
#define MI_SOLVED_NON_BRANCHABLE (3)
#define MI_SOLVED_BRANCHABLE (2)
#define MI_NOT_SOLVED (1)
#define MI_FREE (0)
#define MI_ONE (1)
#define MI_ZERO (0)
#define MI_STAR (-1)
/*** Exit flags ***/
/*ECOS_BB found optimal solution*/
#define MI_OPTIMAL_SOLN (ECOS_OPTIMAL)
/*ECOS_BB proved problem is infeasible*/
#define MI_INFEASIBLE (ECOS_PINF)
/*ECOS_BB proved problem is unbounded*/
#define MI_UNBOUNDED (ECOS_DINF)
/*ECOS_BB hit maximum iterations but a feasible solution was found and the best seen feasible solution was returned*/
#define MI_MAXITER_FEASIBLE_SOLN (ECOS_OPTIMAL + ECOS_INACC_OFFSET)
/*ECOS_BB hit maximum iterations without finding a feasible solution*/
#define MI_MAXITER_NO_SOLN (ECOS_PINF + ECOS_INACC_OFFSET)
/*ECOS_BB hit maximum iterations without finding a feasible solution that was unbounded*/
#define MI_MAXITER_UNBOUNDED (ECOS_DINF + ECOS_INACC_OFFSET)
/* Max integer and all smaller integer representable by single precision */
#define MAX_FLOAT_INT (8388608)
#ifdef __cplusplus
extern "C"
{
#endif
enum BRANCHING_STRATEGY
{
BRANCHING_STRATEGY_MOST_INFEASIBLE = 0,
BRANCHING_STRATEGY_STRONG_BRANCHING = 1,
BRANCHING_STRATEGY_PSEUDOCOST_BRANCHING = 2,
BRANCHING_STRATEGY_RELIABILITY = 3,
BRANCHING_STRATEGY_RANDOM = 4
};
enum NODE_SELECTION_METHOD
{
BREADTH_FIRST = 0,
DIVE_LOWER_NODE = 1,
DIVE_UPPER_NODE = 2,
};
typedef struct settings_bb
{
idxint maxit; /* maximum number of iterations */
idxint verbose; /* verbosity bool for PRINTLEVEL < 3 */
pfloat abs_tol_gap; /* termination criteria |U-L| */
pfloat rel_tol_gap; /* termination criteria for |U-L|/|L| < 3 */
pfloat integer_tol; /* integer rounding tolerance */
enum BRANCHING_STRATEGY branching_strategy;
idxint reliable_eta; /* number of pseudocost values needed for costs to be reliable */
enum NODE_SELECTION_METHOD node_selection_method;
} settings_bb;
typedef struct node
{
char status;
pfloat L;
pfloat U;
pfloat relaxation;
idxint split_idx;
pfloat split_val;
idxint prev_split_idx;
pfloat prev_split_val;
pfloat prev_relaxation;
int up_branch_node;
} node;
/* Wrapper for mixed integer module */
typedef struct ecos_bb_pwork
{
/* Mixed integer data */
idxint num_bool_vars;
idxint num_int_vars;
node *nodes;
char *bool_node_ids;
pfloat *int_node_ids;
idxint *bool_vars_idx;
idxint *int_vars_idx;
/* ECOS data */
pwork *ecos_prob;
/* Modified pointers to ecos internals */
/* Use these to edit or reset the h variables */
spmat *A;
spmat *G;
pfloat *c;
pfloat *b;
pfloat *h;
/* best iterate seen so far */
/* variables */
pfloat *x; /* primal variables */
pfloat *y; /* multipliers for equality constaints */
pfloat *z; /* multipliers for conic inequalities */
pfloat *s; /* slacks for conic inequalities */
pfloat kap; /* kappa (homogeneous embedding) */
pfloat tau; /* tau (homogeneous embedding) */
stats *info; /* info of best iterate */
pfloat global_U;
pfloat global_L;
/* Tmp data */
char *tmp_bool_node_id;
pfloat *tmp_int_node_id;
idxint iter;
idxint dive_node_id;
/* Tmp nodes used for strong branching */
char *tmp_branching_bool_node_id;
pfloat *tmp_branching_int_node_id;
/* Pseudocost branching values */
pfloat *pseudocost_bin_sum;
pfloat *pseudocost_int_sum;
idxint *pseudocost_bin_cnt;
idxint *pseudocost_int_cnt;
/* Stored pointers to prevent memory leaks */
pfloat *Gpr_new;
idxint *Gjc_new;
idxint *Gir_new;
pfloat *h_new;
/* settings struct */
settings *ecos_stgs;
settings_bb *stgs;
idxint default_settings;
} ecos_bb_pwork;
ecos_bb_pwork *ECOS_BB_setup(
idxint n, idxint m, idxint p,
idxint l, idxint ncones, idxint *q, idxint nex,
pfloat *Gpr, idxint *Gjc, idxint *Gir,
pfloat *Apr, idxint *Ajc, idxint *Air,
pfloat *c, pfloat *h, pfloat *b,
idxint num_bool_vars, idxint *bool_vars_idx,
idxint num_int_vars, idxint *int_vars_idx,
settings_bb *stgs);
idxint ECOS_BB_solve(ecos_bb_pwork *prob);
void ECOS_BB_cleanup(ecos_bb_pwork *prob, idxint num_vars_keep);
void updateDataEntry_h(ecos_bb_pwork *w, idxint idx, pfloat value);
void updateDataEntry_c(ecos_bb_pwork *w, idxint idx, pfloat value);
settings_bb *get_default_ECOS_BB_settings();
/* Calculate the offset into the node_id array */
static char *get_bool_node_id(idxint idx, ecos_bb_pwork *prob)
{
return &prob->bool_node_ids[prob->num_bool_vars * idx];
}
static pfloat *get_int_node_id(idxint idx, ecos_bb_pwork *prob)
{
return &prob->int_node_ids[prob->num_int_vars * idx * 2];
}
static pfloat abs_2(pfloat number)
{
return number < 0.0 ? -number : number;
}
static pfloat pfloat_round(pfloat number)
{
return (number >= 0) ? (int)(number + 0.5) : (int)(number - 0.5);
}
static pfloat pfloat_ceil(pfloat number, pfloat integer_tol)
{
return (pfloat)(number < 0 ? (int)number : (int)(number + (1 - integer_tol)));
}
static pfloat pfloat_floor(pfloat number, pfloat integer_tol)
{
return (pfloat)(number < 0 ? (int)(number - (1 - integer_tol)) : (int)number);
}
static idxint float_eqls(pfloat a, pfloat b, pfloat integer_tol)
{
return abs_2(a - b) < integer_tol;
}
#ifdef __cplusplus
}
#endif
#endif