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
|
/*
* 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]
*/
#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)
/* define INFINITY and isinf for MSFT */
#ifdef _MSC_VER
#include "float.h"
#define INFINITY (DBL_MAX+DBL_MAX)
/* this will also return true if x is nan, but we don't check that anyway */
#define isinf(x) (!_finite(x))
#endif
#ifdef __cplusplus
extern "C" {
#endif
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 */
} settings_bb;
typedef struct node {
char status;
pfloat L;
pfloat U;
idxint split_idx;
pfloat split_val;
} 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;
/* 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 inline char* get_bool_node_id(idxint idx, ecos_bb_pwork* prob){
return &prob->bool_node_ids[prob->num_bool_vars * idx];
}
static inline pfloat* get_int_node_id(idxint idx, ecos_bb_pwork* prob){
return &prob->int_node_ids[prob->num_int_vars * idx * 2];
}
static inline pfloat abs_2(pfloat number){
return number < 0.0 ? -number : number;
}
static inline pfloat pfloat_round(pfloat number){
return (number >= 0) ? (int)(number + 0.5) : (int)(number - 0.5);
}
static inline pfloat pfloat_ceil(pfloat number, pfloat integer_tol){
return (pfloat) (number < 0 ? (int) number : (int) (number+(1-integer_tol)) );
}
static inline pfloat pfloat_floor(pfloat number, pfloat integer_tol){
return (pfloat) (number < 0 ? (int) (number-(1-integer_tol)) : (int) number);
}
static inline idxint float_eqls(pfloat a, pfloat b, pfloat integer_tol){
return abs_2(a - b) < integer_tol;
}
#ifdef __cplusplus
}
#endif
#endif
|
