Scippy

UG

Ubiquity Generator framework

xternal.cpp
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and software framework */
4/* UG --- Ubquity Generator Framework */
5/* */
6/* Copyright Written by Yuji Shinano <shinano@zib.de>, */
7/* Copyright (C) 2021-2024 by Zuse Institute Berlin, */
8/* licensed under LGPL version 3 or later. */
9/* Commercial licenses are available through <licenses@zib.de> */
10/* */
11/* This code is free software; you can redistribute it and/or */
12/* modify it under the terms of the GNU Lesser General Public License */
13/* as published by the Free Software Foundation; either version 3 */
14/* of the License, or (at your option) any later version. */
15/* */
16/* This program is distributed in the hope that it will be useful, */
17/* but WITHOUT ANY WARRANTY; without even the implied warranty of */
18/* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
19/* GNU Lesser General Public License for more details. */
20/* */
21/* You should have received a copy of the GNU Lesser General Public License */
22/* along with this program. If not, see <http://www.gnu.org/licenses/>. */
23/* */
24/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
25
26/**@file xternal.cpp
27 * @brief main document page
28 * @author Yuji Shinano
29 * @author Franziska Schloesser
30 *
31 *
32 */
33
34/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35
36/** @mainpage Overview
37 *
38 * @tableofcontents
39 *
40 * @section WHATISUG What is UG?
41 *
42 * \UG is originally a framework to parallelize state-of-the-art branch-and-bound based solvers to solve optimization problems such
43 * as constraint integer programs (CIPs) and mixed-integer (non-)linear programs. In particular
44 *
45 * - \UG incorporates a mixed-integer programming (MIP) solver as well as
46 * - an LP based mixed-integer nonlinear programming (MINLP) solver, and
47 * - is a framework for branch-and-cut-and-price programs.
48 *
49 * \UG is a high-level task parallelization framework that is generalized, that means it can also handle both branch-and-bound-based and non-branch-and-bound based solvers starting from \UG version 1.0.
50 *
51 * See the web site <a href="http://ug.zib.de">ug.zib.de</a> for more information about licensing and to download the recent release.
52 *
53 *
54 * @section TABLEOFCONTENTS Structure of this manual
55 *
56 * This manual gives an accessible introduction to the functionality of the UG code in the following chapters
57 *
58 * - @subpage GETTINGSTARTED Installation and license information and an interactive shell tutorial
59 * - @subpage PARAMETERS List of all UG parameters
60 * - @subpage PROGRAMMING Important programming concepts for working with(in) UG.
61 * - @subpage AUTHORS UG Authors
62 * - @subpage CONCEPT Concept of UG's high-level task parallelization framework
63 * - @subpage QUICKSTART Quickstart
64 * - @subpage DOC How to search the documentation for interface methods
65 * - @subpage HIERARCHYDIRS Classes hierarchy and source code directory organization
66 * - @subpage CODE Coding style guidelines
67 * - @subpage DEBUG Debugging
68 *
69 *
70 * @page CONCEPT Concept of UG's high-level task parallelization framework
71 *
72 * One of the most famous high-level task parallelization frameworks would be one that follows the \b Master-Worker paradigm:
73 * A \b Task represents an operation that is running on a \b Worker.
74 * In this context, the word \e high-level means that the \e granularity of the \b Task is coarse.
75 * The words \b Task and its granularity are generally used in the field of parallel programming,
76 * where the granularity indicates how much computation is needed to process one \b Task.
77 *
78 * \UG is a high-level task parallelization framework following the \b Supervisor-Worker paradigm:
79 * From the configuration point of view, \UG is composed by the two elements \b LoadCoordinator and \b Solvers,
80 * where the \b LoadCoordinator is the \b Supervisor and a \b Solver is a \b Worker.
81 * In the UG's high-level task parallelization framework, the goal is to parallelize a state-of-the-art single-threaded or multi-threaded \b Solver,
82 * in which the \b Task operation is very much complicated and is processed by a large number of lines of code.
83 * For example, a Mixed Integer Programming problem (MIP) solver was the initial main target.
84 * In that case, a \b Task is a (sub-)MIP.
85 *
86 * To understand \UG, the concepts of \b Master-Worker and \b Supervisor-Worker are compared
87 * using the example of the way a parallel Branch-and-bound solver works.
88 *
89 * @section PARADIGMMASTERWORKER "Master-Worker paradigm"
90 *
91 * In the \b Master-Worker paradigm, the communication is very simple, the key messages are:
92 * - \b Task : contains task information, such as a (sub-)problem representation and current best incumbent value
93 * - \b Result : contains all information regarding the task execution. In the case of a parallel MIP solver, the best incumbent solution and all open nodes as examples.
94 *
95 * \image html Master-Worker.png "A parallel MIP solver based on the Master-Worker paradigm" width=500px
96 * \image latex Master-Worker.png "A parallel MIP solver based on the Master-Worker paradigm" width=500px
97 *
98 * The \b granularity of a Task can be controlled in the Worker by a termination criterion for a (sub-)problem computation,
99 * such as the number of open nodes generated.
100 * Note that all open branch-and-bound nodes are managed by the Master side and the number of transferred nodes is huge in case the solution process
101 * generates a huge search tree.
102 * In order to reduce the number of open nodes, usually depth-first search is used in the Worker side.
103 * An advantage is that the all nodes in the Master are independent, that is, all nodes can be a (sub-)problem root.
104 * This fact allows for a simple checkpoint and restart mechanism, that can fully save and resume the tree search.
105 * This loosely coupled Master-Worker paradigm is very well suitable for high-throughput computing,
106 * but is not so efficient in large-scale high-performance computing.
107 *
108 * @section PARADIGMSUPERVISORWORKER "Supervisor-Worker paradigm"
109 *
110 * Different from the previously explained Master-Worker paradigm, the \b Supervisor-Worker paradigm used in UG's high-level task
111 * parallelization framework defines a very flexible message passing protocol.
112 * The key messages are:
113 * - \b Task : contains task information, such as a (sub-)problem representation, and it indicates the beginning of the Task computation.
114 * - \b Status : contains the Task computation status and the nitification frequency to Supervisor, which can be specified at run-time.
115 * - \b Completion : indicates the termination of the task computation.
116 *
117 * In between the \b Task and \b Completion messages, any message passing protocol can be defined, for example
118 * - \b Solution : represents the best incumbent solution. Then, the solution can be share whenever a single Solver found a new one.
119 * - \b InCollecting : indicates that the Supervisor needs new Tasks. This message allows to collect (sub-)problems on demand.
120 * - \b OutCollecting : indicates that the Supervisor does not need new Tasks.
121 * - \b Interrupt : indicates the current executing Task can be interrupted
122 * - etc.
123 *
124 * \image html Supervisor-Worker.png "A parallel MIP solver based on Supervisor-Worker" width=500px
125 * \image latex Supervisor-Worker.png "A parallel MIP solver based on Supervisor-Worker" width=500px
126 *
127 * The \b LoadCoordinator manages and does a dynamic load balancing among \b Solvers.
128 * However, the \b LoadCoordinaor only keeps root (sub-)problem nodes at run-time.
129 * For checkpoints, an even smaller number of only essential nodes are saved.
130 * These essential nodes are checking relation among the root nodes, that is, if its ancestor node exits.
131 * If it does exist, then the node does not have to be saved, since it can be regenerated from its ancestor.
132 * This looks inefficient, but in a state-of-the-art MIP solver, it sometimes works very well
133 * (see <a href="https://ieeexplore.ieee.org/document/6969561">
134 * Solving Hard MIPLIB2003 Problems with ParaSCIP on Supercomputers: An Update</a>).
135 * For Supervisor-Worker, see
136 * <a href="https://link.springer.com/chapter/10.1007/978-3-319-63516-3_8">
137 * Parallel Solvers for Mixed Integer Linear Optimization</a> in more detailed.
138 *
139 * UG can flexibly define the message passing protocol in between \b Task and \b Completion.
140 *
141 * The key feature of UG's high-level Task parallelization framework is the above described flexible message passing protocol
142 * during a \b Task computation.
143 *
144 *
145 * @page QUICKSTART Quickstart
146 *
147 * The stand-alone shared memory parallel MIP/MINLP solver FiberSCIP can be used easily via the `fscip` command.
148 * Let's consider the following minimal example in LP format,
149 * a 4-variable problem with a single, general integer variable and three linear constraints:
150 *
151 * \verbinclude simple.lp
152 *
153 * Saving this file as "simple.lp" allows to read it into FiberSCIP.
154 * Create a default parameter file for FiberSCIP:
155 *
156 * \verbinclude default.prm
157 *
158 * The column starting with "#" is treated as a comment.
159 * Therefore, this parameter file contains all default settings.
160 * Save this file as "default.prm" and solve "simple.lp" with these settings by running the command:
161 *
162 * ```
163 * fscip default.prm simple.lp -q
164 * ```
165 *
166 * This model is solved by using the maximal number of cores on your PC:
167 *
168 * \verbinclude output.log
169 *
170 * The solution file "sample.sol" will be written as below:
171 *
172 * \verbinclude simple.sol
173 *
174 */
175
176/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
177
178/**@page GETTINGSTARTED Getting started
179 *
180 * - @subpage WHATPROBLEMS "What types of optimization problems does UG solve?"
181 *
182 * - @subpage LICENSE "License"
183 * - @subpage INSTALL "Installation"
184 * - @subpage DOC "How to search the documentation for interface methods"
185 */
186
187/**@page PARAMETERS List of all UG parameters
188 *
189 * This page lists all parameters of the current UG version.
190 * It can easily be generated running FiberSCIP with the following parameters:
191 *
192 * <code>Quiet = FALSE</code><br>
193 * <code>OutputParaParams = 4</code>
194 *
195 * \verbinclude parameters.prm
196 *
197 *
198 */
199
200/**@page PROGRAMMING Programming with UG
201 *
202 * The UG high-level task parallelization framework provides a systematic way to develop a massively parallel solver,
203 * that can run on large scale supercomputers.
204 *
205 * 1. develop and debug a stand-alone \b Solver, if the \b Solver does not exit.
206 * 2. develop and debug a shared-memory parallel solver, in which \b Solvers are managed by \b LoadCoordinator.
207 * 3. develop and debug a distributed-memory parallel solver, in which \b Solvers are managed by \b LoadCoordinator.
208 *
209 * Note that, algorithmically, 2 and 3 work the same.
210 * Therefore, a massively parallel solver can be developed on a PC.
211 *
212 * - @subpage HIERARCHYDIRS "Classes hierarchy and source code directory organization"
213 * - @subpage CODE "Coding style guidelines"
214 * - @subpage DEBUG "Debugging"
215 */
216
217/**@page AUTHORS UG Authors
218 *
219 * The current main developer is Yuji Shinano.
220 *
221 */
222
223/**@page WHATPROBLEMS What types of optimization problems does UG solve?
224 *
225 * \UG, as a stand-alone solver using \b SCIP as the underlying base solver,
226 * is called FiberSCIP and ParaSCIP can solve mixed-integer linear and nonlinear programs.
227 * For solving \b MINLP it applies an LP based spatial branch-and-cut algorithm,
228 * that is guaranteed to solve bounded MINLPs within a given numerical tolerance in a finite amount of time.
229 *
230 * The \b SCIP applications
231 *
232 * - \b STP (Steiner Tree Problem) and its applications, also known as \b SCIP-Jack, and
233 * - \b MISDPs (mixed integer semidefinite programs) provided by \b SCIP-SDP,
234 *
235 * are parallelized by \UG. They can be solved as stand-alone \UG applications.
236 *
237 * Any branch-and-bound based solver for a specific problem, which is realized
238 * by \b SCIP plugins, can easily parallelized by adding a small lines of glue code.
239 *
240 * (see, <a href="https://ieeexplore.ieee.org/document/8778206">
241 * An Easy Way to Build Parallel State-of-the-art Combinatorial Optimization Problem Solvers:
242 * A Computational Study on Solving Steiner Tree Problems and Mixed Integer Semidefinite Programs
243 * by using ug[SCIP-*,*]-Libraries</a>)
244 *
245 * In the \UG framework, the underlying base solver is abstracted.
246 * By adding the \UG wrapper code etc. for a specific optimization problem,
247 * a massively parallel solver for the problem can be built.
248 * Ongoing projects are the following:
249 * - Quadratic Assignment Problem (\b QAP):
250 * DNN relaxation with Newton Bracket method based branch-and-bound solver is parallelized
251 * (see, <a href="https://arxiv.org/abs/2101.09629">Solving Challenging Large Scale QAPs</a>).
252 * - Traveling Salesman Problem (\b TSP): <a href="http://www.math.uwaterloo.ca/tsp/concorde.html">
253 * Concorde TSP solver</a> has been parallelized by \UG.
254 * - \b MIP: Another MIP solver, in which multi-threaded FICO Xpress solver is used as underlying base solver
255 * (see, <a href="https://www.tandfonline.com/doi/abs/10.1080/10556788.2018.1428602?journalCode=goms20">ParaXpress: an experimental extension of the FICO Xpress-Optimizer to solve hard MIPs on supercomputers</a>).
256 *
257 * Also, \UG version 1.0 can be used to parallelize non-branch-and-bound based solvers:
258 * A Shortest Vector Problem (\b SVP : see <a href="https://www.latticechallenge.org/svp-challenge/">
259 * SVP Challenge</a>) solver has been parallelized by \UG.
260 *
261 *
262 *
263 *
264 *
265 */
266
267/**@page LICENSE License
268 *
269 * \verbinclude COPYING
270 */
271
272/**@page INSTALL Installing UG
273 *
274 * This chapter is a detailed guide to the installation procedure of UG.
275 *
276 * UG lets you freely choose between its own, manually maintained Makefile system
277 * or the CMake cross platform build system generator. For new users, we strongly
278 * recommend to use CMake, if available on their targeted platform.
279 *
280 * - @subpage CMAKE "Installation information using CMake (recommended for new users)"
281 * - @subpage MAKE "Installation information using Makefiles (deprecated)"
282 */
283
284/**@page CMAKE Building UG with CMake
285 *
286 * <a href=https://cmake.org/>CMake</a> is a build system generator that can create, e.g., Makefiles for UNIX and Mac
287 * or Visual Studio project files for Windows.
288 *
289 * CMake provides an <a href="https://cmake.org/cmake/help/latest/manual/cmake.1.html">extensive documentation</a>
290 * explaining available features and use cases as well as an <a href="https://cmake.org/Wiki/CMake_FAQ">FAQ section</a>.
291 * It's recommended to use the latest stable CMake version available. `cmake --help` is also a good first step to see
292 * available options and usage information.
293 *
294 * Platform independent build instructions:
295 *
296 * ```
297 * cmake -Bbuild -H. [-DSCIP_DIR=/path/to/scip]
298 * cmake --build build
299 * ```
300 *
301 * Linux/macOS Makefile-based build instructions:
302 *
303 * ```
304 * mkdir build
305 * cd build
306 * cmake ..
307 * make
308 * ```
309 *
310 * CMake uses an out-of-source build, i.e., compiled binaries and object files are separated from the source tree and
311 * located in another directory. Usually this directory is called `build` or `debug` or whatever you prefer. From within
312 * this directory, run `cmake <path/to/UG>` to configure your build, followed by `make` to compile the code according
313 * to the current configuration (this assumes that you chose Linux Makefiles as CMake Generator). By default, UG
314 * searches for SCIP as base solver. If SCIP is not installed systemwide, the path to a CMake build directory
315 * of SCIP must be specified (ie one that contains "scip-config.cmake").
316 *
317 * Afterwards, successive calls to `make` are going to recompile modified source code,
318 * without requiring another call to `cmake`.
319 *
320 * The generated executable and libraries are put in directories `bin` and `lib` respectively and will simply be named `fscip`.
321 *
322 * @section CMAKE_CONFIG Modifying a CMake configuration
323 *
324 * There are several options that can be passed to the `cmake <path/to/UG>` call to modify how the code is built.
325 * For all of these options and parameters you have to use `-D<Parameter_name>=<value>`. Following a list of available
326 * options, for the full list run
327 *
328 * ```
329 * cmake <path/to/UG> -LH
330 * ```
331 *
332 * CMake option | Available values | Makefile equivalent | Remarks |
333 * ---------------------|--------------------------------|------------------------|--------------------------------------------|
334 * CMAKE_BUILD_TYPE | Release, Debug, ... | OPT=[opt, dbg] | |
335 * SCIP_DIR | /path/to/scip/install | | |
336 *
337 * Parameters can be set all at once or in subsequent calls to `cmake` - extending or modifying the existing
338 * configuration.
339 *
340 * @section CMAKE_INSTALL Installation
341 *
342 * CMake uses a default directory for installation, e.g., /usr/local on Linux. This can be modified by either changing
343 * the configuration using `-DCMAKE_INSTALL_PREFIX` as explained in \ref CMAKE_CONFIG or by setting the environment
344 * variable `DESTDIR` during or before the install command, e.g., `DESTDIR=<custom/install/dir> make install`.
345 *
346 * @section CMAKE_TARGETS Additional targets
347 *
348 * There are several further targets available, which can be listed using `make help`. For instance, there are some
349 * examples that can be built with `make examples` or by specifying a certain one: `make <example-name>`.
350 *
351 * | CMake target | Description | Requirements |
352 * |-----------------|-------------------------------------------------------|---------------------------------------|
353 * | fiberscip | build fiberscip UG executable | |
354 * | parascip | build parascip UG executable | |
355 * | githash | build executables for all applications | |
356 */
357
358/**@page MAKE Makefiles / Installation information
359 *
360 * Compiling with \UG directly can be done as follows:
361 *
362 * Type `make` in the console from the UG main folder. The system will ask you to provide necessary links and build fiberscip.
363 * Options include `OPT=<opt|dbg>` to select optimized or debug mode, `COMM=<pth,mpi,cpp11>` to select pthreads, MPI or cpp11.
364 * Also, some Makefile flags from scip can be set, such as `LPS` and `IPOPT`. Please refer to the
365 * <a href="https://scipopt.org/doc-8.0.0/html/md_INSTALL.php">SCIP documentation</a> for a full list.
366 *
367 * With `make doc` you can build a local copy of this documentation if you have doxygen installed in your machine.
368 * After the build process completed, open `doc/html/index.html` with your favourite browser.
369 *
370 */
371
372/**@page DOC How to search the documentation for interface methods
373 *
374 * If you are looking for a method in order to perform a specific task, the public UG Documentation is the place to look.
375 *
376 */
377
378/**@page HIERARCHYDIRS Classes hierarchy and source code directory organization
379 *
380 * The released code in the Ubiquity Generator framework (UG) has the following classes hierarchy and code directory organization.
381 *
382 * \image html classes.png "Classes hierarchy and source code directory organization" width=500px
383 * \image latex classes.png "Classes hierarchy and source code directory organization" width=500px
384 *
385 * - UG base classes: Classes for high-level task parallelization features
386 * - B&B Base classes: Classes for general parallel Branch-and-Bound features
387 * - UG_SCIP classes: Classes to parallelize the SCIP solver
388 *
389 * To add code to a specific baseSolver locate the source code files to parallelize the baseSolver in
390 *
391 * - src/ug_baseSolver
392 *
393 * The code specific to baseSolver can be inherited from B&B base classes or from UG base classes depending on the solver being based on B&B or non-B&B.
394 *
395 */
396
397/**@page CODE Coding style guidelines
398 *
399 * We follow the following coding style guidelines and recommend them for all developers in coding-style-guidelines.md.
400 * \verbinclude coding-style-guidelines.md
401 *
402 * If you want to contribute to UG development, please check out the contribution-guidelines.md.
403 * \verbinclude contribution-guidelines.md
404 *
405 * @section CODESPACING Spacing:
406 *
407 * - Indentation is 3 spaces. No tabs anywhere in the code.
408 * - Every opening parenthesis requires an additional indentation of 3 spaces.
409 *
410 * @section CODENAMING Naming:
411 *
412 * - Use assert() to show preconditions for the parameters, invariants, and postconditions.
413 * - Make all functions that are not used outside the module 'static'.
414 * - Naming should start with a lower case letter.
415 *
416 * @section CODEDOC Documentation:
417 *
418 * - Document functions, parameters, and variables in a doxygen conformed way.
419 *
420 * @section ECLIPSE Customize eclipse
421 *
422 * Eclipse user can use the profile below. This profile does not match the \UG coding guideline completely.
423 *
424 * \include codestyle/eclipse_ug_codestyle.xml
425 *
426 */
427
428/**@page DEBUG Debugging
429 *
430 * If you need to debug your own code that uses UG, here are some tips and tricks:
431 *
432 * - Use <b>asserts</b> in your code to show preconditions for the parameters, invariants and postconditions.
433 * Assertions are boolean expressions which inevitably have to evaluate to <code>TRUE</code>.
434 *
435 * - Compile UG in debug mode and run it with <a href="https://github.com/rr-debugger/rr">RR (Record and Replay)</a> or your favourite debug tool.
436 *
437 */