1<!DOCTYPE doctype PUBLIC "-//w3c//dtd html 4.0 transitional//en"> 2<!-- BEGIN LICENSE BLOCK 3 - Version: CMPL 1.1 4 - 5 - The contents of this file are subject to the Cisco-style Mozilla Public 6 - License Version 1.1 (the "License"); you may not use this file except 7 - in compliance with the License. You may obtain a copy of the License 8 - at www.eclipse-clp.org/license. 9 - 10 - Software distributed under the License is distributed on an "AS IS" 11 - basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See 12 - the License for the specific language governing rights and limitations 13 - under the License. 14 - 15 - The Original Code is The ECLiPSe Constraint Logic Programming System. 16 - The Initial Developer of the Original Code is Cisco Systems, Inc. 17 - Portions created by the Initial Developer are 18 - Copyright (C) 2006 Cisco Systems, Inc. All Rights Reserved. 19 - 20 - Contributor(s): 21 - 22 - END LICENSE BLOCK --> 23<html> 24<head> 25 <meta http-equiv="Content-Type" 26 content="text/html; charset=iso-8859-1"> 27 <meta name="Author" content="Joachim Schimpf"> 28 <meta name="GENERATOR" 29 content="Mozilla/4.79 [en] (X11; U; Linux 2.4.18-18.7.X-perfctr i686) [Netscape]"> 30</head> 31<body> 32<h1> Implementation Notes for lib(eplex), in ECLiPSe 5.6</h1> 33Author: Joachim, Kish <br> 34Date: July 2003 <br> 35Revision history: <a href="eplex_impl.html">July 2001 (original)</a>, 36May 2002 (modified for 5.4), Dec 2002 (modified for 5.5) <br> 37Contents: 38<blockquote> <a href="#Global%20structure">#Global structure</a> <br> 39 <a href="#Eclipse%20Code%20Level">#Eclipse Code Level</a> <br> 40 <a href="#C%20Code%20Level">#C Code Level</a></blockquote> 41<h2> <a name="Global structure"></a><u>Global structure</u></h2> 42These notes applies to the original eplex only. From ECLiPSe version 435.6, the standalone version of eplex, which does not require an ECLiPSe 44bounds keeper (ic or range) to keep the bounds of the variables, was 45introduced. This is described separately. 46<h3> Files</h3> 47Components: 48<ul> 49 <li> <b>eplex.c</b>: low level functions, lots of ifdefs for CPLEX 50and XPRESS and different versions of them</li> 51 <li> <b>eplex.pl</b>: top-level wrapper for loading the eplex library 52(with either range, ic or the external solver (standalone) for the 53interval).</li> 54 <li> <b>eplex_with_ic.ecl and eplex_with_range.ecl</b>: provides the 55ic- or range- specific macros and support. One of these are 56loaded by eplex.pl. In turn it loads eplex_.ecl, where the bulk of the 57ECLiPSe code for eplex is. There are two modulles, eplex and eplex_.</li> 58 <li> <b>eplex_.ecl</b>: generic (independent of cplex/xpress, 59ic/range) code implementing the library functionality. This code is 60loaded into the eplex_ module.</li> 61 <li><span style="font-weight: bold;"> ic_eplex.ecl and range_eplex.ecl</span>: 62trivial wrappers for eplex.pl to force loading of either ic- 63or range- for the interval.</li> 64 <li> <b>eplex_xpress.pl and eplex_cplex.pl</b>: trivial wrappers for 65eplex.pl to force loading of either solver</li> 66 <li> <b>eplex_comments</b>: the comment directives documentation for 67eplex.</li> 68 <li> <b>eplex_lic_info.pl:</b> data file that can be edited by the 69user (which licence on which machine). Also determines the default 70solver.</li> 71 <li> <b>empty_language.ecl: </b>contains the small set of predicates 72that are needed in the dummy modules used to select external 73solver/bounds keeper.</li> 74 <li> <b>eplex_params.h</b>: contains a C table to map the 75CPLEX/XPRESS parameter value to symbolic names used on the Eclipse 76level. This is created semi-automatically from the xpresso.h or cplex.h 77respectively.</li> 78 <li> <b>eplex_xpress.def and eplex_cplex.def</b>: DLL export 79specification for the Windows build</li> 80 <li> <b>WinMSC/EplexXpress and WinMSC/EplexCplex</b>: the 81corresponding projects for the Windows build</li> 82 <li> <span style="font-weight: bold;">bugxps.h, bugxp</span><span 83 style="font-weight: bold;">14.h, bugcpx.h</span>: the include files 84for the logging code</li> 85</ul> 86Related: 87<ul> 88 <li> fdplex.pl: a sample fd/eplex hybrid solver</li> 89 <li> mip.pl: a mip branch-and-bound on top of eplex</li> 90 <li> mipex.pl: some tests, not in the distribution</li> 91 <li> linearize.pl: used to linearize arithmetic expressions</li> 92 <li> lib(ic): provides the interval-variables used in eplex 93(alternative: range.pl)</li> 94 <li> lib(range): provides the range-variables used in eplex 95(alternative:ic.pl)</li> 96 <li> lib(var_name): provides stable variable name support</li> 97 <li> lib(constraint_pools): support for eplex instances</li> 98 <li> lib(colgen): column generation library, which uses 99lib(eplex)</li> 100 <li>lib(bfs): best-first search library, can be used in conjunction 101with lib(colgen)<br> 102 </li> 103</ul> 104<h3> Modules</h3> 105eplex.pl contains two modules <b>eplex</b> and <b>eplex_.</b> Most of 106the code is in eplex_ and reexported through eplex. The reason to have 107eplex_ at all is that eplex redefines the arithmetic predicates (>, 108>=, ...) which would be inconvenient to have in the actual 109implementation module. 110<p>There are four dummy modules, <b>eplex_cplex </b>and <b>eplex_xpress</b> 111, <b> ic_eplex </b>and<b> range_eplex</b> (defined in the 112corresponding files). They don't contain anything. In addition, 113to avoid the confusion of apparently being able to post arithematic 114constraints to these module, they only reexport the small subset of 115eclipse_language built-ins needed by the small amount of code in these 116modules.The only effect is that eplex.pl loads eplex_with_range.ecl 117when range_eplex exists, and the ic_with_range.ecl when ic_eplex 118exists; and simularily, eplex_.ecl attempts to load the Cplex version 119when the module eplex_cplex exists, and the Xpress version when module 120eplex_xpress exists. If none of them exists, the loaded solver is 121solely determined by the eplex_lic_info file. </p> 122<h3> Debugging</h3> 123The C code is littered (and made even more unreadable) by macros which 124can be used to produce a trace of all XPRESS/CPLEX functions that get 125called. This trace can be turned into a pure C bug report, so that any 126external solver bugs can be isolated from ECLiPSe. See section on <a 127 href="#Logging">logging</a>. 128<h2> <a name="Eclipse Code Level"></a><u>Eclipse Code Level</u></h2> 129<h3> Licences and versions</h3> 130Quite a bit of code at the beginning of eplex_.ecl deals with finding 131the right version of the C code to load and obtaining a licence 132(because the underlying solver is usually licence-protected). We use a 133little database file that tells the library which solver and version to 134use on a particular host, and where to find the licence for this 135solver. The information is held in the file <b>eplex_lic_info.ecl</b> 136in the Eclipse lib directory. If both Cplex and Xpress are available on 137a particular host, the selected solver is 138<ul> 139 <li> Cplex, if lib(eplex_cplex) was called</li> 140 <li> Xpress, if lib(eplex_xpress) was called</li> 141 <li> the first one listed in <b>eplex_lic_info.ecl</b> if lib(eplex) 142was called</li> 143</ul> 144It is not possible to have two different external solvers in the same 145Eclipse session. <br> 146The pair of predicates lp_get_licence/0 and lp_release_licence/0 obtain 147or release a licence. lp_get_licence/0 fails if no licence is availble, 148but it can be called again until one becomes available. On loading, the 149library tries to grab a licence, and prints a warning if this is not 150possible. 151<p>We also have OEM versions of Xpress that can be used with ECLiPSe 152which the user can use without obtaining an Xpress license from Dash. 153This checking is done at the C level (in p_cpx_init()) if the macro 154XPRESS_OEM_ICPARC_2002 is defined. It is done in C to avoid checking 155for 32 bit overflow: the formular used by Dash requires 32 bit integers 156to work correctly, whereas in ECLiPSe, integers > 32 bits will 157become bignums. Different keys are needed for the different versions of 158Xpress, and this is hard-coded into the C code via macros.</p> 159<h3> Attribute</h3> 160Eplex variables have the following attribute: 161<pre>:- export struct(<br> eplex(<br> solver, % A solver that this variable occurs in<br> idx, % The column number in that solver's matrix<br> intol_inst, % Suspension list to be woken on intolerable<br> next % can point to a different eplex attribute for another<br> % handler, or the atom 'end'<br><br> )<br> ).</pre> 162The eplex attribute consists of a chain of one or more attribute 163structures. Each attribute structure belongs to a specific solver 164state. Together they represent the eplex problems the particular 165variable occurs in. 166<p>The <b>solver</b> field contains <i>one of the problem handles 167where the variable occurs</i>, and the corresponding column index <b>idx</b>. 168This information is mainly needed in lp_var_get/4 to retrieve 169variable-related information such as the lp solution. This link is the 170main problem when we consider dealing with multiple solver handles 171simultaneously. <br> 172The <b>intol_inst</b> waking list is only used for a very special 173purpose, namely waking when the variable gets instantiated to a value 174that is outside of a certain tolerance from the lp solution. The 175tolerances can be set by using lp_set/3 on the solver handle and are 176different for continuous and integer variables. </p> 177<p>The <b>next</b> field points to the next attribute structure, or the 178atom end if there are none. An atom instead of a variable is used 179to terminate the chain to avoid potential problems with using setarg 180(setarg needs to be used as the chain needs to be modified in cases 181like when an attribute is discarded (see unification of attribute 182chains below)). <b><i>Each attribute structure in a chain must refer 183to a different solver state.</i></b> This assumption is made in 184many of the routines that handle the attribute chains. </p> 185<pre>:- meta_attribute(eplex, [<br> print:lp_var_print/2,<br> unify:unify_eplex/2,<br> suspensions:suspensions_eplex/3<br> ]).</pre> 186In general, the attribute handlers have to handle every single 187attribute structure in the chain. The attribute print handler prints 188the lp solutions of all the attribute structures in the 189chain(using the solver/idx fields in the attribute). The unify handler 190is responsible for: 191<ul> 192 <li> schedulting the intol_inst list if necessary</li> 193 <li> merging the eplex attribute chains when two eplex variables are 194unified:</li> 195 <ul> 196 <li> transfer the attribute chain if necessary if only one variable 197is an eplex variable.</li> 198 <li> if both are eplex variables, their chain is merged. The chain 199needs to be checked to see that the two chains do not contain 200attributes structures for the same solver state. If they do, one of the 201attribute structure is discarded, and an equality constraint send to 202the solver state. The event <b>lp_unify_same_handle </b>is also 203raised.</li> 204 </ul> 205</ul> 206<h3> Problem Handle</h3> 207What we call a <b>problem</b> in the following consists of 208<ul> 209 <li> a set of constraints</li> 210 <li> an objective function</li> 211 <li> the variables that occur in these constraints or the objective 212function</li> 213 <li> a (possibly empty) subset of these variables that are considered 214integers</li> 215 <li> a number of option settings</li> 216</ul> 217Multiple problems are supported by eplex, each problem having its own 218handles.We have problem handles on several levels: 219<ol> 220 <li> <b>Eclipse level:</b> this is an Eclipse structure (<b>struct prob</b> 221), its fields are backtracked, the first field refers to the C level 222descriptor</li> 223 <li> <b>C level:</b> this is a C structure (<b>struct lp_desc</b>), 224its fields are non-backtracked, it refers among others to the solver 225state descriptor</li> 226 <li> <b>CPLEX/XPRESS level:</b> this is the solver's problem handle 227(if any) which is a black box for us. We refer to this as the solver 228state.</li> 229</ol> 230The <b>Eclipse handle</b> contains all the information we want to hold 231on the Eclipse level, for whatever reason (because it it more 232convenient, because it is logical storage, etc). Among the fields are: 233<pre>:- export struct(<br> prob(<br> cplex_handle, % int: pointer to C data structure<br>...<br> vars, % ''(X1,...,Xn): struct of problem variables<br> ints, % [Xi1,...Xik]: list of integer variables<br>...<br> method, % atom: solving method (primal, dual, ...)<br> demon_tol_int, % float: tolerable deviation of instantiation<br> demon_tol_real, % float: ... to simplex solution.<br>...<br> presolve, % 1 for yes, 0 for no<br> use_copy, % 1 for yes, 0 for no<br>...<br> status, % return status of last successful invocation<br> cost, % float: cost of the current solution<br> sols, % array[n] of raw solutions (or [] or _)<br> pis, % array[m] of dual values (or [] or _)<br> slacks, % array[m] of slacks (or [] or _)<br> djs, % array[n] of reduced costs (or [] or _)<br> base % iarray[n+m] of basis status (or [] or _)<br> )<br> ).</pre> 234The <b>vars</b> array keeps a reference to all the variables involved 235in the problem. The array index corresponds to the column number on the 236solver level (except that Eclipse array indixes run from 1..N and 237column number from 0..N-1). The variables that are treated as integers 238by the solver are stored in an additional list <b>ints</b>. If this 239list is empty, we only solve LP problems! <br> 240<a name="presolve"></a>The <span style="font-weight: bold;">presolve </span>field 241specifies the presolve setting for this problem. If the solver supports 242only global parameter, then this local setting for presolve is simulated 243at the C-level by changing the parameter whenever it is needed for the 244problem. In addition, some solvers may have more than a simple binary 245setting for the presolve, and indeed different parameters for the MIP 246and LP presolves (Xpress). In this case, the <span 247 style="font-weight: bold;">presolve </span>setting maps to all 248problem types with some default values when presolve is on. <br> 249The <span style="font-weight: bold;">use_copy</span> field 250specifies if a copy of the problem at the C-level should be used when a 251MIP problem is solved. Using a copy allows a MIP problem to be modified 252when Xpress is used; as otherwise Xpress does not allow a MIP 253problem to be modified (beyond changing bounds) once the MIP search has 254started.<span style="font-weight: bold;"></span> <br> 255The <b>method</b> and <b>demon_tol </b>fields store control 256parameters for the solver (others are stored on a lower level). <br> 257The remaining group are solver results: <b>status</b> is an integer 258that contains the underlying solver's last return status (not normally 259needed by the programmer). <b>cost</b> is the cost of the last solution 260that was computed. <br> 261The subsequent <b>arrays</b> contain the result values belonging to 262that solution. Note that not all these arrays need to be in use. When 263they are initialised to free variables, they remain unused. When they 264are initialised to nil, they will be setarg'd to new arrays after every 265successful run of the solver. This initialisation is done by the 266corresponding solver options (in lp_setup/3 or later via lp_set/3): <br> 267<center> 268<table border="1" cols="3" width="60%" nosave=""> 269 <caption> 270 <center> 271 <p></p> 272 </center> 273 </caption><tbody> 274 </tbody><tbody> 275 </tbody> <tbody> 276 <tr bgcolor="#cccccc" nosave=""> 277 <td nosave=""><b>Result option name</b></td> 278 <td><b>Default setting</b></td> 279 <td><b>Array name in prob</b></td> 280 </tr> 281 <tr> 282 <td>solution</td> 283 <td>yes</td> 284 <td>sols</td> 285 </tr> 286 <tr> 287 <td>dual_solution</td> 288 <td>no</td> 289 <td>pis</td> 290 </tr> 291 <tr> 292 <td>slack</td> 293 <td>no</td> 294 <td>slacks</td> 295 </tr> 296 <tr> 297 <td>reduced_cost</td> 298 <td>no</td> 299 <td>djs</td> 300 </tr> 301 <tr> 302 <td>keep_basis</td> 303 <td>no</td> 304 <td>base</td> 305 </tr> 306 </tbody> 307</table> 308</center> 309<p>Note again that this is <i>logical storage</i> which is properly 310reset on backtracking, while everything that is stored at the C level 311is not. Where reset is needed at the C level, explcit "undo functions" 312needs to be trailed. <br> 313</p> 314<h3> Support for column generation</h3> 315The column generation library uses the eplex library. The 316main support provided by eplex for column generation are: 317<ul> 318 <li> returning row indicies for the added constraints</li> 319 <li> adding columns with coefficients for existing rows, and also a 320non-zero objective coefficient</li> 321 <li> retreiving column data from the ECLiPSe level</li> 322</ul> 323<h3> Support for multiple problems</h3> 324As disccused under the attribute section, multiple problems are 325supported in the ECLiPSe level with chains of eplex attributes. A 326variable can be involved in multiple eplex problems, each with a 327different solver state, and each attribute structure within the eplex 328attribute for the variable represents one solver state. 329<p>Each ECLiPSe problem handle is given a unique integer id, the <b>solver 330id</b> . Each time a solver state is created, it is assigned a new 331solver id maintained within a global reference, whose value is 332incremented for the next solver id. The solver id is stored into the <b>solver_id</b> 333field of the problem handle for the solver state, and is used to 334identify the solver state within the ECLiPSe code for the library, for 335example, in predicates which needs to access a specific eplex 336attribute structure in a chain. </p> 337<p>The concept of <a href="#Eplex_instances">eplex instances </a>is 338used to represent multiple eplex problems at a high-level. This allows 339constraints for an eplex problem to be posted before a solver state is 340set up for it. Note that the eplex attribute structure is not 341created until the solver state is set up. </p> 342<h3> Managing solver parameters</h3> 343With Xpress 13+, the solver parameters are specific to each problem and 344there are no global parameters. With Cplex and older Xpresses, the 345parameters are global (i.e. applies to all problems). This difference 346unfortunately cannot be hidden from the user. An additional 347complication is that currently a ECLiPSe level problem may not yet have 348a C-level solver handle (e.g. if the problem was empty). This is an 349issue if the solver parameters are problem specific. 350<p>We allow access (get/set) to these parameters via the problem handle 351(or eplex instance)[local access], or `globally', without specifying any 352handle/instance. The exact meaning of `global' parameter depends on if 353the solver has global parameters or not: </p> 354<ol> 355 <li> solver has global parameters: acess to global parameters in eplex 356directly accesses the corresponding solver parameter.</li> 357 <li> solver has no global parameters: `global' parameters are the 358default settings for the parameters, i.e. the values that would be 359given to a new problem when it is set up (at the C level). It does <span 360 style="font-style: italic;">not </span>affect any existing 361problem's parameter.</li> 362</ol> 363Thus, the two cases of the global parameters behaves in the same way 364only if the parameters are accessed before any problem setup. 365<p>The following table shows the value that is returned for various 366types of accesses. There are three types of access: global access (no 367handle), local access, no C handle (with a problem handle that does not 368yet have a low level handle), local access, with C handle (with a 369problem handle with a low level handle): <br> 370<table border="1" cellspacing="2" cellpadding="2" 371 style="width: 100%; text-align: left;"> 372 <caption><br> 373 </caption><tbody> 374 </tbody> <tbody> 375 <tr> 376 <td valign="top" style="background-color: rgb(192, 192, 192);">access 377type</td> 378 <td valign="top" style="background-color: rgb(192, 192, 192);">solver 379has local params</td> 380 <td valign="top" style="background-color: rgb(192, 192, 192);">solver 381has global params</td> 382 </tr> 383 <tr> 384 <td valign="top">global </td> 385 <td valign="top">default value</td> 386 <td valign="top">global value</td> 387 </tr> 388 <tr> 389 <td valign="top">local, no C handle</td> 390 <td valign="top">default value</td> 391 <td valign="top">global value</td> 392 </tr> 393 <tr> 394 <td valign="top">local, with C handle</td> 395 <td valign="top">problem's value</td> 396 <td valign="top">global value</td> 397 </tr> 398 </tbody> 399</table> 400</p> 401<p>We plan to remove the complication of wheather there is a C level 402handle or not by always setting up a low level solver for a problem 403during problem setup. </p> 404<p>We do not allow the user to<span style="font-weight: bold;"> set </span>a 405solver parameter locally if the solver has global parameters only, 406because this would have the `side effect' of changing this parameter 407globally. </p> 408<p>Also, note that the <span style="font-weight: bold;">presolve </span>parameter 409is treated specially. This does not correspond directly to the low 410level presolve parameter of the solver. Instead it always behaves as if 411this parameter is local, i.e. it is specific to each problem, and if 412set globally, it sets the default value. With solvers that only has 413global parameters, the local behaviour is simulated as discussed <a 414 href="#presolve">here.</a> </p> 415<p>The default values for parameters in Xpress 13+ is stored in a dummy 416problem which is created on initialisation. The values of these 417parameters is copied into each new problem that are created. </p> 418<p>When used from ECLiPSe, these parameters needed to be wrapped in a 419optimizer_param/1 structure, to clearly show that they are optimizer 420(and version) specific. We also provide two special aliases that do not 421need the optimizer_param/1 wrapping: <span style="font-weight: bold;">presolve</span>, 422as discussed above, and <span style="font-weight: bold;">timeout</span>. 423This allow the user to avoid version specific code for these common 424cases, and also not needing to worry about the differences in the 425actual solver parameter (different names, different argument type, 426different semantics). </p> 427<h3> Normalised expressions and constraints</h3> 428All expressions occurring in eplex constraints are turned into 429normalised linear form using lib(linearize): 430<pre> [C0*1, C1*X1, C2*X2, ...]</pre> 431where Ci are numbers and Xi are distinct variables. The first 432(constant) term is always present, Ci (i>=1) are nonzero. <br> 433Constraints are normalized by bringing all terms to one side of the 434relational symbol and then storing just the relational symbol and the 435non-zero side as a normalised expression: 436<pre> Sense:NormExpr</pre> 437where Sense is one of the atoms =:=, >= or =< and NormExpr is a 438normalised expression as above. E.g. 439<pre> (>=):[-5*1,3*X]</pre> 440could encode the source constraint 441<pre> 5 =< X*3</pre> 442There is also a quadratic normal form being used for quadratic 443objectives, see lib(linearize) for details. 444<h3> <a name="Eplex_instances"></a><a name="eplex_instances"></a>Eplex 445instances</h3> 446For ease of programming multiple eplex problems, the abstraction of <i>eplex 447instances</i> is introduced. Conceptually, an eplex instance is an 448instance of the eplex solver for one eplex problem. Each 449eplex instance is a module, and from a user's point of view, it works 450like any other solver module: predicates are defined in the module 451which allows the user to post linear arithmetic and intergrality 452constraints, and to set up and invoke an external solver to solve the 453problem. There are three components: 454<ol> 455 <li> storage for constraints</li> 456 <li> predicates to set up and trigger solver state</li> 457 <li> associated external solver state (if one has been setup)</li> 458</ol> 459<h4> Storage for constraints</h4> 460This is implemented using lib(constraint_pools). The posted constraints 461are buffered on the ECLiPSe level in constraint pools, one pool per 462eplex instance. 463<p>When an eplex instance is declared using eplex_instance/1, an eplex 464instance is either created (if it does not already exist) or checked to 465see if it is empty (no posted constraints in the constraint pool, no 466associated solver). An eplex instance is created by creating the 467constraint pool for it. </p> 468<p>The constraints are divided into two types, defined in the structure 469constraint_type in eplex_.ecl: </p> 470<p>:- local struct(constraint_type(integers,linear)). </p> 471<p>integers are the intergrality constraints (integers/1), and linear 472are the linear arithmetic constraints (=:=/2, >=/2, =</2). </p> 473<p><a name="lincon-action"></a>When a linear constraint is posted, the 474following happens: </p> 475<p> 1. the constraint gets normalised <br> 476 2. if ground, solve it now, i.e. check if satisfied <br> 477 3. if it has only one variable, turn it into a (range- or 478ic-) bound update <br> 479 4. otherwise, add the normalised form to the linear 480constraint type of the constraint pool. </p> 481<p>integers/1 is handled by </p> 482<ol> 483 <li> imposing ic:integers/1 or range:integers/1 on the variables</li> 484 <li> eliminating ground integers from the list</li> 485 <li> add the remaining variables to the integers constraint type of 486the constraint pool. For efficiency, when the integers list is 487traversed to eliminate ground integers, a unbounded tail is created to 488allow the existing integers to be added to this tail</li> 489</ol> 490Thus the constraints are not actually maintained as suspensions, but 491logically they are still part of the resolvent. Any constraints that 492remain in any of the eplex instances' constraint pools are thus printed 493out at the end of an execution. This is done by calling 494set_lp_pending/0 whenever a constraint is added to an eplex instance. 495set_lp_pending/0 will create an lp_pending/0 suspension if one does not 496already exist, so the presence of this suspended goal indicates that 497there are possibly some constraints posted to some eplex instance. A 498portray macro for lp_pending/0 is defined to print out the outstanding 499constraints in all the eplex instances, so that when the delay goals 500are printed at the end of an execution, the eplex constraints would be 501printed instead of lp_pending/0. Note that constraints collected by an 502external solver will not be printed, even if the external solver was 503not invoked to solve the problem. 504<p>The suspended lp_pending goal is stored in the global reference <b>lp_info</b> 505in the module eplex_. lp_info is a structure with two fields: </p> 506<p>:- local struct(lp_info(newid, % int: next 507handler id <br> 508 509pending % suspension: lp_pending's suspension <br> 510 )). </p> 511<p>newid is the next solver id. </p> 512<h4> Predicates for the eplex instance</h4> 513Predicates defined in the eplex instances simply call their 514counter-parts in the module eplex_ with the eplex instance name as an 515argument. All the real work is done by the predicates in the eplex_ 516module. This is specified in the create_constraint_pool/3 call <br> 517when the constraint pool is created. 518<p>Except for the constraint predicates, all other predicate names 519defined for an eplex instance start with eplex_. The predicates 520(in the eplex instance) are: <br> 521 </p> 522<blockquote><b>constraints</b>: 523integers/1, =:=/2, >=/2, =</2 <br> 524 <b>solver setup:</b> 525eplex_solver_setup/1, eplex_solver_setup/5 <br> 526 <b>solver invocation:</b> eplex_solve/1, 527eplex_probe/2 <br> 528 <b>solver state:</b> 529eplex_get/2, eplex_var_get/3 <br> 530 <b>destroy solver:</b> 531eplex_cleanup/0<br> 532 <span style="font-weight: bold;">read/write problem: </span> 533eplex_read/2, eplex_write/2<br> 534</blockquote> 535In turn, the eplex_* predicates in eplex_.ecl calls the low-level 536predicate that uses solver state handles. The solver handle is for the 537solver state that is associated with the particular eplex instance. 538<h4> <b>Associating external solver state</b></h4> 539A new external solver state can be associated with an eplex instance by 540the solver setup predicates of the eplex instance. The solver state is 541first created and then associated with the eplex instance. 542<p>Associating with an eplex instance is done using the pool item 543facility of lib(constraint_pools). The ECLiPSe handle for a solver 544state is stored in the eplex instance's pool item if the eplex instance 545has an associated solver, otherwise 0 is stored as the pool item. <br> 546 </p> 547<h3> lp_setup</h3> 548This is really the core of the library. It takes as input 549<ol> 550 <li> a list of already normalised constraints (equalities and 551inequalities)</li> 552 <li> an objective expression (linear or quadratic)</li> 553 <li> a list of integer variables (within the option list)</li> 554 <li> a list of solver options</li> 555</ol> 556This data is used to set up a linear, quadratic or mixed integer 557problem with the external solver, and a handle to it is returned. 558<ul> 559 <li> A quadratic problem (qp) is set up if the objective is not linear</li> 560 <li> A mixed integer problem (mip) is set up if the list of integers 561is not empty. Note that the integrality-information in the 562range-attribute (range:integers/1) is completely ignored for this 563purpose. This allows lp_setup to set up a linear relaxation easily.</li> 564 <li> A linear problem (lp) is set up otherwise</li> 565</ul> 566There are a few interdependencies<br> 567<ul> 568 <li>there are restrictions on changing the problem type, some of 569which is imposed by our interface.:</li> 570 <ul> 571 <li> An lp problem can change to a mip problem, but not vice 572versa (except during backtracking) as contraints cannot be removed in 573forward execution. <br> 574 </li> 575 <li>A qp problem cannot change to a qpmip problem. We have 576not yet implemented the interface for dealing qpmip problems.</li> 577 <li>A linear problem cannot change to a quadratic problem. This 578affects lp_probe only, as this is the only way the objective can be 579changed in eplex. There is probably no implementational reason 580that this can't be done (currently a qp problem is first set up as an 581lp problem at the C level).</li> 582 </ul> 583 <li> mip problems cannot be quadratic</li> 584 <li> quadratic problems imply the use of the barrier method<br> 585 </li> 586</ul> 587Pseudocode: 588<pre>lp_setup:<br> assign a new solver id<br> renormalise constraints (possibly do some simplification)<br> normalise the objective (and determine whether it's linear)<br> create array of problem variables<br> create list of integer variables if required<br> assign column numbers to the variables and store them in the attributes<br> convert constraints into column-wise lists of row:coefficient pairs<br> transfer data into the C-level descriptor (including transfer of all variable<br> bounds from bounds keeper to solver)<br> call the C-level problem setup function cplex_loadprob()</pre> 589Note that special treatment is needed for extreme cases (no variables, 590no constraints), because the low-level code cannot cope with degenerate 591cases. 592<p>Each solver state is assigned an unique integer solver id. The next 593id to assign is maintained in a global reference. </p> 594<h3> lp_solve</h3> 595Takes a problem handle and invokes the actual optimizer. Because it can 596be called repeatedly on the same problem handle, it takes care of first 597transferring possibly updated variable bounds to the solver,and 598optionally loading a basis that might have been saved from a previous 599solver run. It may alsoPseudocode: 600<pre>lp_solve:<br> setup problem if not already setup<br> if not a freshly set up problem:<br> transfer current variable bounds to the solver (all or some)<br> if a previous basis is available:<br> transfer basis to the solver<br> invoke the solver<br> interpret the result<br> if successful:<br> retrieve the cost<br> retrieve the required result arrays (solutions, basis, etc)</pre> 601You can see that the <b>updating of variable bounds </b>is not very 602well optimized: we normally assume that every variable could have 603changed bounds and traverse the whole variable array and transfer all 604the current bounds to the solver in case they have changed. Any better 605strategy would require to monitor variables individually, and it is not 606clear whether this is worthwhile. <br> 607About handling the <b>basis</b>: storing the basis at the logical 608Eclipse-level is optional. If it is done, then the solver can restart 609from the basis of the logical ancestor in the search tree. If it is not 610done, it will just use the basis from the chronologically last solver 611invocation. The latter is less predicatable, but has less overhead. <br> 612Cplex and Xpress can return lots of different <b>result codes</b>. We 613classify them into the following groups: <br> 614<center> 615<table border="1" width="90%" nosave=""> 616 <caption> 617 <center> 618 <p></p> 619 </center> 620 </caption><tbody> 621 </tbody><tbody> 622 </tbody> <tbody> 623 <tr bgcolor="#cccccc" nosave=""> 624 <td nosave="">Result</td> 625 <td>description</td> 626 <td>action</td> 627 <td>default handler</td> 628 </tr> 629 <tr nosave=""> 630 <td>DESCR_SOLVED_SOL</td> 631 <td>an optimal solution was found</td> 632 <td>success</td> 633 <td nosave="">success</td> 634 </tr> 635 <tr> 636 <td>DESCR_SOLVED_NOSOL</td> 637 <td>no solution was found, infeasible</td> 638 <td>fail</td> 639 <td>fail</td> 640 </tr> 641 <tr> 642 <td>DESCR_ABORTED_SOL </td> 643 <td>a possibly suboptimal solution was found (mip)</td> 644 <td>event(eplex_suboptimal)</td> 645 <td>success</td> 646 </tr> 647 <tr> 648 <td>DESCR_ABORTED_NOSOL </td> 649 <td>no solution was found, but there may be one (mip)</td> 650 <td>event(eplex_abort)</td> 651 <td>abort</td> 652 </tr> 653 <tr> 654 <td>DESCR_UNBOUNDED_NOSOL</td> 655 <td>problem unbounded, no solution values</td> 656 <td>event(eplex_unbounded)</td> 657 <td>success</td> 658 </tr> 659 <tr> 660 <td>DESCR_UNKNOWN_NOSOL</td> 661 <td>unknown whether infeasible or unbounded</td> 662 <td>event(eplex_unknown)</td> 663 <td>fail</td> 664 </tr> 665 </tbody> 666</table> 667</center> 668<p>The <i>infeasible or unbounded</i> result can arise from the use of 669presolving or the dual simplex method (because infeasibility of the dual 670indicates infeasibility or unboundedness of the primal). The events have 671been introduced to enable the library user to tailor the behaviour of 672the solver for the doubtful results. </p> 673<h3> optimize</h3> 674Optimize (the black-box solver) is a simple sequence of 675<ol> 676 <li> collecting the pending constraints (equalities, inequalities and 677eplex:integers/1)</li> 678 <li> setting up a solver</li> 679 <li> run the solver</li> 680 <li> unifying the resulting cost</li> 681 <li> retrieving the solutions and unifying them with the variables</li> 682 <li> cleaning up the solver</li> 683</ol> 684<h3> lp_demon</h3> 685For the demon solver, the setup and initial solving is like for the 686black-box solver. The differerences are that a demon with appropriate 687waking conditions is set up as well, the Cost variable is only bounded 688by the solution (rather than unified), and the problem variables are 689not touched after solving: 690<ol> 691 <li> collecting the pending constraints (equalities, inequalities and 692integers/1) from the eplex instance that the demon is associated with 693(if any), specified by the collect_from option.</li> 694 <li> setting up a solver</li> 695 <li> create the lp_demon suspension</li> 696 <li> insert the suspension into the suspend field of the handle</li> 697 <li> run the solver once if initial_solve option is yes</li> 698 <li> calling the post-goal (see user documentation)</li> 699 <li> bounding the Cost variable</li> 700</ol> 701When the lp_demon is woken subsequently, it performs: 702<ol> 703 <li> collecting new pending constraints (equalities, inequalities and 704eplex:integers/1) if the solver state is associated with an eplex 705instance.</li> 706 <li> adding them to the existing handle</li> 707 <li> in case new variables have been introduced, let the lp_demon 708suspend on them as well</li> 709 <li> calling the pre-goal</li> 710 <li> run the solver again</li> 711 <li> calling the post-goal</li> 712 <li> bounding the Cost variable</li> 713</ol> 714Triggering the demon: <br> 715<center> 716<table border="1" width="80%" nosave=""> 717 <caption><br> 718 <center> 719 <p></p> 720 </center> 721 </caption><tbody> 722 </tbody><tbody> 723 </tbody> <tbody> 724 <tr bgcolor="#cccccc" nosave=""> 725 <td nosave="">Trigger condition</td> 726 <td>Implementation</td> 727 </tr> 728 <tr> 729 <td>inst</td> 730 <td>insert in all variable's (inst of suspend) lists</td> 731 </tr> 732 <tr> 733 <td>bounds</td> 734 <td>insert in all variable's (wake_lo/wake_hi of range) lists</td> 735 </tr> 736 <tr> 737 <td>deviating_inst</td> 738 <td>insert in all variable's (intol_inst of eplex) lists</td> 739 </tr> 740 <tr> 741 <td>deviating_bounds</td> 742 <td>like deviating_inst, additionally set up a 743deviating_bounds_demon on every variable which wakes on bound changes 744and schedules the intol_inst list when the new bounds exclude the 745lp-solution</td> 746 </tr> 747 <tr> 748 <td valign="top">Attribute:Index</td> 749 <td valign="top">insert in all variables' suspension list found 750in attribute Attribute in the index'th position </td> 751 </tr> 752 <tr> 753 <td>new_constraint</td> 754 <td>the nc_trigger field of the solver state's handle is set to 755yes (it defaults to no). When constraints are added to the solver state 756(see lp_add below), the nc_trigger filed is checked, and if it is yes, 757then the demon is triggered (by scheduling the suspension for the demon 758in the suspension field for the handle)</td> 759 </tr> 760 <tr> 761 <td>trigger(atom)</td> 762 <td>attach to a global trigger</td> 763 </tr> 764 </tbody> 765</table> 766</center> 767<h3> lp_add</h3> 768lp_add add constraints and variables to a previously set up problem 769handle. The handles on all levels must be adjusted accordingly. In 770general, the problem type can change from lp to mip (if interger 771constraints are added to an lp problem). Both linear and integers 772constraints can be added (if allowed by the problem type). 773Currently we do not support the changing of a qp problem to qmip 774problem. 775<p>lp_add can be called in several ways, either explicitly (e.g. via 776lp_add_constraints), or implicitly (when a demon solver is invoked), 777with various steps, which are carried out by three predicates:<br> 778</p> 779<ol> 780 <li><span style="font-weight: bold;">renormalise_and_check_simple</span>: 781Renormalise any new linear constraints <br> 782 </li> 783 <li><span style="font-weight: bold;">lp_add_normalised</span>: Add 784the new (normalised) constraints/variables to the problem</li> 785 <li><span style="font-weight: bold;">var_triggers</span>: Add the new 786variables to the triggers<br> 787 </li> 788</ol> 789Not all calls to adding constraints/variables to the problem perform 790all three steps. For example, adding columns for column generation does 791not normalise the constraint (because simple constraints has to be 792added to the problem).<br> 793<h4><span style="font-weight: bold;">renormalise_and_check_simple</span></h4> 794Renormalised and any ground linear constraints (all variables in 795constraint instantiated) are checked for satisfaction and filtered out 796(not passed to external solver). Note that unlike when linear 797constraints are posted, single variable constraints are not turned into 798bound updates.<br> 799<span style="font-weight: bold;"><br> 800lp_add_normalised</span> 801<p>This predicate returns the row indicies of the added constraints. 802This is needed by the column geneation library. In other cases, these 803indcies are ignored. </p> 804<p>Variables occurs in both the new linear and integers constraints 805being added. They can be classified as: </p> 806<ul> 807 <li>old variables: variables that are already in the solver 808state</li> 809 <ul> 810 <li>old integer variables: old variables which occur in the 811new integers constraints. They may or may not already be constrained to 812be integer</li> 813 <li>other old variables: old variables which occurs in the 814new linear constraints only<br> 815 </li> 816 </ul> 817 <li>new variables: variables that are not yet in the solver state </li> 818 <ul> 819 <li> new integer variables: new variables which occur in both the 820new linear constraints and integers constraints.</li> 821 <li>new non-integer variables: new variables which occur in the new 822linear constraints only<br> 823 </li> 824 </ul> 825 <ul> 826 <li> non-problem variables: these are variables are neither in the 827solver state or occur in the new linear constraints (i.e. they occur 828only in the new integers constraints)<br> 829 </li> 830 </ul> 831</ul> 832<p>The steps performed by lp_add are: </p> 833<ol> 834 <li>If problem not yet initialised (no variables/constraints set up 835yet), initialise it</li> 836 <li> Classify the variables that occur in the new constraints (both 837linear and integers) into old integers, other old variables, new 838integers, non-problem variables and new non-integer variables. These 839need to be treated differently:</li> 840 <ul> 841 <li>other old variables: nothing needs to be done with these<br> 842 </li> 843 <li> old integers: the type of columns representing these variables 844in the external solver matrix need to be changed if it was not 845already an integer (or boolean). The type changes are undone on 846backtracking at the C level.</li> 847 <li> new integers: new column needs to be added to the external 848solver matrix, as type integer</li> 849 <li> non-problem variables: these are not passed to the external 850solver. A warning is printed.</li> 851 <li> new non-integer variables: these are new variables that 852are not constrained to be integers. A new column needs to be added to 853the external solver matrix, as type continueous.</li> 854 </ul> 855 <li> The C level code are called to possibly add new rows (if there 856are new linear constraints) and columns (if there are new problem 857variables) with the correct type. (cplex_flush_new_rows)</li> 858 <li>If var_names option is set, pass any variable names for the new 859varaibles to the solver state.<br> 860 </li> 861</ol> 862<h4>var_triggers</h4> 863If there are variable trigger conditions, add the variable trigger 864condition(s) to the new variables. This same code is used here as 865during the demon solver's setup.<br> 866<h3>lp_add_constraints</h3> 867This basically calls lp_add after normalising the constraints, and then 868filter out simple one variable linear constraints as done when linear 869constraints are posted to an eplex instance. <br> 870After calling lp_add, the solver is invoked if the nc_trigger field of 871the handle is set to yes. 872<h3>lp_eq, lp_ge, lp_le</h3> 873These are called when the linear constraints (=:=, >=, =< and 874their $ equivalents, respectively) are posted to an eplex 875instance. The actiions performed are described <a 876 href="file:///a/breeze/extra4/ks15/Eclipse/documents/internal/lincon-action">here</a>.<br> 877<h3> lp_probe</h3> 878lp_probe is simply a wrapper around lp_solve: 879<pre>lp_probe:<br> change Handle's objective function to temporary one<br> invoke lp_solve on Handle<br> change Handle's objective function back to the original one</pre> 880if a variable occurs in the new objective, but not in the problem, it 881is added to the problem if it has bounds of the bounds keeper (i.e. 882range for range_eplex, ic for ic_eplex). This is to get around the 883problem where the user post only simple bounds constraints for such 884variable, which are then not added to the problem. This is not a 885problem for stand-alone eplex, as such variables are added to the 886problem. <br> 887 888<h3> lp_add_columns</h3> 889adds new columns to the external solver matrix. Unlike lp_add, these 890new columns may be non-empty, i.e. there may be non-zero values for the 891existing rows, and objective coefficient. <br> 892This is used by the column generation library to add the generated 893columns. The column information is specified by a list [Var, Obj, Col], 894where Var is the variable representing the new column, Obj is its 895objective coefficient, and Col is a list of RowIdx-Value pair 896representing the non-zero column coefficients. 897<p>The steps performed by lp_add_columns are (code is based on the 898lp_add code, with column-wise C-level buffer arrays for the column 899coefficients (cmatbeg, cmatind,cmatval) in the problem descriptor: </p> 900<ul> 901 <li> extract the individual column data for the new columns, filtering 902out existing columns</li> 903 <li> set the new indecies for the new columns and update the buffer 904arrays (column coefficients and bounds)</li> 905 <li> flush the data to the external solver state by calling 906cplex_flush_new_cols</li> 907 <li> set the var_names for the new columns (if required)</li> 908 <li> set the objective coefficients for the new columns (earlier 909versions of this code clears all the objective coefficients, including 910the existing one, and resets everything).</li> 911 <li> extend the basis by retaining the last basis and giving 0 to the 912new columns</li> 913</ul> 914<h3> reduced_cost_pruning</h3> 915reduced _cost_pruning implements an optional functionality that the 916programmer can invoke on a solved handle (see for example Michela 917Manela's work). If we are solving the lp-relaxation of a more complex 918global problem, and we have a maximum (minimum) of the relaxation, and 919a lower (upper) bound on the global problem, then we can use the 920reduced cost information of the relaxed solution to prune variable 921values that cannot possibly yield a better solution to the global 922problem. 923<center><img src="redcost.png" alt="reduced cost pruning" height="277" 924 width="424" align="bottom"></center> 925For those variables whose solution value is at one of their bounds, the 926reduced cost gives a gradient which says how much the objective 927deteriorates (at least) when the value moves away from the bound. 928Values that are so far away that the relaxed cost gets worse than the 929known bound on the global cost, are useless and so the opposite bound 930may be pruned to that value. 931<h2> <a name="C Code Level"></a><u>C Code Level</u></h2> 932<h3> Versions</h3> 933The C code needs to be compiled separately for every version of the 934Cplex or Xpress solver that we want to support. The makefile builds 935differently named shared libraries from the single eplex.c source file, 936e.g. 937<ul> 938 <li> ecplex65.so for Cplex 6.5 (compiled with -D<i>CPLEX=6</i> and -D<i> 939CPLEXMINOR=5</i>)</li> 940 <li> express1412.so for Xpress 14.12 (compiled with -D<i>XPRESS=14</i>)</li> 941</ul> 942One Eclipse distribution can contain several versions of the compiled C 943code for different solvers and different solver versions. At runtime 944however, when lib(eplex) is loaded, it can only load one of them. Which 945one gets loaded depends on the information in the <b>eplex_lic_info.ecl</b> 946file, see the loader code at the beginning of eplex.pl. 947<p>The C code links in the external solver library code statically if 948possible, and is itself dynamically loaded when lib(eplex) is loaded. 949However, static linking is not possible with Xpress 14, and in addition 950two dynamic libraries: the solver itself, and the licensing code, have 951to be loaded. In addition, the files must be loaded with their full 952name, including the minor version numbers at the end (e.g. 953libxprl.so.1.0.3), as this is checked in some systems. To make our code 954as generic as possible, we ensure that only one copy of each dynamic 955library is copied into the right subdirectory and preload (in ECLiPSe 956code) the library by specifying the file name partially (e.g. 957libxprl.so.* ). </p> 958<h3> Problem descriptor</h3> 959We maintain a C-level problem descriptor (which is itself referred to 960by the Prolog level problem handle) 961<ul> 962 <li> struct lp_desc {}</li> 963</ul> 964This descriptor stores: 965<ul> 966 <li> the solver-specific problem descriptor (CPXLPptr for Cplex, or 967XPRSprob for Xpress 13+)</li> 968 <li> additional data about the problem we want to maintain in 969non-backtracked storage (e.g. success and failure counters)</li> 970 <li> all data (esp. arrays) that need to be built up incrementally 971during problem setup, and that are then used as input to the solver's 972own problem setup function</li> 973 <li> some problem specific settings that are more convenient/efficient 974to maintain at the C level, e.g. the presolve state</li> 975</ul> 976The descriptor has a state which is either one of the solution states 977described under lp_solve/2, or 978<ul> 979 <li> DESCR_LOADED during setup, no solve attempted yet</li> 980 <li> DESCR_EMPTY after cleanup</li> 981</ul> 982<h3> Initialization and finalization</h3> 983Two C externals are provided for initialise and finalise the whole 984subsystem, essentially this means dealing with the licences: 985<ul> 986 <li> <b>cplex_init(LicenceLocation, SerialNum), p_cpx_init</b></li> 987 <br> 988tries to obtain a solver licence, fails if this is not possible. The 989arguments come from the eplex_lic_info.ecl file. SerialNum is only 990relevant for Cplex runtime licences. <li> <b>cplex_exit, p_cpx_exit</b></li> 991 <br> 992releases the solver licence, and deallocation of some of the storage 993</ul> 994<h3> Problem name</h3> 995Xpress requires a problem name when initialising. Moreover, the problem 996name is used to generate various intermediate results files (mostly 997during MIP search). If more than one Xpress is running at the same time 998within the same file space, then name clashes are possible which might 999lead to incorrect behaviour. In order to avoid this, the problem name 1000is generated from the machine's host id and the current process's id. 1001<p>For Xpress, the problem name can contain directory paths, so that 1002the intermediate files can be written in other directory than the 1003current directory. To allow for this, we allow the user to 1004specifiy a "tem_dir" option for the path. This can have a large impact 1005on performance (elasped time), because the accessing the current 1006directory can be slow (e.g. a NFS file store, like our local file 1007space), and in addition this will allow the user to run their program 1008in a directory they do not have write permission for. </p> 1009<h3> Problem setup and cleanup</h3> 1010Problem setup requires calling many small C externals from the Eclipse 1011code. It is done is three steps. First, cplex_prob_init/8 allocates a C 1012level descriptor including sufficiently large arrays. These arrays are 1013the filled successively using the cplex_set_xxx or cplex_loadxxx 1014functions. When this is finished, cplex_loadprob calls the actual 1015Cplex/Xpress setup routine, passing the previously prepared arrays. In 1016the following, CPH stands for the C level handle, I stands for row 1017numbers, J for column numbers: 1018<ul> 1019 <li> <b>cplex_prob_init(PreSolve,UseCopy,Rows,Cols,NonZeros,ExtraRows,ExtraCols,ExtraNz,Sense,-Handle), 1020p_cpx_prob_init</b></li> 1021 <br> 1022allocates the C-level handle and stores it into the first argument of 1023the Eclipse-level handle. Also allocates arrays for a complete 1024column-wise representation of a problem of the given size (number of 1025rows, columns, nonzeros). An undo-function is trailed which will 1026deallocate the handle with all its arrays on backtracking or garbage 1027collection. The ExtraXXX arguments are no longer needed since Xpress 1028R12. The Presolve argument is either 1 or 0, and the C level 1029descriptor's presolve field is set to this value. At the external 1030solver level, the presolve status is global (for Cplex and Xpress), and 1031before calling any external solver library calls that may be affected 1032by the presolve state, the presolve state is set according to the 1033presolve field. This allows the presolve state to be set on a 1034per-problem basis. 1035</ul> 1036<ul> 1037 <li> <b>cplex_set_rhs_coeff(CPH,I,SenseCode,Rhs), p_cpx_set_rhs_coeff</b></li> 1038 <br> 1039set constraint sense and right hand side for constraint row I. <li> <b>cplex_set_obj_coeff(CPH,J,Val), 1040p_cpx_set_obj_coeff</b></li> 1041 <br> 1042set objective coefficient for variable column J. <li> <b>cplex_set_qobj_coeff(CPH,J1,J2,Val), 1043p_cpx_set_qobj_coeff</b></li> 1044 <br> 1045set quadratic objective coefficient for the product of variables column 1046J1 and J2 <li> <b>cplex_set_bounds(CPH,J,Lo,Hi), p_cpx_set_bounds</b></li> 1047 <br> 1048set bounds of variable column J. <li> <b>cplex_set_type(CPH,J,TypeCode), 1049p_cpx_set_type</b></li> 1050 <br> 1051set type of variable column J. TypeCode is a character C, I or B. <li> <b>cplex_set_matbeg(CPH,J,K,K1), 1052p_cpx_set_matbeg</b></li> 1053 <br> 1054coefficient array locations K to K1-1 contain entries for column J. <li> <b>cplex_set_matval(CPH,K,I,Cij), 1055p_cpx_set_matval</b></li> 1056 <br> 1057set the matrix coefficient for row I and column J (implicit) in 1058coefficient array location K. <li> <b>cplex_set_var_name(CPH, Cj, 1059Name), p_cpx_set_var_name</b></li> 1060 <br> 1061set the name for the variable column J in the external solver. This 1062name will be 1063used 1064when the external solver prints the problem. <li> <b>cplex_loadbase(CPH,Basis), 1065p_cpx_loadbase</b></li> 1066 <br> 1067load a basis (a string buffer, obtained by retrieving from the handle 1068earlier) <li> <b>cplex_loadorder(CPH,Length,OrderList), p_cpx_loadorder</b></li> 1069 <br> 1070load MIP branching order preferences (undocumented feature) <li> <b>cplex_loadsos(CPH,SosType,Size,Js), 1071p_cpx_loadsos</b></li> 1072 <br> 1073load definition of an SOS 1 or 2. Js is a list of length Size of the 1074column numbers that make up the SOS. <li> <b>cplex_loadprob(CPH), 1075p_cpx_loadprob</b></li> 1076 <br> 1077set up the actual solver problem using the (now filled) arrays in the C 1078level handle. <li> <b>cplex_cleanup(CPH), p_cpx_cleanup</b></li> 1079 <br> 1080free the problem descriptor (this also happens on untrailing and 1081garbage collection). 1082</ul> 1083<h3> Problem modification</h3> 1084Most of the modification functions are split into the transfer of the 1085information into growable arrays (hidden on the C level), and a 1086flush-function which conveys the array contents to the actual solver: 1087<ul> 1088 <li> <b>cplex_new_bounds(CPH,J,Lo,Hi), p_cpx_new_bounds</b></li> 1089 <br> 1090set new bounds for variable column J <li> <b>cplex_flush_bounds(CPH), 1091p_cpx_flush_bounds</b></li> 1092 <br> 1093actually transfer the new bounds to the solver <li> <b>cplex_new_obj_coeff(CPH,J,Val), 1094p_cpx_new_obj_coeff</b></li> 1095 <br> 1096set new linear objective coefficients <li> <b>cplex_flush_obj(CPH), 1097p_cpx_flush_obj</b></li> 1098 <br> 1099actually transfer new linear objective coefficients to the solver <li> <b>cplex_new_qobj_coeff(CPH,J1,J2,Val), 1100p_cpx_new_qobj_coeff</b></li> 1101 <br> 1102set new quadratic objective coefficients <li> <b>cplex_new_row(CPH,SenseCode,Rhs,RIdx), 1103p_cpx_new_row</b></li> 1104 <br> 1105start adding a new row with given constraint sense and right hand side. 1106In RIdx the new row's index is returned. <li> <b>cplex_add_coeff(CPH,J,Cij), 1107p_cpx_add_coeff</b></li> 1108 <br> 1109set coefficient for column J in currently added row <li> <b>cplex_flush_new_rows(Handle), 1110p_cpx_flush_new_rows</b></li> 1111 <br> 1112actually transfer one or more new rows and columns to the solver. The 1113new columns have zero values for all the existing (pre-addition) rows. 1114Note the Prolog handle is taken rather than CPH; the timestamp in the 1115Prolog handle is needed for the undo function _cpx_del_rowcols to remove 1116the added rows and columns. <br> 1117 <br> 1118 <li> <b>cplex_change_type(Handle, J, TypeCode), p_cpx_change_type</b></li> 1119 <br> 1120change the type of column J to TypeCode (the code for the type obtained 1121from type_to_cplex_type/4). <br> 1122 <li> <b>cplex_chg_rhs(CPH, I, Rhs), p_cpx_chg_rhs</b></li> 1123 <br> 1124change the rhs value for row I to Rhs. <li> <b>cplex_new_col(CPH), 1125p_cpx_new_col</b></li> 1126 <br> 1127start adding a new column. This is used by column generation, and 1128the column is expected to have non-zero values for the existing rows. 1129This call is follwed by calls to cplex_add_col_coeff to fill in the 1130column's non-zero values in the column-wise buffer arrays (cmatval, 1131cmatind). <li> <b>cplex_add_col_coeff(CPH, I, Val), p_cpx_add_col_coeff</b></li> 1132 <br> 1133set the non-zero coefficient for row I to Val in the currently added 1134column. <li> <b>cplex_flush_new_cols(CPH), p_cpx_new_col</b></li> 1135 <br> 1136actually transfer one or more new non-empty (have non-zero values) 1137columns to the solver. No new rows are added. 1138</ul> 1139For Xpress, only the bounds for a MIP problem can be modified once the 1140MIP search is started. To get round this restriction, we make a copy of 1141the problem, which is pointed to by lpcopy, and solve the problem using 1142the copy so that the original can still be modified. This produces the 1143problem of : <br> 1144 1145<ul> 1146 <li> The problem pointers lp and lpcopy are always present, even when 1147it is not needed. In these cases, lpcopy and lp points to the same 1148problem.</li> 1149</ul> 1150<ul> 1151 <li> When copying is needed, the problem is copied from lp to lpcopy 1152just before it is solved as a MIP problem, and any modifications to the 1153problem is always done to lp, not lpcopy. Once solved, solution data is 1154obtained from the copy until it becomes invalid when the problem is 1155modified (either by forward execution or backtracking in ECLiPSe; the 1156appropriate function must make the copy invalid by changing the 1157copystatus, see next item).</li> 1158</ul> 1159<ul> 1160 <li> In XPRESS 13+, which needs the problem copy for MIP modification, 1161an extra field in lp_desc, <span style="font-weight: bold;">copystatus</span>, 1162is used to specify the status of the copy:</li> 1163</ul> 1164<ul> 1165 <ul> 1166 <li> XP_COPYOFF: we are not using a copy (MIP modification would not 1167be possible, but solving single MIP problems will avoid the copying 1168overhead)</li> 1169 <li> XP_COPYINVALID: the problem in lpcopy is invalid.</li> 1170 <li> XP_COPYCURRENT: the problem in lpcopy is current</li> 1171 </ul> 1172</ul> 1173<div style="margin-left: 40px;">The copystatus is used to determine if 1174information is extracted from lp or lpcopy in procedures that are called 1175independently from ECLiPSe. Currently this applies only to 1176p_cpx_lpwrite(). Other accesses to lpcopy are done in code that occurs 1177in p_cpx_optimise(), after the call to optimise. Here, lpcopy is either 1178valid and pointing to the problem copy with the result of the 1179optimisation, or to lp, if copying is not needed (Cplex, or LP/QP in 1180Xpress).</div> 1181<span style="font-weight: normal;"></span>An LP problem can change into 1182a MIP problem if integers constraints are added. This may happen after 1183the problem is initially loaded. This is not a problem for Cplex, which 1184loads all problems with the same routine. Xpress however, has different 1185routines for loading different problem types. We get around this by 1186always using the `global' loading routine (XPRSloadglobal()) for both 1187LP and MIP problems. If the problem is an LP problem, it is simply 1188solved as an LP problem in XPRSminim/maxim. This apparently has no 1189implications in performance for an LP problem. An LP problem can thus 1190be changed to a MIP problem. On backtracking, this change is undone by 1191_cpx_reset_mip_to_lp() undo function. 1192<p>Unfortunately, when Xpress's solving of an LP problem is aborted, 1193the problem is left in a pre-solved state instead of the original 1194state. The problem can therefore not be modified correctly 1195subsequently. No solution to this problem is implemented currently, but 1196one possible solution is to make copy of an LP problem as well as a 1197MIP problem. </p> 1198<h3> Problem solving and result retrieval</h3> 1199Running the solver is always done with cplex_optimise, regardless of 1200the problem type or the solver method used. 1201<ul> 1202 <li> <b>cplex_optimise(+CPH,+Method,-Result,-Status), p_cpx_optimise</b></li> 1203 <br> 1204run the solver, using the given method (primal,dual,barrier,...). Note 1205however, that for mip problems the methods only specifies the start 1206algorithm, and for qp problems the method is always barrier. Result is 1207the resulting descriptor state (DESCR_XXX) and Status is the underlying 1208solver's own return code (the latter is never interpreted by the 1209Eclipse level code, it is just printed or passed to a user error 1210handler). 1211</ul> 1212There is one function to return the objective value: 1213<ul> 1214 <li> <b>cplex_get_objval(+CPH,-Cost), p_cpx_get_objval</b></li> 1215 <br> 1216get the cost of the solution found <br> 1217 <li> <b>get_darray_element(+Darray,+I,-Value), 1218p_get_darray_element</b></li> 1219 <br> 1220get element I of a darray <br> 1221 <li> <b>darray_list(+Darray,-List), p_darray_list</b></li> 1222 <br> 1223convert a darray to a list of doubles 1224</ul> 1225A <b>darray</b> is actually an Eclipse string, but it contains doubles 1226rather than characters. We use these as the most efficient way of saving 1227large floating point result arrays to the Eclipse global stack. 1228<p>The various results arrays (solution, dual, slacks, reduced costs 1229and basis) are retrieved inside p_cpx_optimise(). This is done either 1230by setting up a callback function (Xpress 13+, MIP problems), or 1231directly after a (successful) optimisation. In Xpress 13+, setting the 1232callback function avoids Xpress writing solution files during MIP. Note 1233that some files are still created during the MIP search, however. The 1234cleanup routines (p_cpx_cleanup()) will delete any such file for the 1235current session, but if it is not called (e.g. because of some crash), 1236then extra files may be left behind. </p> 1237<h3> Retrieving problem data</h3> 1238These are non-essential functions, used to retrieve information from 1239the C level handle: 1240<ul> 1241 <li> <b>cplex_get_prob_param(+CPH,+Which,-Value), p_cpx_get_prob_param</b></li> 1242 <br> 1243retrieve handle-specific properties (problem type, last status) and 1244statistics (size, counters) <li> <b>cplex_get_type_and_bounds(+CPH,+J,-TypeCode,-Lo,-Hi), 1245p_cpx_get_type_and_bounds</b></li> 1246 <br> 1247get type and bounds of variable column J <li> <b>cplex_get_row(+CPH,+I), 1248p_cpx_get_row</b></li> 1249 <br> 1250prepare retrieval of row information for row I <li> <b>cplex_get_rhs(+CPH,+I,-SenseCode,-Rhs), 1251p_cpx_get_rhs</b></li> 1252 <br> 1253get current row's sense and right hand side <li> <b>cplex_get_col_coef(+CPH,+J,-Cij), 1254p_cpx_get_col_coef</b></li> 1255 <br> 1256get coefficient of current row, column J <li> <b>cplex_get_obj_coef(+CPH,+J,-C), 1257p_cpx_get_obj_coef</b></li> 1258 <br> 1259get objective coefficient for column J 1260</ul> 1261<h3> Other functions</h3> 1262<ul> 1263 <li> <b>cplex_get_param(ParamName,Value), p_cpx_get_param</b></li> 1264 <br> 1265get a global parameter setting. The ParamName is an atom. The result 1266type is implicit (float,integer,string). This uses the name mapping 1267table in eplex_params.h <li> <b>cplex_set_param(ParamName,Value), 1268p_cpx_set_param</b></li> 1269 <br> 1270set a global parameter. The ParamName is an atom. The required value 1271type is determined by the parameter itself. <li> <b>cplex_lpwrite(File,Format,Handle), 1272p_cpx_lpwrite</b></li> 1273 <br> 1274write the problem in a prticular format to File. Cplex supports several 1275formats, Xpress only 'mps' format. <li> <b>cplex_lpread(File,Format,Handle), 1276p_cpx_lpread</b></li> 1277 <br> 1278read a problem from a file. This only works in Cplex and is neither 1279widely used nor well tested. <li> <b>cplex_lo_hi(NegInf,PosInf), 1280p_cpx_lo_hi</b></li> 1281 <br> 1282returns the solver's idea of negative and positive infinity (something 1283like 1e20) <li> <b>cplex_output_stream(ChannelNr,AddRem,StreamNr), 1284p_cpx_output_stream</b></li> 1285 <br> 1286associate or disassociate a Cplex I/O channel (result_channel (0), 1287error_channel(1), warning_channel(2), log_channel (3)) with the given 1288Eclipse stream StreamNr. Xpress has a similar concept of 4 message 1289levels 1290</ul> 1291<center> 1292<table border="1" cols="5" width="80%" nosave=""> 1293 <caption><br> 1294 <center> 1295 <p></p> 1296 </center> 1297 </caption><tbody> 1298 </tbody><tbody> 1299 </tbody> <tbody> 1300 <tr bgcolor="#cccccc" nosave=""> 1301 <td nosave="">Eclipse level name</td> 1302 <td>ChannelNr</td> 1303 <td>Cplex</td> 1304 <td>Xpress msg type</td> 1305 <td>Default Eclipse stream</td> 1306 </tr> 1307 <tr nosave=""> 1308 <td>result_channel</td> 1309 <td>0</td> 1310 <td nosave="">result</td> 1311 <td>2</td> 1312 <td>-</td> 1313 </tr> 1314 <tr nosave=""> 1315 <td>error_channel</td> 1316 <td>1</td> 1317 <td nosave="">error</td> 1318 <td>4</td> 1319 <td>error</td> 1320 </tr> 1321 <tr> 1322 <td>warning_channel</td> 1323 <td>2</td> 1324 <td>warning</td> 1325 <td>3</td> 1326 <td>warning_output</td> 1327 </tr> 1328 <tr> 1329 <td>log_channel</td> 1330 <td>3</td> 1331 <td>log</td> 1332 <td>1</td> 1333 <td>-</td> 1334 </tr> 1335 </tbody> 1336</table> 1337</center> 1338<br> 1339 1340<h3> Undo functions</h3> 1341These functions are setup using ec_trail_undo, which places the 1342function on the trail such that it is called when untrailed. 1343Additionally, ec_trail_undo allows a time-stamped trailing so that the 1344function will only be trailed if the time-stamp is `old' (older than 1345the most recent choicepoint). 1346<ul> 1347 <li> <span style="font-weight: bold;">_untrail_cleanup </span>*non 1348time-stamped*</li> 1349</ul> 1350<div style="margin-left: 40px;">calls p_cpx_cleanup, and then free the 1351problem descriptor. Trailed during p_cpx_prob_init so problem space can 1352be freed upon backtracking</div> 1353<ul> 1354 <li> <span style="font-weight: bold;">_cpx_reset_mip_to_lp </span>*non 1355time-stamped*</li> 1356</ul> 1357<div style="margin-left: 40px;">reset a problem type from MIP to 1358LP. CPLEX has to be informed of the changed as well (but not 1359XPRESS). Trailed when problem is changed from LP to MIP. In future 1360versions, this function may be extended to change a QPMIP problem back 1361to a QP problem</div> 1362<ul> 1363 <li style="font-weight: bold;"> <b>_cpx_reset_col_type</b> <span 1364 style="font-weight: normal;">*non time-stamped*</span></li> 1365</ul> 1366<div style="margin-left: 40px;">change a column back to its original 1367type. Trailed when a column type is changed in p_cpx_change_type. The 1368untrail data contains the column's number and the original type. This 1369function is not time-stamped because each column can only change 1370type at most twice (C -> I -> B).</div> 1371<ul> 1372 <li style="font-weight: bold;"> <b>_cpx_del_rowcols</b> <span 1373 style="font-weight: normal;">*time-stamped*</span></li> 1374</ul> 1375<div style="margin-left: 40px;">delete added rows (and any added 1376columns) from a problem matrix. Rows are always added incrementally, so 1377only one delete is needed per choice-point even if there were many row 1378additions. The same time-stamp as _cpx_reset_col_type is used, as there 1379is no need to reset the types of columns that are deleted. Trailed 1380during p_cpx_flush_new_rows or p_cpx_flush_new_cols. Untrail data 1381contains the old column and row sizes.</div> 1382<br> 1383 1384<h3> Multiple handles</h3> 1385While Cplex has always had problem handles, these need to be simulated 1386for older (pres-13) versions of Xpress. We will not disucss 1387this further as more recent versions of Xpress also have problem 1388handles. 1389<h3> Memory allocation</h3> 1390Memory in eplex.c is allocated through the macros Malloc(), Realloc() 1391and Free(), which are normally set to the standard C library's 1392allocation functions, but can be redefined for debugging purposes. Note 1393that we have no control over the memory allocation of the actual solver 1394library! 1395<h3> Global Parameters</h3> 1396Cplex and Xpress have a large number of parameters that affect their 1397behaviour. Only a few of them coincide with their meaning. We have 1398therefore decided to map the parameter access one-to-one from the C 1399level to the Eclipse level. While the rest of eplex tries hard to hide 1400all the differences between Cplex and Xpress, the parameter setting is 1401the exception. <br> 1402To make things worse, every new release of Cplex or Xpress comes with a 1403modified set of parameters. We have therefore introduced a fixed 1404mapping from the parameter names in the solver's C interface to the 1405(atomic) parameter name that is used on the Eclipse level, e.g. 1406<blockquote>Cplex's <tt>CPX_PARAM_NODELIM</tt> becomes <tt>nodelim</tt> <br> 1407Xpress's <tt>MAXNOD</tt> or <tt>N_MAXNOD</tt> becomes <tt>maxnod</tt></blockquote> 1408The mapping is defined in the file eplex_params.h, which unfortunately 1409must be updated for every new solver release. The comment at the 1410beginning of the file explains how to do the job semi-automatically 1411using editor commands. 1412<h3> Solver Numerical Differences</h3> 1413The external solver may give different results depending on the 1414FPU control settings. One example that affects XPRESS 13.26 under 1415i386_linux is that the floats are normally in `extended precision' of 141680 bits in the hardware registers. This is the default used when 1417ECLiPSe is started. However, if embedded Java is used, Java sets the 1418float precision to double, i.e. 64 bits. With XPRESS 13.26, this can 1419result in different behaviours of the solver, e.g. Retimer can give 1420different alternative answers. 1421<h3>Debugging the External Solver</h3> 1422When an error occurs in using eplex (program crash, unexpected abort, 1423or incorrect result returned), the error can be due to ECLiPSe 1424(either C or Prolog level), or the external solver. In the case of the 1425external solver, we cannot fix the bug, but we can report it so that it 1426can be fixed (and perhaps workaround the problem in our own code).<br> 1427<br> 1428In order to report a problem to Dash or ILOG, we need to show that the 1429problem<br> 1430is due to their external solver. Several methods are available to do 1431this:<br> 1432<ul> 1433 <li>if the problem occur while the external solver is solving a 1434problem, the problem state can be saved before it is solved by the 1435external solver. If the problem also occurs when the saved problem is 1436loaded back into (an interactive) session of the solver, then the saved 1437problem can be used in the bug report. Eplex supports the saving of a 1438problem before solving it with the option write_before_solve when the 1439problem is setup. The problem is written using as high a 1440precision as possible when written as lp or mps format. However, 1441sometimes the problem may not occur with these formats, but would occur 1442when written using the binary format. The disadvantage of the binary 1443format is that it is solver and platform specific, and is non 1444human-readable.</li> 1445 <li>log the external solver calls by eplex. See next section for more 1446details.</li> 1447</ul> 1448Other useful methods to aid in debugging is to run the whole ECLiPSe 1449session under a memory debugger like valgrind. This can show up 1450problems both in ECLiPSe and the external solver.<br> 1451<h4><a name="Logging"></a>Logging External Solver Calls</h4> 1452There are extra code at the C level which are used to generate a log of 1453the calls made to the external solver. These code are only compiled if 1454the macro LOG_CALLS is defined. The log consists of the calls, plus 1455extra support code, so that only a header file and the toplevel 1456procedure need to be added to generate a pure C program, which can then 1457be used to make bug reports to Dash or ILOG. <br> 1458 1459<h4> Structure of the log code</h4> 1460The log code consists of a number of step_N procedures, where N is an 1461integer. Each such procedure makes a call to the appropriate optimise 1462function of the external procedure, after setting up the data and 1463making the other supporting calls to the solver. After the optimise 1464call, a new step_N procedure, with N incremented by 1. 1465<p>The data needed for the calls is stored in the same C level problem 1466descriptor lp_desc that the eplex code used. This is defined in an 1467include file, along with some procedures and variables that the log 1468code use. There are three include files, for the three versions of log 1469code generated: <br> 1470 <br> 1471<table border="1" cellspacing="2" cellpadding="2" width="100%" 1472 style="text-align: left;"> 1473 <caption><br> 1474 </caption><tbody> 1475 </tbody> <tbody> 1476 <tr> 1477 <td valign="top">Xpress 13+</td> 1478 <td valign="top">bugxprs.h</td> 1479 </tr> 1480 <tr> 1481 <td valign="top">Xpress 12</td> 1482 <td valign="top">bugxprs12.h</td> 1483 </tr> 1484 <tr> 1485 <td valign="top">CPlex (6.5+)</td> 1486 <td valign="top">bugcpx.h</td> 1487 </tr> 1488 </tbody> 1489</table> 1490</p> 1491<p>The include file has the following support variables: </p> 1492<p>struct lp_desc *lpd; <br> 1493struct lp_desc *lpdmat[20]; /* change size if more lpd used */ <br> 1494double objval; <br> 1495int res,err; </p> 1496<p>lpdmat[] is an array to support multiple handles. The generated log 1497code loads the appropriate lp_desc from lpdmat into lpd at the start of 1498a step_N procedure, and at any time the handle changes. Note that the 1499size of lpdmat may need to be adjusted upwards if the logged program 1500uses more handles than is defined. objval is used to store the 1501objective value if required (getting the objective value is not 1502automatically generated in the log code), and res and err are used to 1503store any return codes from function calls. </p> 1504<p>Finally, a main procedure needs to be added to call all the step_N 1505procedures in sequence, e.g. if there are three steps, and the 1506solver is Xpress 13+: </p> 1507<p> main() { <br> 1508 XPRSinit(NULL); <br> 1509 XPRScreateprob(&cpx_env); <br> 1510 step_0(); <br> 1511 step_1(); <br> 1512 step_2(); <br> 1513} </p> 1514<p>In this case, the cpx_env is the dummy problem where all the default 1515parameter values are stored. <br> 1516 </p> 1517<h4> <a name="Logging_macros"></a>Logging macros</h4> 1518Several macros are defined to minimise the amount of special logging 1519code needed: 1520<ul> 1521 <li> <span style="font-weight: bold;">Call(Ret, Proc)</span>: 1522Generates a call to Proc in the form Ret = Proc, and a log for Proc if 1523LOG_CALL is defined.</li> 1524 <li> <span style="font-weight: bold;">CallN(Proc)</span>: Generates a 1525call to Proc in the form Proc, and a log for Proc if LOG_CALL is 1526defined. This should be used if Proc should be called without getting 1527the return code.</li> 1528 <li> <span style="font-weight: bold;">Log1(Proc, A1)</span>: 1529Generates a log for Proc if LOG_CALL is defined. No actual call is 1530generated, so seperate code for the call is needed. This macro should 1531be used when an argument for Proc needs to be supplied dynamically at 1532run-time. Proc can be written in printf style with a leading % for the 1533argument supplied in A1.</li> 1534 <li> <span style="font-weight: bold;">Log2(Proc, A1, A2)</span>: Same 1535as Log1, except it allows two dynamic arguments.</li> 1536 <li> <span style="font-weight: bold;">Log3(Proc, A1, A2, A3)</span>: 1537Same as Log1, except it allows three dynamic arguments.</li> 1538 <li> <span style="font-weight: bold;">Log4(Proc, A1, A2, A3, A4)</span>: 1539Same as Log1, except it allows four dynamic arguments.</li> 1540 <li> <b>Log5(Proc,A1,A2,A3,A4,A5):</b> Same as Log1, except it allows 1541five dynamic arguments.</li> 1542</ul> 1543In addition, logging code is also given between #ifdef LOG_CALLS, e.g. 1544for loading the various data structures. 1545<p>The logged call is generated by printfs, to the log_output stream. 1546In order to allow macro transformation for the logged code to be 1547performed, the call is wrapped in a Transform_Quoted macro, which 1548performs the transformation even though the logged call occurs inside 1549the printf quotes. <br> 1550 <br> 1551 </p> 1552</body> 1553</html> 1554
