diff options
author | 2020-06-25 19:55:10 +0200 | |
---|---|---|
committer | 2020-06-25 19:55:10 +0200 | |
commit | c3a6d4b9cf3657070d180aa65ddbf0459e880329 (patch) | |
tree | 780c4fc61578dcb309af53fb0c164c7627e51676 /Solvers/ILP-Solver/hu.bme.mit.inf.dslreasoner.ilp.cbc/cpp | |
parent | New configuration language parser WIP (diff) | |
parent | Scope unsat benchmarks (diff) | |
download | VIATRA-Generator-c3a6d4b9cf3657070d180aa65ddbf0459e880329.tar.gz VIATRA-Generator-c3a6d4b9cf3657070d180aa65ddbf0459e880329.tar.zst VIATRA-Generator-c3a6d4b9cf3657070d180aa65ddbf0459e880329.zip |
Merge branch 'kris'
Diffstat (limited to 'Solvers/ILP-Solver/hu.bme.mit.inf.dslreasoner.ilp.cbc/cpp')
3 files changed, 316 insertions, 0 deletions
diff --git a/Solvers/ILP-Solver/hu.bme.mit.inf.dslreasoner.ilp.cbc/cpp/CMakeLists.txt b/Solvers/ILP-Solver/hu.bme.mit.inf.dslreasoner.ilp.cbc/cpp/CMakeLists.txt new file mode 100644 index 00000000..6169ae8f --- /dev/null +++ b/Solvers/ILP-Solver/hu.bme.mit.inf.dslreasoner.ilp.cbc/cpp/CMakeLists.txt | |||
@@ -0,0 +1,23 @@ | |||
1 | cmake_minimum_required(VERSION 3.10.2) | ||
2 | project(hu.bme.mit.inf.dslreasoner.ilp.cbc) | ||
3 | |||
4 | set(CMAKE_CXX_STANDARD 14) | ||
5 | |||
6 | find_package(JNI REQUIRED) | ||
7 | find_package(PkgConfig REQUIRED) | ||
8 | |||
9 | pkg_check_modules(CBC REQUIRED cbc) | ||
10 | |||
11 | add_library(viatracbc SHARED viatracbc.cpp) | ||
12 | |||
13 | target_link_libraries(viatracbc | ||
14 | ${JAVA_JVM_LIBRARY} | ||
15 | ${CBC_LIBRARIES}) | ||
16 | target_include_directories(viatracbc | ||
17 | PUBLIC ${JNI_INCLUDE_DIRS} | ||
18 | PRIVATE ${CBC_INCLUDE_DIRS}) | ||
19 | |||
20 | set(VIATRACBC_NATIVES_DIR ${CMAKE_SOURCE_DIR}/../lib) | ||
21 | add_custom_command(TARGET viatracbc POST_BUILD | ||
22 | COMMAND ${CMAKE_COMMAND} -E make_directory ${VIATRACBC_NATIVES_DIR} | ||
23 | COMMAND ${CMAKE_COMMAND} -E copy $<TARGET_FILE:viatracbc> ${VIATRACBC_NATIVES_DIR}) | ||
diff --git a/Solvers/ILP-Solver/hu.bme.mit.inf.dslreasoner.ilp.cbc/cpp/viatracbc.cpp b/Solvers/ILP-Solver/hu.bme.mit.inf.dslreasoner.ilp.cbc/cpp/viatracbc.cpp new file mode 100644 index 00000000..34cab1dd --- /dev/null +++ b/Solvers/ILP-Solver/hu.bme.mit.inf.dslreasoner.ilp.cbc/cpp/viatracbc.cpp | |||
@@ -0,0 +1,277 @@ | |||
1 | |||
2 | #include <cmath> | ||
3 | #include <cstdlib> | ||
4 | #include <iostream> | ||
5 | #include <stdexcept> | ||
6 | |||
7 | #include <jni.h> | ||
8 | |||
9 | #include "CbcBranchDefaultDecision.hpp" | ||
10 | #include "CbcCompareDefault.hpp" | ||
11 | #include "CbcHeuristic.hpp" | ||
12 | #include "CbcHeuristicLocal.hpp" | ||
13 | #include "CbcModel.hpp" | ||
14 | #include "CglClique.hpp" | ||
15 | #include "CglFlowCover.hpp" | ||
16 | #include "CglGomory.hpp" | ||
17 | #include "CglKnapsackCover.hpp" | ||
18 | #include "CglMixedIntegerRounding.hpp" | ||
19 | #include "CglOddHole.hpp" | ||
20 | #include "CglProbing.hpp" | ||
21 | #include "CoinModel.hpp" | ||
22 | #include "OsiClpSolverInterface.hpp" | ||
23 | |||
24 | #include "viatracbc.hpp" | ||
25 | |||
26 | static const char *const kCbcExceptionClassName = "hu/bme/mit/inf/dslreasoner/ilp/cbc/CbcException"; | ||
27 | static const char *const kRuntimeExceptionClassName = "java/lang/RuntimeException"; | ||
28 | |||
29 | static const jint kCbcSolutionBounded = 0; | ||
30 | static const jint kCbcSolutionUnbounded = 1; | ||
31 | static const jint kCbcUnsat = 2; | ||
32 | static const jint kCbcAbandoned = 3; | ||
33 | static const jint kCbcTimeout = 4; | ||
34 | static const jint kCbcError = 5; | ||
35 | |||
36 | static CoinModel CreateModel(JNIEnv *env, jdoubleArray columnLowerBoundsArray, | ||
37 | jdoubleArray columnUpperBoundsArray, jintArray rowStartsArray, jintArray columnIndicesArray, | ||
38 | jdoubleArray entriedArray, jdoubleArray rowLowerBoundsArray, jdoubleArray rowUpperBoundsArray, | ||
39 | jdoubleArray objectiveArray, jboolean lpRelaxation); | ||
40 | static void CreateModelColumns(JNIEnv *env, jdoubleArray columnLowerBoundsArray, | ||
41 | jdoubleArray columnUpperBoundsArray, jdoubleArray objectiveArray, jboolean lpRelaxation, | ||
42 | CoinModel &build); | ||
43 | static void CreateModelRows(JNIEnv *env, jintArray rowStartsArray, jintArray columnIndicesArray, | ||
44 | jdoubleArray entriesArray, jdoubleArray rowLowerBoundsArray, jdoubleArray rowUpperBoundsArray, | ||
45 | CoinModel &build); | ||
46 | static jint SolveModel(CoinModel &build, jdouble timeoutSeconds, jboolean silent, jdouble &value); | ||
47 | static void ThrowException(JNIEnv *env, const char *message); | ||
48 | |||
49 | template < | ||
50 | typename Array, | ||
51 | typename Element, | ||
52 | Element *(JNIEnv::*GetElementsPtr)(Array, jboolean *), | ||
53 | void (JNIEnv::*ReleaseElementsPtr)(Array, Element *, jint) | ||
54 | > | ||
55 | class PinnedArray { | ||
56 | public: | ||
57 | PinnedArray(JNIEnv *env, Array array) | ||
58 | : env_{env}, array_{array}, elements_{(env->*GetElementsPtr)(array, nullptr)} { | ||
59 | if (elements_ == nullptr) { | ||
60 | throw std::runtime_error("Failed to pin array elements"); | ||
61 | } | ||
62 | } | ||
63 | PinnedArray(const PinnedArray &) = delete; | ||
64 | PinnedArray(PinnedArray &&) = delete; | ||
65 | PinnedArray &operator=(const PinnedArray &) = delete; | ||
66 | PinnedArray &operator=(PinnedArray &&) = delete; | ||
67 | ~PinnedArray() { | ||
68 | (env_->*ReleaseElementsPtr)(array_, elements_, 0); | ||
69 | } | ||
70 | |||
71 | operator Element *() { return elements_; } | ||
72 | operator const Element *() const { return elements_; } | ||
73 | |||
74 | private: | ||
75 | JNIEnv *env_; | ||
76 | Array array_; | ||
77 | Element *elements_; | ||
78 | }; | ||
79 | |||
80 | using PinnedIntArray = PinnedArray<jintArray, jint, &JNIEnv::GetIntArrayElements, &JNIEnv::ReleaseIntArrayElements>; | ||
81 | using PinnedDoubleArray = PinnedArray<jdoubleArray, jdouble, &JNIEnv::GetDoubleArrayElements, &JNIEnv::ReleaseDoubleArrayElements>; | ||
82 | |||
83 | jint Java_hu_bme_mit_inf_dslreasoner_ilp_cbc_CbcSolver_solveIlpProblem( | ||
84 | JNIEnv *env, jclass klazz, jdoubleArray columnLowerBoundsArray, jdoubleArray columnUpperBoundsArray, | ||
85 | jintArray rowStartsArray, jintArray columnIndicesArray, jdoubleArray entriesArray, | ||
86 | jdoubleArray rowLowerBoundsArray, jdoubleArray rowUpperBoundsArray, jdoubleArray objectiveArray, | ||
87 | jdoubleArray outputArray, jboolean lpRelaxation, jdouble timeoutSeconds, jboolean silent) { | ||
88 | try { | ||
89 | auto build = CreateModel(env, columnLowerBoundsArray, columnUpperBoundsArray, | ||
90 | rowStartsArray, columnIndicesArray, entriesArray, rowLowerBoundsArray, rowUpperBoundsArray, | ||
91 | objectiveArray, lpRelaxation); | ||
92 | double value; | ||
93 | jint result = SolveModel(build, timeoutSeconds, silent, value); | ||
94 | if (result == kCbcSolutionBounded) { | ||
95 | PinnedDoubleArray output{env, outputArray}; | ||
96 | *output = value; | ||
97 | } | ||
98 | return result; | ||
99 | } catch (const std::exception &e) { | ||
100 | ThrowException(env, e.what()); | ||
101 | } catch (...) { | ||
102 | ThrowException(env, "Unknown solver error"); | ||
103 | } | ||
104 | return kCbcError; | ||
105 | } | ||
106 | |||
107 | CoinModel CreateModel(JNIEnv *env, jdoubleArray columnLowerBoundsArray, | ||
108 | jdoubleArray columnUpperBoundsArray, jintArray rowStartsArray, jintArray columnIndicesArray, | ||
109 | jdoubleArray entriesArray, jdoubleArray rowLowerBoundsArray, jdoubleArray rowUpperBoundsArray, | ||
110 | jdoubleArray objectiveArray, jboolean lpRelaxation) { | ||
111 | CoinModel build; | ||
112 | CreateModelColumns(env, columnLowerBoundsArray, columnUpperBoundsArray, objectiveArray, | ||
113 | lpRelaxation, build); | ||
114 | CreateModelRows(env, rowStartsArray, columnIndicesArray, entriesArray, rowLowerBoundsArray, | ||
115 | rowUpperBoundsArray, build); | ||
116 | return build; | ||
117 | } | ||
118 | |||
119 | void CreateModelColumns(JNIEnv *env, jdoubleArray columnLowerBoundsArray, | ||
120 | jdoubleArray columnUpperBoundsArray, jdoubleArray objectiveArray, jboolean lpRelaxation, | ||
121 | CoinModel &build) { | ||
122 | int numColumns = env->GetArrayLength(columnLowerBoundsArray); | ||
123 | PinnedDoubleArray columnLowerBounds{env, columnLowerBoundsArray}; | ||
124 | PinnedDoubleArray columnUpperBounds{env, columnUpperBoundsArray}; | ||
125 | PinnedDoubleArray objective{env, objectiveArray}; | ||
126 | for (int i = 0; i < numColumns; i++) { | ||
127 | build.setColumnBounds(i, columnLowerBounds[i], columnUpperBounds[i]); | ||
128 | build.setObjective(i, objective[i]); | ||
129 | if (!lpRelaxation) { | ||
130 | build.setInteger(i); | ||
131 | } | ||
132 | } | ||
133 | } | ||
134 | |||
135 | void CreateModelRows(JNIEnv *env, jintArray rowStartsArray, jintArray columnIndicesArray, | ||
136 | jdoubleArray entriesArray, jdoubleArray rowLowerBoundsArray, jdoubleArray rowUpperBoundsArray, | ||
137 | CoinModel &build) { | ||
138 | int numRows = env->GetArrayLength(rowLowerBoundsArray); | ||
139 | PinnedIntArray rowStarts{env, rowStartsArray}; | ||
140 | PinnedIntArray columnIndices{env, columnIndicesArray}; | ||
141 | PinnedDoubleArray entries{env, entriesArray}; | ||
142 | PinnedDoubleArray rowLowerBounds{env, rowLowerBoundsArray}; | ||
143 | PinnedDoubleArray rowUpperBounds{env, rowUpperBoundsArray}; | ||
144 | for (int i = 0; i < numRows; i++) { | ||
145 | int rowStart = rowStarts[i]; | ||
146 | int numbersInRow = rowStarts[i + 1] - rowStart; | ||
147 | build.addRow(numbersInRow, &columnIndices[rowStart], &entries[rowStart], | ||
148 | rowLowerBounds[i], rowUpperBounds[i]); | ||
149 | } | ||
150 | } | ||
151 | |||
152 | jint SolveModel(CoinModel &build, jdouble timeoutSeconds, jboolean silent, jdouble &value) { | ||
153 | OsiClpSolverInterface solver; | ||
154 | solver.loadFromCoinModel(build); | ||
155 | CbcModel model{solver}; | ||
156 | |||
157 | if (timeoutSeconds >= 0) { | ||
158 | model.setDblParam(CbcModel::CbcMaximumSeconds, timeoutSeconds); | ||
159 | } | ||
160 | if (silent == JNI_FALSE) { | ||
161 | model.messageHandler()->setLogLevel(2); | ||
162 | model.solver()->messageHandler()->setLogLevel(1); | ||
163 | } else { | ||
164 | model.solver()->setHintParam(OsiDoReducePrint, true, OsiHintTry); | ||
165 | model.messageHandler()->setLogLevel(0); | ||
166 | model.solver()->messageHandler()->setLogLevel(0); | ||
167 | } | ||
168 | |||
169 | // Cut generators and heuristics are used according to | ||
170 | // https://github.com/coin-or/Cbc/blob/6b977b6707f1755520c64fea57b95891c1f3ddc0/Cbc/examples/sample2.cpp | ||
171 | |||
172 | CglProbing probing; | ||
173 | probing.setUsingObjective(true); | ||
174 | probing.setMaxPass(1); | ||
175 | probing.setMaxPassRoot(5); | ||
176 | probing.setMaxProbe(10); | ||
177 | probing.setMaxProbeRoot(1000); | ||
178 | probing.setMaxLook(50); | ||
179 | probing.setMaxLookRoot(500); | ||
180 | probing.setMaxElements(200); | ||
181 | probing.setRowCuts(3); | ||
182 | model.addCutGenerator(&probing, -1, "Probing"); | ||
183 | |||
184 | CglGomory gomory; | ||
185 | gomory.setLimit(300); | ||
186 | model.addCutGenerator(&gomory, -1, "Gomory"); | ||
187 | |||
188 | CglKnapsackCover knapsackCover; | ||
189 | model.addCutGenerator(&knapsackCover, -1, "KnapsackCover"); | ||
190 | |||
191 | CglClique clique; | ||
192 | clique.setStarCliqueReport(false); | ||
193 | clique.setRowCliqueReport(false); | ||
194 | model.addCutGenerator(&clique, -1, "Clique"); | ||
195 | |||
196 | CglFlowCover flowCover; | ||
197 | model.addCutGenerator(&flowCover, -1, "FlowCover"); | ||
198 | |||
199 | CglMixedIntegerRounding mixedIntegerRounding; | ||
200 | model.addCutGenerator(&mixedIntegerRounding, -1, "MixedIntegerRounding"); | ||
201 | |||
202 | OsiClpSolverInterface *osiClp = dynamic_cast<OsiClpSolverInterface *>(model.solver()); | ||
203 | if (osiClp != nullptr) { | ||
204 | osiClp->setSpecialOptions(128); | ||
205 | osiClp->setupForRepeatedUse(0, 0); | ||
206 | } | ||
207 | |||
208 | CbcRounding rounding; | ||
209 | model.addHeuristic(&rounding); | ||
210 | |||
211 | CbcHeuristicLocal localHeuristic; | ||
212 | model.addHeuristic(&localHeuristic); | ||
213 | |||
214 | CbcBranchDefaultDecision branchDecision; | ||
215 | model.setBranchingMethod(&branchDecision); | ||
216 | |||
217 | CbcCompareDefault nodeComparison; | ||
218 | model.setNodeComparison(nodeComparison); | ||
219 | |||
220 | model.initialSolve(); | ||
221 | |||
222 | if (model.isInitialSolveProvenPrimalInfeasible()) { | ||
223 | return kCbcUnsat; | ||
224 | } | ||
225 | if (model.isInitialSolveProvenDualInfeasible()) { | ||
226 | return kCbcSolutionUnbounded; | ||
227 | } | ||
228 | if (model.isInitialSolveAbandoned()) { | ||
229 | return kCbcTimeout; | ||
230 | } | ||
231 | |||
232 | model.setMinimumDrop(CoinMin(1.0, fabs(model.getMinimizationObjValue()) * 1.0e-3 + 1.0e-4)); | ||
233 | model.setMaximumCutPassesAtRoot(-100); | ||
234 | model.setNumberStrong(10); | ||
235 | model.solver()->setIntParam(OsiMaxNumIterationHotStart, 100); | ||
236 | |||
237 | model.branchAndBound(); | ||
238 | |||
239 | switch (model.status()) { | ||
240 | case 0: | ||
241 | if (model.isProvenInfeasible()) { | ||
242 | return kCbcUnsat; | ||
243 | } | ||
244 | if (model.isProvenDualInfeasible()) { | ||
245 | return kCbcSolutionUnbounded; | ||
246 | } | ||
247 | if (model.isProvenOptimal()) { | ||
248 | value = model.getMinimizationObjValue(); | ||
249 | return kCbcSolutionBounded; | ||
250 | } | ||
251 | throw std::runtime_error("CBC status is 0, but no solution is found"); | ||
252 | case 1: | ||
253 | return kCbcTimeout; | ||
254 | case 2: | ||
255 | return kCbcAbandoned; | ||
256 | default: | ||
257 | throw std::runtime_error("Unknown CBC status"); | ||
258 | } | ||
259 | } | ||
260 | |||
261 | void ThrowException(JNIEnv *env, const char *message) { | ||
262 | jclass exceptionClass = env->FindClass(kCbcExceptionClassName); | ||
263 | if (exceptionClass == nullptr) { | ||
264 | std::cerr << "WARNING: " << kCbcExceptionClassName << " class was not found" << std::endl; | ||
265 | exceptionClass = env->FindClass(kRuntimeExceptionClassName); | ||
266 | if (exceptionClass == nullptr) { | ||
267 | std::cerr << "FATAL: " << kRuntimeExceptionClassName << " class was not found" << std::endl; | ||
268 | std::cerr << "FATAL: " << message << std::endl; | ||
269 | std::exit(EXIT_FAILURE); | ||
270 | } | ||
271 | } | ||
272 | if (env->ThrowNew(exceptionClass, message) < 0) { | ||
273 | std::cerr << "FATAL: Could not throw java exception" << std::endl; | ||
274 | std::cerr << "FATAL: " << message << std::endl; | ||
275 | std::exit(EXIT_FAILURE); | ||
276 | } | ||
277 | } | ||
diff --git a/Solvers/ILP-Solver/hu.bme.mit.inf.dslreasoner.ilp.cbc/cpp/viatracbc.hpp b/Solvers/ILP-Solver/hu.bme.mit.inf.dslreasoner.ilp.cbc/cpp/viatracbc.hpp new file mode 100644 index 00000000..12198c8b --- /dev/null +++ b/Solvers/ILP-Solver/hu.bme.mit.inf.dslreasoner.ilp.cbc/cpp/viatracbc.hpp | |||
@@ -0,0 +1,16 @@ | |||
1 | #ifndef HU_BME_MIT_INF_DSLREASONER_ILP_CBC_ | ||
2 | #define HU_BME_MIT_INF_DSLREASONER_ILP_CBC_ | ||
3 | |||
4 | #include <jni.h> | ||
5 | |||
6 | extern "C" { | ||
7 | |||
8 | JNIEXPORT jint JNICALL Java_hu_bme_mit_inf_dslreasoner_ilp_cbc_CbcSolver_solveIlpProblem( | ||
9 | JNIEnv *env, jclass klazz, jdoubleArray columnLowerBoundsArray, jdoubleArray columnUpperBoundsArray, | ||
10 | jintArray rowStartsArray, jintArray columnIndicesArray, jdoubleArray entriesArray, | ||
11 | jdoubleArray rowLowerBoundsArray, jdoubleArray rowUpperBoundsArray, jdoubleArray objectiveArray, | ||
12 | jdoubleArray outputArray, jboolean lpRelaxation, jdouble timeoutSeconds, jboolean silent); | ||
13 | |||
14 | } | ||
15 | |||
16 | #endif // HU_BME_MIT_INF_DSLREASONER_ILP_CBC_ | ||