1<!DOCTYPE html PUBLIC "-//w3c//dtd html 4.0 transitional//en"> 2<html> 3<head> 4<!-- BEGIN LICENSE BLOCK 5 - Version: CMPL 1.1 6 - 7 - The contents of this file are subject to the Cisco-style Mozilla Public 8 - License Version 1.1 (the "License"); you may not use this file except 9 - in compliance with the License. You may obtain a copy of the License 10 - at www.eclipse-clp.org/license. 11 - 12 - Software distributed under the License is distributed on an "AS IS" 13 - basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See 14 - the License for the specific language governing rights and limitations 15 - under the License. 16 - 17 - The Original Code is The ECLiPSe Constraint Logic Programming System. 18 - The Initial Developer of the Original Code is Cisco Systems, Inc. 19 - Portions created by the Initial Developer are 20 - Copyright (C) 2006 Cisco Systems, Inc. All Rights Reserved. 21 - 22 - Contributor(s): 23 - 24 - END LICENSE BLOCK --> 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.76 [en] (X11; U; SunOS 5.7 sun4u) [Netscape]"> 30</head> 31<body> 32 33<h1>Implementation Notes for lib(eplex), in ECLiPSe 5.10</h1> 34Author: Joachim, Kish 35<br> 36Date: Nov 2006 37<br> 38Revision history: July 2003: Taken from lib(eplex) implementation notes 39(5.6), revised Jan 2004 (5.7), Jan 2005 (5.8), Feb 2005 (5.9), July 402005 41(5.9), May 2006 (5.9), Aug 2006 (Osi),<br> 42Nov 2006 (5.10)<br> 43Contents: 44<blockquote> <a href="#Intro">#Introdcution</a> <br> 45 <a href="#Global%20structure"> #Global structure</a> <br> 46 <a href="#Eclipse%20Code%20Level">#Eclipse Code Level</a> <br> 47 <a href="#C%20Code%20Level">#C Code Level</a></blockquote> 48<h2> 49<a name="Global structure"></a><u>Global structure</u></h2> 50<h3> 51Files</h3> 52The bulk of the code are in eplex_s.ecl and seplex.c. 53<br> 54<br> 55Components: 56<ul> 57 <li> <b>seplex.c</b>: low level functions, lots of ifdefs for CPLEX 58and 59XPRESS 60and different versions of them (modified from eplex.c)</li> 61 <li> <b>eplex.pl</b>: top-level wrapper for loading the eplex/seplex 62library</li> 63 <li> <b>eplex_standalone.ecl</b>: provides the 64standalone 65specific macros and support. This is loaded by eplex.pl if seplex 66is selected. In turn it loads eplex_s.ecl, where the bulk of the 67ECLiPSe 68code for seplex is. There are two modulles, eplex and eplex_s. This 69file was needed when there was standalone and ic/range eplexes. <br> 70 </li> 71 <li> <b>eplex_s.ecl</b>: generic (independent of cplex/xpress) code 72implementing 73the library functionality. This code is loaded into the eplex_ module 74(modified 75from eplex_.ecl).</li> 76 <li> <b>s_eplex_xpress.pl and s_eplex_cplex.pl</b>: trivial wrappers 77for 78eplex.pl 79to force loading of either solver with seplex</li> 80 <li> <b>s_eplex_comments.ecl</b>: the comment directives 81documentation 82for seplex 83(modified from eplex_comments.eci).</li> 84 <li> <b>eplex_lic_info.pl:</b> data file that can be edited by the 85user 86(which 87licence on which machine). Also determines the default solver.</li> 88 <li> <b>empty_language.ecl: </b>contains the small set of 89predicates 90that are 91needed in the dummy modules used to select external solver/bounds 92keeper.</li> 93 <li> <b>eplex_params.h</b>: contains a C table to map the 94CPLEX/XPRESS/OSI 95parameter 96value to symbolic names used on the Eclipse level. This is created 97semi-automatically 98from the xpresso.h or cplex.h respectively.</li> 99 <li><span style="font-weight: bold;">seplex.h:</span> header 100file for eplex: used by seplex.c and coinplex.cpp, for common 101declarations used in both files. Also used for compiling loged cide,<br> 102 </li> 103 <li><span style="font-weight: bold;">coinplex.cpp</span>: C++ code 104interface to OSI solvers, provides the API that seplex.c calls for the 105OSI solvers. <br> 106 </li> 107 <li> <b>seplex_xpress.def and seplex_cplex.def</b>: DLL export 108specification 109for the Windows build</li> 110 <li> <b>WinMSC/Standalone</b>: the corresponding projects for the 111Windows build (no longer used with Windows cross-compiling)<br> 112 </li> 113</ul> 114<li> 115Related:</li> 116<ul> 117 <li>lib(linearize): used to linearize arithmetic expressions</li> 118 <li>lib(var_name): provides stable variable name support</li> 119 <li>lib(constraint_pools): support for eplex instances</li> 120</ul> 121<h3> 122Modules</h3> 123eplex_s.ecl contains two modules <b>eplex</b> and <b>eplex_s.</b> 124Most 125of the code is in eplex_ s and reexported through eplex. The reason to 126have eplex_ s at all is that eplex redefines the arithmetic predicates 127(>, >=, ...) which would be inconvenient to have in the actual 128implementation 129module. 130<p>There are several dummy modules, <b>eplex_cplex,</b> <b>eplex_xpress</b>, 131<span style="font-weight: bold;">eplex_osi</span> and <span 132 style="font-weight: bold;">eplex_osi_*</span>, 133(defined in the corresponding files). They don't contain anything. The 134only effect is that eplex_s.ecl attempts to load the Cplex version when 135the 136module eplex_cplex exists, and the Xpress version when module 137eplex_xpress 138exists, etc.. If none of them exist, the loaded solver is solely 139determined 140by 141the eplex_lic_info file. More specific dummy modules can also be 142created 143by the user to specify the exact solver version to load, in the 144form 145eplex_<solver>_<version>, e.g. <b>eplex_xpress_1427icp </b>for 146the 147OEM (`icp') version of Xpress 14.27. Note that `version' for OSI 148indicates the actual solver (or combiation of solvers) used through the 149OSI interface. The available versions can 150be 151found by examining the binaries that are built, which has the same 152version 153information appended to the end of the file/directory names to allow 154binariies 155for more than one version of the same solver, e.g. express1417icp.so. 156</p> 157<p>The dummy modules now reexports empty_language. This restricts the 158defined 159predicates in these modules to the very small subset of built-in 160predicates 161re-exported from sepia_kernel by empty_language. This subset are 162the predicates that are actually used in these modules. This was done 163to 164avoid the confusion that these dummy modules might be eplex instances 165that 166the user can post constraints to. This will now raise an `undefined 167predicate' 168error. 169</p> 170<h3>Debugging</h3> 171The C code is littered (and made even more unreadable) by macros which 172can be used to produce a trace of all XPRESS/CPLEX functions that get 173called. 174This trace can be turned into a pure C bug report, so that any external 175solver bugs can be isolated from ECLiPSe. See section on <a 176 href="#Logging">logging</a>. 177<h2><a name="Eclipse Code Level"></a><u>Eclipse Code Level</u></h2> 178<h3> 179Licences and versions</h3> 180Quite a bit of code at the beginning of eplex_s.ecl deals with finding 181the right version of the C code to load and obtaining a licence 182(because 183the underlying solver is usually licence-protected). We use a little 184database 185file that tells the library which solver and version to use on a 186particular 187host, and where to find the licence for this solver. The information is 188held in the file <b>eplex_lic_info.ecl</b> in the Eclipse lib 189directory. 190If more than one solver are available on a particular host, the 191selected 192solver is 193<ul> 194 <li>Solver given in * (where * is an available solver), if 195lib(eplex_*) was called</li> 196 <li>the first one listed in <b>eplex_lic_info.ecl</b> if lib(eplex) 197was 198called</li> 199 <li>if no solvers are listed in eplex_lic_info.ecl, then the first 200solver found in the directry listing.<br> 201 </li> 202</ul> 203It is not possible to have two different external solvers in the same 204Eclipse 205session. 206<br> 207The pair of predicates lp_get_licence/0 and lp_release_licence/0 obtain 208or release a licence. lp_get_licence/0 fails if no licence is availble, 209but it can be called again until one becomes available. On loading, the 210library tries to grab a licence, and prints a warning if this is not 211possible. <br> 212<p>We also have OEM versions of Xpress that can be used with ECLiPSe 213which 214the user can use without obtaining an Xpress license from Dash. This 215checking 216is done at the C level (in p_cpx_init()) if the macro 217XPRESS_OEM_ICPARC_2002 218is defined. It is done in C to avoid checking for 32 bit overflow: the 219formular used by Dash requires 32 bit integers to work correctly, 220whereas 221in ECLiPSe, integers > 32 bits will become bignums. Different keys 222are 223needed for the different versions of Xpress, and this is hard-coded 224into 225the C code via macros.<br> 226</p> 227<p>For OSI, lp_get_licence/0 is used only to determine the solver to 228load, and not obtain any <br> 229licenses. This is because OSI does not provide any provisions to obtain 230licenses: open-source solvers will not require licenses, and for 231commercial solvers, the license has<br> 232to be obtained using the normal mechanisms provided by the solver (e.g. 233by setting environment variables). <br> 234</p> 235<p><br> 236</p> 237<h3>Attribute</h3> 238Eplex variables have the following attribute: 239<pre>:- export struct(<br> eplex(<br> stamp, % time stamp for this variable in this solver. <br> solver, % A solver that this variable occurs in<br> idx, % The column number(s) 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> 240The eplex attribute consists of a chain of one or more attribute 241structures. Each attribute structure belongs to a specific solver 242state. Together they represent the eplex problems the particular 243variable 244occurs in. 245<p>The <b>solver</b> field contains <i>one of the problem handles 246where 247the variable occurs,</i> and the attribute represents the 248variable 249in that problem. This is normally one column in the problem matrix, but 250if the variable has been unified with other problem variables, 251then 252it may represent multiple columns in the same problem. See <a 253 href="#mergecol">#mergecol</a> 254<br> 255<b>idx </b>is a list of the column numbers represented by the 256attribute. 257This information is mainly needed in lp_var_get/4 to retrieve 258variable-related 259information such as the lp solution. This link is the main problem when 260we consider dealing with multiple solver handles simultaneously. 261<br> 262The <b>intol_inst</b> waking list is only used for a very special 263purpose, 264namely waking when the variable gets instantiated to a value that is 265outside 266of a certain tolerance from the lp solution. The tolerances can be set 267by using lp_set/3 on the solver handle and are different for continuous 268and integer variables. 269</p> 270<p>The stamp field is needed at the C level, it is used for 271timestamping 272in the undo functions that affects this variable in the solver (i.e. 273the 274column idx in the matrix), e.g, bounds and type for the column. 275</p> 276<p>The <span style="font-weight: bold;">next </span>field 277points 278to the next attribute structure, or the atom end if there are 279none. 280An atom instead of a variable is used to terminate the chain to avoid 281potential 282problems with using setarg (setarg needs to be used as the chain needs 283to be modified in cases like when an attribute is discarded (see 284unification 285of attribute chains below)). <b><i>Each attribute structure in a chain 286must refer to a different solver state.</i></b> This assumption 287is 288made in many of the routines that handle the attribute chains. 289</p> 290<pre>:- meta_attribute(eplex, [<br> print:lp_var_print/2,<br> unify:unify_eplex/2,<br> get_bounds:lp_attr_get_bounds/3,<br> set_bounds:lp_attr_set_bounds/3,<br> suspensions:suspensions_eplex/3<br> ]).</pre> 291In general, the attribute handlers have to handle every single 292attribute 293structure in the chain. The attribute print handler prints the range 294and 295lp solutions (if it exists) of all the attribute structures in 296the 297chain(using the solver/idx fields in the attribute). The unify handler 298is responsible for: 299<ul> 300 <li>schedulting the intol_inst list if necessary</li> 301 <li>when the variable is instantiated to a number, update the column 302bounds 303in all the external solver state(s) where the variable occurs. The 304upper 305and lower bounds are set to the numeric value of the number [This is 306done 307with seplex only as bounds are no longer synchronnised]. In 308addition, 309the demon solver (for the attribute) is triggered if 310bounds/deviating_bounds 311was specified as triggering conditions, and the condition is met. Note 312this is not implemented using the normal suspension list mechanism as 313we 314have access to the solver suspension directly from the attribute: we 315directly 316call schedule_suspensions/2 with the suspension in a dummy goal.</li> 317 <li>merging the eplex attribute chains when two eplex variables are 318unified:</li> 319 <ul> 320 <li>transfer the attribute chain if necessary if only one variable 321is an 322eplex 323variable.</li> 324 <li>if both are eplex variables, their chain is merged. The chain 325needs to 326be checked to see that the two chains do not contain attributes 327structures 328for the same solver state. If they do, one of the attribute structure 329is 330discarded, and an equality constraint send to the solver state. The 331event<b> 332lp_unify_same_handle </b>is also raised.</li> 333 </ul> 334</ul> 335<h3> 336Problem Handle</h3> 337What we call a <b>problem</b> in the following consists of 338<ul> 339 <li>a set of constraints, including bounds constraints</li> 340 <li>an objective function</li> 341 <li>the variables that occur in these constraints or the objective 342function</li> 343 <li>a (possibly empty) subset of these variables that are considered 344integers</li> 345 <li>a number of option settings</li> 346</ul> 347Multiple problems are supported by eplex, each problem having its own 348handles.We 349have problem handles on several levels: 350<ol> 351 <li> <b>Eclipse level:</b> this is an Eclipse structure (<b>struct 352prob</b> 353), its fields are backtracked, the first field refers to the C level 354descriptor</li> 355 <li> <b>C level:</b> this is a C structure (<b>struct lp_desc</b>), 356its 357fields 358are non-backtracked, it refers among others to the solver state 359descriptor</li> 360 <li> <b>CPLEX/XPRESS level:</b> this is the solver's problem handle 361(if 362any) 363which is a black box for us. We refer to this as the solver state.</li> 364</ol> 365The <b>Eclipse handle</b> contains all the information we want to hold 366on the Eclipse level, for whatever reason (because it it more 367convenient, 368because it is logical storage, etc). Among the fields are: 369<pre>:- export struct(<br> prob(<br> cplex_handle, % handle to C data structure<br>...<br> vars, % [Xn,...,X1]: list of problem variables<br> ints, % [Xi1,...Xik]: list of integer variables<br>...<br> presolve, % 1 for yes, 0 for no<br> use_copy, % 1 for yes, 0 for no<br>...</pre> 370<pre> 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> 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> 371The <b>vars</b> list keeps a reference to all the variables involved 372in 373the problem. The variables in the list are in reverse coluumn order 374(i.e. 375first column at the tail of the list). The variables that are treated 376as 377integers by the solver are stored in an additional list <b>ints</b>. 378If 379this list is empty, we only solve LP problems! 380<br> 381<a name="presolve"></a>The <span style="font-weight: bold;">presolve </span>field 382specifies the presolve setting for this problem. If the solver supports 383only global parameter, then this local setting for presolve is 384simulated 385at the C-level by changing the parameter whenever it is needed for the 386problem. In addition, some solvers may have more than a simple binary 387setting 388for the presolve, and indeed different parameters for the MIP and LP 389presolves 390(Xpress). In this case, the <span style="font-weight: bold;">presolve </span>setting 391maps to all problem types with some default values when presolve is on. 392<br> 393The <span style="font-weight: bold;">use_copy</span> field 394specifies 395if a copy of the problem at the C-level should be used when a MIP 396problem 397is solved. Using a copy allows a MIP problem to be modified when 398Xpress 399is used; as otherwise Xpress does not allow a MIP problem to be 400modified 401(beyond changing bounds) once the MIP search has started.<span 402 style="font-weight: bold;"></span> 403<br> 404The <b>method</b> and <b>demon_tol </b>fields store control 405parameters 406for the solver (others are stored on a lower level). 407<br> 408The remaining group are solver results: <b>status</b> is an integer 409that contains the underlying solver's last return status (not normally 410needed by the programmer). <b>cost</b> is the cost of the last 411solution 412that was computed. 413<br> 414The subsequent <b>arrays</b> contain the result values belonging to 415that solution. Note that not all these arrays need to be in use. When 416they 417are initialised to free variables, they remain unused. When they are 418initialised 419to nil, they will be setarg'd to new arrays after every successful run 420of the solver. This initialisation is done by the corresponding solver 421options (in lp_setup/3 or later via lp_set/3): 422<center><br> 423<table nosave="" border="1" cols="3" width="60%"> 424 <caption> 425 <center> 426 <p></p> 427 </center> 428 </caption><tbody> 429 </tbody><tbody> 430 </tbody><tbody> 431 </tbody><tbody> 432 </tbody><tbody> 433 </tbody> <tbody> 434 <tr nosave="" bgcolor="#cccccc"> 435 <td nosave=""><b>Result option name</b></td> 436 <td><b>Default setting</b></td> 437 <td><b>Array name in prob</b></td> 438 </tr> 439 <tr> 440 <td>solution</td> 441 <td>yes</td> 442 <td>sols</td> 443 </tr> 444 <tr> 445 <td>dual_solution</td> 446 <td>no</td> 447 <td>pis</td> 448 </tr> 449 <tr> 450 <td>slack</td> 451 <td>no</td> 452 <td>slacks</td> 453 </tr> 454 <tr> 455 <td>reduced_cost</td> 456 <td>no</td> 457 <td>djs</td> 458 </tr> 459 <tr> 460 <td>keep_basis</td> 461 <td>no</td> 462 <td>base</td> 463 </tr> 464 </tbody> 465</table> 466</center> 467<p>Note again that this is <i>logical storage</i> which is properly 468reset 469on backtracking, while everything that is stored at the C level is not. 470Where reset is needed at the C level, explcit "undo functions" needs to 471be trailed. 472</p> 473<h3>Support for cutpool constraints</h3> 474Cutpool constraints (`global cuts') are supported from version 5.9. The 475support is mainly at the C level, where the cutpool constraints are 476stored. The solving process is also mdified from previously, as a call 477to the external solver can now result in multiple invocations of the 478external solver. See <a href="#cutpool">here</a> for the ECLiPSe level 479descriptions, and <a href="#cutpoolc">here</a> for the C level 480descriptions.<br> 481<h3>Support for column generation</h3> 482The column generation library uses the eplex library. The 483main 484support provided by eplex for column generation are: 485<blockquote> 486 <ul> 487 <li>returning row indicies for the added constraints 488(lp_add_constraints/4)</li> 489 <li>adding columns with coefficients for existing rows, and also a 490non-zero 491objective coefficient (lp_add_columns/2)</li> 492 <li>retreiving column data from the ECLiPSe level</li> 493 </ul> 494</blockquote> 495<h3> 496Support for multiple problems<br> 497</h3> 498<p>As disccused under the attribute section, multiple problems are 499supported in the ECLiPSe level with chains of eplex attributes. A 500variable 501can be involved in multiple eplex problems, each with a different 502solver state, and each attribute structure within the eplex attribute 503for 504the variable represents one solver state. 505</p> 506<p>Each ECLiPSe problem handle is given a unique integer id, the <b>solver 507id</b> . Each time a solver state is created, it is assigned a new 508solver 509id maintained within a global reference, whose value is incremented for 510the next solver id. The solver id is stored into the <b>solver_id</b> 511field 512of the problem handle for the solver state, and is used to identify the 513solver state within the ECLiPSe code for the library, for 514example, 515in predicates which needs to access a specific eplex attribute 516structure 517in a chain. 518</p> 519<p>The concept of <a href="#Eplex_instances">eplex instances </a>is 520used 521to represent multiple eplex problems at a high-level. This allows 522constraints 523for an eplex problem to be posted before a solver state is set up for 524it. 525Note that the eplex attribute structure is not created until the solver 526state is set up. 527</p> 528<h3>Managing solver parameters</h3> 529With Xpress 13+, the solver parameters are specific to each problem and 530there are no global parameters. With Cplex and older Xpresses, the 531parameters 532are global (i.e. applies to all problems). This difference 533unfortunately 534cannot be hidden from the user. An additional complication is that 535currently 536a ECLiPSe level problem may not yet have a C-level solver handle (e.g. 537if the problem was empty). This is an issue if the solver parameters 538are 539problem specific.<br> 540<p>We allow access (get/set) to these parameters via the problem handle 541(or eplex instance)[local access], or `globally', without specifying 542any 543handle/instance. The exact meaning of `global' parameter depends on if 544the solver has global parameters or not: 545</p> 546<ol> 547 <li>solver has global parameters: acess to global parameters in eplex 548directly 549accesses the corresponding solver parameter.</li> 550 <li>solver has no global parameters: `global' parameters are the 551default 552settings 553for the parameters, i.e. the values that would be given to a new 554problem 555when it is set up (at the C level). It does <span 556 style="font-style: italic;">not </span>affect 557any existing problem's parameter.</li> 558</ol> 559Thus, the two cases of the global parameters behaves in the same way 560only 561if the parameters are accessed before any problem setup. 562<p>We do not allow the user to<span style="font-weight: bold;"> 563set </span>a 564solver parameter locally if the solver has global parameters only, 565because 566this would have the `side effect' of changing this parameter globally. 567</p> 568<p>OSI provides a small number (less than 10) of parameters, and the 569interface treats them as problem specific. Only the most basic and 570common parameters are provided, and not all of them useful in the eplex 571context. We provide access to those parameters that are useful, and in 572addition, to some solver specific parameters, and also some parameters 573to how eplex<br> 574itself behaves at the OSI interface level. For the eplex user, all 575these parameters<br> 576are seen uniformly as optimizer_param.<br> 577</p> 578<p>Note that the <span style="font-weight: bold;">presolve </span> 579and<b> timeout </b>parameters are treated specially. They do not 580correspond 581directly to the low level parameters of the solver. Instead they alway 582behave as if the parameter is local, i.e. it is specific to each 583problem, 584and if set globally, it sets the default value. With solvers that only 585has global parameters, the local behaviour is simulated as discussed <a 586 href="#presolve">here.</a> 587</p> 588<p>The default values for parameters in Xpress 13+ is stored in a dummy 589problem which is created on initialisation. The values of these 590parameters 591are copied into each new problem that are created. 592</p> 593<p>When used from ECLiPSe, these parameters are wrapped in an 594optimizer_param/1 595structure, to clearly show that they are optimizer (and version) 596specific. 597We also provide two special aliases that do not need the 598optimizer_param/1 599wrapping:<span style="font-weight: bold;">presolve</span>, as discussed 600above, and <span style="font-weight: bold;">timeout</span>. This 601allow 602the user to avoid version specific code for these common cases, and 603also 604not needing to worry about the differences in the actual solver 605parameter 606(different names, different argument type, different semantics). 607</p> 608<h3>Normalised expressions and constraints</h3> 609All expressions occurring in eplex constraints are turned into 610normalised 611linear form using lib(linearize): 612<pre> [C0*1, C1*X1, C2*X2, ...]</pre> 613where Ci are numbers and Xi are distinct variables. The first 614(constant) 615term is always present, Ci (i>=1) are nonzero. 616<br> 617Constraints are normalized by bringing all terms to one side of the 618relational symbol and then storing just the relational symbol and the 619non-zero 620side as a normalised expression: 621<pre> Sense:NormExpr</pre> 622where Sense is one of the atoms =:=, >= or =< and NormExpr is a 623normalised 624expression as above. E.g. 625<pre> (>=):[-5*1,3*X]</pre> 626could encode the source constraint 627<pre> 5 =< X*3</pre> 628There is also a quadratic normal form being used for quadratic 629objectives, 630see lib(linearize) for details. 631<br> 632 633<h3>Bounds constraints</h3> 634These can be posted either as =:=, >= or =< constraints with a 635single 636variable, or with the ::/2 constraint (the ::/2 constraint 637can be posted to an eplex instance only). 638<p>Treatment of these bounds constraint are different before and after 639the setup of a solver state. <span style="font-weight: bold;">After </span>setup, 640bounds for the variables are maintained in the external solver, and if 641the posted bounds constraint narrows the bound(s) for the variable, 642these 643are passed to the external solver (with an undo function to restore the 644original bound on backtracking). <span style="font-weight: bold;">Before</span> 645setup, the bounds are stored as single variable >=/=< 646constraints. During 647problem setup, single variable constraints are detected and converted 648to 649bounds updates for the external solver if the bounds are narrowed. 650</p> 651<p>For a problem that has been set up, bound updates can also be done 652with 653lp_var_set_bounds/4, for existing problem variables. This is not 654considered 655as posting a constraint (i.e. it would not trigger wakeup with the 656new_constraint 657trigger option). 658</p> 659<p>Bounds are treated like other constraints, and each solver state can 660have its own bounds, even if they are mutually inconsistent. In 661addtion, 662a variable is <span style="font-weight: bold;">never instantiated</span> 663by the posting of eplex bound constraints. 664<br> 665 666</p> 667<h3><a name="mergecol"></a>Unification of problem variables</h3> 668When two problem variables for the same problem instance are unified, 669their 670attributes are merged, so that the columns represented by the two 671original 672attributes is now represented by one attribute. One of the 673attribute is maintained in the merged variable, while information from 674the other attribute is merged into it. The following are done for the 675merging: 676<br> 677 678<ul> 679 <li>The column indecies are merged into one list. With the first 680index in 681list 682of the retained attribute remaining the first index in the merged list. 683This is required because the time-stamp in the attribute is used in 684updating 685the column's bound at the C-level, and this time-stamp must always be 686used 687for the same column for correct untrail behaviour.</li> 688 <li>The bounds from the merged columns are merged, and if the merged 689bounds 690is different from the original bounds, the new bounds are posted to the 691column represented by the first index. Only the bounds of this 692first 693column will be updated, and when user request the bounds of any of the 694merged columns, it is the first column's bound that will be returned. 695The 696other column bounds are no longer updated, as their original 697time-stamps 698are no longer available. Note that for the external solver, the 699bounds 700need not be updated, as long as there is an equality constraint linking 701the merged columns. The update is done so that the user can see the 702correct 703bounds, and also for the bounds trigger mode to behave correctly. As 704this 705bounds merging is done every time two variables are merged, only the 706first 707column from the two merging variables needs to be examined.</li> 708 <li>The column types are merged: if one of the merged column is of 709integer 710type and the other not, then this column(s) is also set to integer in 711the 712external solver. This is done so that when obtaining the solution 713value via typed_solution, the correct type for the solution is always 714returned.</li> 715 <li>an equality constraint between the first columns of the merged 716variables 717is added to the solver state, unless the post_equality_when_unified 718option 719is set to no. This option is available because there may already be 720other 721constraints in the solver state that constrains the two columns to be 722equal, 723and adding a redundant equality constraint may needlessly slow down the 724solving process. If an equality constraint is posted, then the 725demon 726solver is scheduled if the new_constraint trigger mode is set.</li> 727 <li>the intol_inst lists are merged</li> 728</ul> 729One general design decision that was made is the treatment of any 730existing 731solution state information when two problem variables are merged: the 732existing 733solution is no longer valid because the problem is changed. The two 734alternatives 735are 736<ol> 737 <li>Retain the old state, with the definition that the state 738information is 739the information available from the (logically) last solve of the 740problem</li> 741 <li>Clear the old state, with the definition that the state 742information is 743for the problem as it is currently defined. Any time the problem is 744altered, 745the state has to be cleared</li> 746</ol> 747We implemented policy 1, as the state will be available as long as 748possible 749(until the solver is next called), and obtaining the state information 750for probing fits into this notion of the state easily. Also, as 751unification 752of two problem variables can be done by some other solver, it would be 753difficult for the user to know exactly when the state information might 754be cleared. This retaning the solution state is now made 755consisitent 756when we modify the problem by adding constraints - the state is no 757longer 758cleared. Previously, the state is selectively cleared in some 759situation. 760<p>Accessing the solution value through a merged variable will return 761the 762solution value from the first column: after the problem is resolved, 763the 764solution values in the merged column would be the same because of the 765equality 766constraints. Accessing the reduced cost, through a merged variable will 767return 0.0. It is not safe to simply return one of the reduced cost, 768because 769the user may be summing the reduced cost of all the variables. 770Returning 771a 0.0 is the safe and simple way of dealing with this. 772<br> 773 774</p> 775<h3><a name="Eplex_instances"></a><a name="eplex_instances"></a>Eplex 776instances</h3> 777For ease of programming multiple eplex problems, the abstraction of <i>eplex 778instances</i> is introduced. Conceptually, an eplex instance is an 779instance 780of the eplex solver for one eplex problem. Each eplex 781instance 782is a module, and from a user's point of view, it works like any other 783solver 784module: predicates are defined in the module which allows the user to 785post 786linear arithmetic and intergrality constraints, and to set up and 787invoke 788an external solver to solve the problem. There are three components: 789<ol> 790 <li>storage for constraints</li> 791 <li>predicates to set up and trigger solver state</li> 792 <li>associated external solver state (if one has been setup)</li> 793</ol> 794<h4> 795Storage for constraints</h4> 796This is implemented using lib(constraint_pools), with each eplex 797instance 798having an associated constraint pool. With standalone eplex, 799constraints 800are only stored in the pools before an external solver solver is set up 801for the instance. After setup, posted constraints are immediately added 802to the external solver. To make this more efficient, the <span 803 style="font-weight: bold;">vars</span> 804field of the problem handle was changed from a structure to a list. 805<br> 806If the added constraints contain new variables, these needed to be 807added to the problem, and previously a new vars structure has to be 808created 809and the old variables copied to it. 810<p>When an eplex instance is declared using eplex_instance/1, an eplex 811instance is either created (if it does not already exist) or checked to 812see if it is empty (no posted constraints in the constraint pool, no 813associated 814solver). An eplex instance is created by creating the constraint pool 815for 816it. 817</p> 818<p>The constraints are divided into two types, defined in the structure 819constraint_type in eplex_s.ecl: 820</p> 821<p>:- local struct(constraint_type(integers,linear)). 822</p> 823<p>integers are the intergrality constraints (integers/1), and linear 824are 825the linear arithmetic constraints (=:=/2, >=/2, =</2). 826</p> 827<p><a name="lincon-action"></a>When a linear constraint is posted, the 828following happens: 829</p> 830<ol> 831 <li>the constraint gets normalised</li> 832 <li>if ground, solve it now, i.e. check if satisfied</li> 833 <li>before solver setup:</li> 834 <ul> 835 <li>add the normalised form to the linear constraint type of the 836constraint 837pool.</li> 838 </ul> 839 <li>after solver setup:</li> 840</ol> 841<ul> 842 <ul> 843 <li>if constraint has only one variable, turn it into a bound 844update 845(shared 846code with ::/2)</li> 847 <li>otherwise, add the constraint to the solver state with <a 848 href="lp_add_normalised">lp_add_normalised</a>. 849If the constraint involves new problem variables, these are added 850to the <span style="font-weight: bold;">vars</span> list.</li> 851 </ul> 852</ul> 853<a name="intcon-action"></a>integers/1 is handled by 854<ul> 855 <li>before solver setup:</li> 856</ul> 857<ol> 858 <ol> 859 <li>extract the variables into a list, eliminating ground integers</li> 860 <li>add the remaining variables to the integers constraint type of 861the 862constraint 863pool. For efficiency, when the integers list is traversed to eliminate 864ground integers, a unbounded tail is created to allow the existing 865integers 866to be added to this tail</li> 867 </ol> 868</ol> 869<ul> 870 <li>after solver setup:</li> 871 <ol> 872 <li>extract the variables into a list, eliminating ground integers</li> 873 <li>for the remaining variables, if the variable is an existing 874problem 875variable, 876change its column type to integer in the external solver state, if it 877is 878not already integer or binary (with trailed undo function). If it is a 879new problem variable, create a column for it in the external solver 880(and 881add to <span style="font-weight: bold;">vars</span> list)</li> 882 <li>Note that the problem type might change from lp to mip. If the 883problem 884is a qp problem, this will raise an error currently, as we cannot yet 885change 886a qp to a qp mip problem.</li> 887 </ol> 888</ul> 889<a name="bdcon-action"></a>::/2 is handled by: 890<ol> 891 <li>fail if the the lower bound is greater than the upper bound</li> 892 <li>extract the variables into a list</li> 893 <li>if the solver state is not yet setup, post the upper and lower 894bounds 895as 896constreaints, for each variable on the LHS: V <= Upper and V >= 897Lower, 898Otherwise:</li> 899 <li>Determine which of the variables on the LHS are new (i.e. not 900already 901in 902the solver state). New columns for these.</li> 903 <li>For each variable in the LHS: get the existing bounds for the 904variable 905from the solver state, check if new bound(s) are narrower. If so, 906impose 907the new bound(s).</li> 908 <li>if any new bounds were imposed, trigger the bd_trigger suspension 909list 910of the problem</li> 911</ol> 912Thus before solver setup, the constraints are not actually maintained 913as 914suspensions, but logically they are still part of the resolvent. Any 915constraints 916that remain in any of the eplex instances' constraint pools are thus 917printed 918out at the end of an execution. This is done by calling 919set_lp_pending/0 920whenever a constraint is added to an eplex instance. set_lp_pending/0 921will 922create an lp_pending/0 suspension if one does not already exist, so the 923presence of this suspended goal indicates that there are possibly some 924constraints posted to some eplex instance. A portray macro for 925lp_pending/0 926is defined to print out the outstanding constraints in all the eplex 927instances, 928so that when the delay goals are printed at the end of an execution, 929the 930eplex constraints would be printed instead of lp_pending/0. Note that 931this 932only applies to constraints posted before solver setup, because after 933setup, 934the constraints are added to the external solver immediately, and will 935not be printed, even if the external solver was not invoked to solve 936the 937problem. 938<p>The suspended lp_pending goal is stored in the global reference <b>lp_info</b> 939in the module eplex_. lp_info is a structure with two fields: 940</p> 941<p>:- local struct(lp_info(newid, % int: next 942handler 943id 944<br> 945 946pending % suspension: lp_pending's suspension 947<br> 948 )). 949</p> 950<p>newid is the next solver id. 951</p> 952<h4>Predicates for the eplex instance</h4> 953Predicates defined in the eplex instances simply call their 954counter-parts 955in the module eplex_s with the eplex instance name as an argument. All 956the real work is done by the predicates in the eplex_s module. This is 957specified in the create_constraint_pool/3 call 958<br> 959when the constraint pool is created. 960<p>Except for the constraint predicates, all other predicate names 961defined 962for an eplex instance start with eplex_s. The predicates (in the 963eplex instance) are: 964<br> 965 966</p> 967<blockquote><b>constraints</b>: 968integers/1, reals/1, =:=/2, >=/2, =</2, ::/2 <br> 969 <b>solver setup:</b> 970eplex_solver_setup/1, eplex_solver_setup/4 <br> 971 <b>solver invocation:</b> eplex_solve/1, 972eplex_probe/2 <br> 973 <b>solver state:</b> 974eplex_get/2, eplex_var_get/3 <br> 975 <b>destroy solver:</b> 976eplex_cleanup/0 <br> 977 <span style="font-weight: bold;">read/write problem: </span> 978eplex_read/2, 979eplex_write/2</blockquote> 980In turn, the eplex_* predicates in eplex_s.ecl calls the low-level 981predicate 982that uses solver state handles. The solver handle is for the solver 983state 984that is associated with the particular eplex instance. 985<h4><b>Associating external solver state</b></h4> 986A new external solver state can be associated with an eplex instance by 987the solver setup predicates of the eplex instance. The solver state is 988first created and then associated with the eplex instance. 989<p>Associating with an eplex instance is done using the pool item 990facility 991of lib(constraint_pools). The ECLiPSe handle for a solver state is 992stored 993in the eplex instance's pool item if the eplex instance has an 994associated 995solver, otherwise 0 is stored as the pool item. 996<br> 997 998</p> 999<h3>lp_setup</h3> 1000This is really the core of the library. It takes as input 1001<ol> 1002 <li>a list of already normalised constraints (equalities and 1003inequalities)</li> 1004 <li>an objective expression (linear or quadratic)</li> 1005 <li>a list of integer variables (within the option list)</li> 1006 <li>a list of solver options</li> 1007</ol> 1008This data is used to set up a linear, quadratic or mixed integer 1009problem 1010with the external solver, and a handle to it is returned. 1011<ul> 1012 <li> A quadratic mix integer problem (qmip) is set up if the 1013objective 1014is not linear and if the list of integers is not empty</li> 1015 <li>A quadratic problem (qp) is set up if the objective is not linear 1016and 1017the 1018list of integers is empty</li> 1019 <li>A mixed integer problem (mip) is set up if the list of integers 1020is not 1021empty. Note that the integrality-information in the range-attribute 1022(range:integers/1) 1023is completely ignored for this purpose. This allows lp_setup to set up 1024a linear relaxation easily.</li> 1025 <li>A linear problem (lp) is set up otherwise</li> 1026</ul> 1027A problem type can change into another problem type after problem 1028setup: 1029<ul> 1030 <li>a non-integer problem (lp, qp) can change into a mix integer 1031problem 1032(mip, 1033qmip) with the posting of integer constraints. On backtracking, the 1034original 1035problem type is restored.</li> 1036 <li>a mixed integer problem (mip, qmip) can change to a non-integer 1037problem 1038(lp, qp) if the integer constraints are relaxed during an lp_probe. The 1039original problem type is restored after the probe.</li> 1040 <li>a non-quadratic problem (lp, mip) can change into a quadratic 1041problem 1042(qp, 1043qmip) and vise versa with lp_probe by the objective. The original 1044problem 1045type is restored after the probe.</li> 1046</ul> 1047Pseudocode: 1048<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 list 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> classify and convert constraints, depending on number of variables:<br> pass problem data, including objective coefficients, rhs, matrix<br> coefficients (in column-wise format) to the C-level handle</pre> 1049<pre> 0 : check for satisfibility immediately<br> 1 : convert into bound check/update for external solver<br> >1: convert to column-wise lists of row:coefficient pairs<br> <br> call the C-level problem setup function cplex_loadprob()</pre> 1050As from 5.7, an external solver state is always setup, even for an 1051empty 1052problem. 1053<p>Each solver state is assigned an unique integer solver id. The next 1054id to assign is maintained in a global reference. 1055</p> 1056<p>Note that there may be restrictions on the problem types available 1057depending 1058on the solver: 1059</p> 1060<ul> 1061 <li>the problem type may be unavailable for the particular solver 1062(for 1063example 1064qmip for older CPLEXes). This is checked for in the C level code and an 1065error raised. An error is also raised for qmip for Xpress older than 1066version 106715, as qmip is `not recommended' for these older versions, even though 1068the library calls are available (they certainly seem quite buggy)</li> 1069 <li>the problem type may be unlicensed in a particular solver. In 1070this 1071case, 1072we rely on the external solver to raise the error.</li> 1073</ul> 1074<h3> 1075lp_solve</h3> 1076Takes a problem handle and invokes the actual optimizer. Because it can 1077be called repeatedly on the same problem handle, it takes care of first 1078transferring possibly updated variable bounds to the solver,,and 1079optionally 1080loading a basis that might have been saved from a previous solver run. 1081Pseudocode: 1082<pre>lp_solve:<br> synchronise bounds if requested to do so (option sync_bounds)<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> 1083About handling the <b>basis</b>: storing the basis at the logical 1084Eclipse-level 1085is optional. If it is done, then the solver can restart from the basis 1086of the logical ancestor in the search tree. If it is not done, it will 1087just use the basis from the chronologically last solver invocation. The 1088latter is less predicatable, but has less overhead. 1089<br> 1090Cplex and Xpress can return lots of different <b>result codes</b>. 1091We classify them into the following groups: 1092<center><br> 1093<table nosave="" border="1" width="90%"> 1094 <caption> 1095 <center> 1096 <p></p> 1097 </center> 1098 </caption><tbody> 1099 </tbody><tbody> 1100 </tbody><tbody> 1101 </tbody><tbody> 1102 </tbody><tbody> 1103 </tbody> <tbody> 1104 <tr nosave="" bgcolor="#cccccc"> 1105 <td nosave="">Result</td> 1106 <td>description</td> 1107 <td>action</td> 1108 <td>default handler</td> 1109 </tr> 1110 <tr nosave=""> 1111 <td>DESCR_SOLVED_SOL</td> 1112 <td>an optimal solution was found</td> 1113 <td>success</td> 1114 <td nosave="">success</td> 1115 </tr> 1116 <tr> 1117 <td>DESCR_SOLVED_NOSOL</td> 1118 <td>no solution was found, infeasible</td> 1119 <td>fail</td> 1120 <td>fail</td> 1121 </tr> 1122 <tr> 1123 <td>DESCR_ABORTED_SOL </td> 1124 <td>a possibly suboptimal solution was found </td> 1125 <td>event(eplex_suboptimal)</td> 1126 <td>success</td> 1127 </tr> 1128 <tr> 1129 <td>DESCR_ABORTED_NOSOL </td> 1130 <td>no solution was found, but there may be one </td> 1131 <td>event(eplex_abort)</td> 1132 <td>abort</td> 1133 </tr> 1134 <tr> 1135 <td>DESCR_UNBOUNDED_NOSOL</td> 1136 <td>problem unbounded, no solution values</td> 1137 <td>event(eplex_unbounded)</td> 1138 <td>success</td> 1139 </tr> 1140 <tr> 1141 <td>DESCR_UNKNOWN_NOSOL</td> 1142 <td>unknown whether infeasible or unbounded</td> 1143 <td>event(eplex_unknown)</td> 1144 <td>fail</td> 1145 </tr> 1146 </tbody> 1147</table> 1148</center> 1149<p>The <i>infeasible or unbounded</i> result can arise from the use of 1150presolving or the dual simplex method (because infeasibility of the 1151dual 1152indicates infeasibility or unboundedness of the primal). The events 1153have 1154been introduced to enable the library user to tailor the behaviour of 1155the 1156solver for the doubtful results. [Note CPlex 8 can properly handle 1157infeasible/unbounded 1158for primal/dual problems] 1159</p> 1160<h3>optimize</h3> 1161Optimize (the black-box solver) is a simple sequence of 1162<ol> 1163 <li>collecting the pending constraints (equalities, inequalities and 1164eplex:integers/1)</li> 1165 <li>setting up a solver</li> 1166 <li>run the solver</li> 1167 <li>unifying the resulting cost</li> 1168 <li>retrieving the solutions and unifying them with the variables</li> 1169 <li>cleaning up the solver</li> 1170</ol> 1171<h3> 1172lp_demon</h3> 1173For the demon solver, the setup and initial solving is like for the 1174black-box 1175solver. The differerences are that a demon with appropriate waking 1176conditions 1177is set up as well, the Cost variable is only bounded by the solution 1178(rather 1179than unified), and the problem variables are not touched after solving: 1180<ol> 1181 <li>setting up a solver</li> 1182 <li>create the lp_demon suspension</li> 1183 <li>insert the suspension into the suspend field of the handle</li> 1184 <li>run the solver once if initial_solve option is yes</li> 1185 <li>calling the post-goal (see user documentation)</li> 1186 <li>bounding the Cost variable (using the generic set_var_bounds/3)</li> 1187</ol> 1188Note that if the Cost variable does not have some bounds attribute, it 1189would not be bounded by step 6. The actual solution value can still be 1190extracted in this case. 1191<br> 1192When the lp_demon is woken subsequently, it performs: 1193<ol> 1194 <li>calling the pre-goal</li> 1195 <li>run the solver again</li> 1196 <li>calling the post-goal</li> 1197 <li>bounding the Cost variable</li> 1198</ol> 1199Triggering the demon: 1200<center><br> 1201<table nosave="" border="1" width="80%"> 1202 <caption> 1203 <center> 1204 <p></p> 1205 </center> 1206 </caption><tbody> 1207 </tbody><tbody> 1208 </tbody><tbody> 1209 </tbody><tbody> 1210 </tbody><tbody> 1211 </tbody> <tbody> 1212 <tr nosave="" bgcolor="#cccccc"> 1213 <td nosave="">Trigger condition</td> 1214 <td>Implementation</td> 1215 </tr> 1216 <tr> 1217 <td>inst</td> 1218 <td>insert in all variable's (inst of suspend) lists</td> 1219 </tr> 1220 <tr> 1221 <td>bounds</td> 1222 <td>bd_trigger field of ECLiPSe handle for probelm is set to 1223bounds. 1224When a problem variable's bound is updated, eplex checks if bd_trigger 1225is set to bounds, and if so, triggers the demon explicitly if the 1226bounds 1227changed. The demon is also triggered during when columns are merged, 1228and 1229the bounds are changed by the merging (the column merge code 1230checks 1231to see if the demon has already been triggered by new_constraints, so 1232that 1233the demon is triggered only once)</td> 1234 </tr> 1235 <tr> 1236 <td>deviating_inst</td> 1237 <td>insert in all variable's (intol_inst of eplex) lists</td> 1238 </tr> 1239 <tr> 1240 <td>deviating_bounds</td> 1241 <td>bd_trigger field of ECLiPSe handle for problem is set to 1242deviating_bounds. 1243When a problem variable's bound is updated, eplex checks if 1244bd_trigger 1245is set to deviating_bounds, and if so, triggers the demon 1246explicitly 1247if the variable's solution value fall outside the new bounds by a 1248tolerance. 1249Merging of columns does NOT trigger the demon, as the solution values 1250in 1251the columns is no longer valid for the changed problem.</td> 1252 </tr> 1253 <tr> 1254 <td valign="top">Attribute:Index</td> 1255 <td valign="top">insert in all variables' suspension list found 1256in attribute 1257Attribute in the index'th position </td> 1258 </tr> 1259 <tr> 1260 <td>new_constraint</td> 1261 <td>the nc_trigger field of the solver state's handle is set to 1262yes (it 1263defaults to no). When constraints are added to the solver state (see 1264lp_add 1265below), the nc_trigger filed is checked, and if it is yes, then the 1266demon 1267is triggered (by scheduling the suspension for the demon in the 1268suspension 1269field for the handle). The demon is also triggered when an equality 1270constraint 1271is posted when columns are merged </td> 1272 </tr> 1273 <tr> 1274 <td>trigger(atom)</td> 1275 <td>attach to a global trigger</td> 1276 </tr> 1277 <tr> 1278 <td>suspension(S)</td> 1279 <td> returns the demon suspension in S. The user can 1280then write 1281their own code for triggering the demon. For example, this allows the 1282user 1283to select specific variables to suspend the demon on.</td> 1284 </tr> 1285 </tbody> 1286</table> 1287</center> 1288<h3> 1289lp_add</h3> 1290lp_add add linear or integer constraints variables to a previously set 1291up problem handle. The handles on all levels must be adjusted 1292accordingly. 1293In general, the problem type can change from lp to mip (if interger 1294constraints 1295are added to an lp problem). Both linear and integers constraints can 1296be 1297added. 1298<p>lp_add can be called in several ways, either explicitly (e.g. via 1299lp_add_constraints), 1300or implicitly (when a demon solver is invoked), with various steps, 1301which 1302are carried out by three predicates: 1303</p> 1304<ol> 1305 <li> <span style="font-weight: bold;">renormalise_and_check_simple</span>: 1306Renormalise 1307any new linear constraints</li> 1308 <li> <span style="font-weight: bold;">lp_add_normalised</span>: Add 1309the 1310new 1311(normalised) constraints/variables to the problem</li> 1312 <li> <span style="font-weight: bold;">var_triggers</span>: Add the 1313new 1314variables 1315to the triggers</li> 1316</ol> 1317<h4> 1318<span style="font-weight: bold;">renormalise_and_check_simple</span></h4> 1319Renormalised and any ground linear constraints (all variables in 1320constraint 1321instantiated) are checked for satisfaction and filtered out (not passed 1322to external solver). Note that unlike when linear constraints are 1323posted, 1324single variable constraints are not turned into bound updates.<span 1325 style="font-weight: bold;"> 1326<br> 1327</span> 1328<h3><span style="font-weight: bold;"><a name="lp_add_normalised"></a>lp_add_normalised</span></h3> 1329Adds the normalised constraints to the solver. It also returns a lists 1330that give the row indicies in the solver 1331<br> 1332matrix for the added constraints. No checks are performed on 1333the constraints: they are assumed to have 1334<br> 1335been checked previously (e.g. by renormalise_and_check_simple). 1336<p>Variables occurs in both the new linear and integers constraints 1337being 1338added. For the integers variables, they can be classified as: 1339</p> 1340<ul> 1341 <li>old variables: variables that are already in the solver 1342state</li> 1343 <ul> 1344 <li>old integer variables: old variables which occur in the 1345new 1346integers 1347constraints. They may or may not already be constrained to be integer</li> 1348 <li>other old variables: old variables which occurs in the 1349new linear 1350constraints only</li> 1351 </ul> 1352 <li>new variables: variables that are not yet in the solver state</li> 1353 <ul> 1354 <li>new integer variables: new variables which occur in the new 1355integers 1356constraints. 1357(They may also occur in the new linear constraints)</li> 1358 <li>new non-integer variables: new variables which occur in the new 1359linear 1360constraints only</li> 1361 </ul> 1362</ul> 1363Note that unlike the bounds keeper eplex, <span 1364 style="font-style: italic;">there 1365are no</span><span style="font-style: italic;"> non-problem variables</span>. 1366This is because after solver setup, all constraints (linear, integer, 1367bounds) 1368are immediately added to the solver state (by lp_add implicitly) when 1369they 1370are posted. 1371<p>The steps performed by lp_add are: 1372</p> 1373<ol> 1374 <li>If problem not yet initialised (no variables/constraints set up 1375yet), 1376initialise 1377it</li> 1378 <li>Classify the variables that occur in the new constraints (both 1379linear 1380and 1381integers) into old integers, other old variables, new integers, and the 1382new non-integer variables. These need to be treated differently:</li> 1383 <ul> 1384 <li>old integers: the type of columns representing these variables 1385in the 1386external 1387solver matrix need to be changed if it was not already an integer 1388(or boolean). The type changes are undone on backtracking at the C 1389level.</li> 1390 <li>new integers: new column needs to be added to the external 1391solver 1392matrix, 1393as type integer</li> 1394 <li>new non-integer variables: these are new variables that are not 1395constrained 1396to be integers. A new column needs to be added to the external solver 1397matrix, 1398as type continueous.</li> 1399 </ul> 1400 <li>Pass the new column-wise problem data (for existing rows) to the 1401C 1402level 1403buffer arrays (set_var_index + setup_new_cols + code to pass 1404integer/bounds 1405information)</li> 1406 <li>Pass the data on the new rows to the C level buffer arrays 1407(setup_new_rows)</li> 1408 <li>Call the C level predicate to flush the new data in the buffer 1409arrays 1410to 1411the external solver (cplex_flush_new_rowcols)</li> 1412 <li>If var_names option is set, pass any variable names for the new 1413varaibles 1414to the solver state.</li> 1415 <br> 1416 1417</ol> 1418<h4> 1419var_triggers</h4> 1420If there are variable trigger conditions, add the variable trigger 1421condition(s) 1422to the new variables. This same code is used here as during the demon 1423solver's 1424setup. 1425<h3>lp_add_constraints/3</h3> 1426This basically calls lp_add after normalising the constraints, and then 1427filter out simple one variable linear constraints as done when linear 1428constraints 1429are posted to an eplex instance. 1430<br> 1431After calling lp_add, the solver is invoked if the nc_trigger field 1432of the handle is set to yes 1433<br> 1434<i>(only in 5.8 development branch: and new constraints</i> 1435<br> 1436<i>were posted that might possibly change the problem (i.e. new 1437arithematic 1438constraints, integer constraints on existing variables (`old 1439integers')).</i> 1440<h3>lp_add_constraints/4</h3> 1441This is the user accessible interface to implementing column 1442generation. 1443Constraints are normalised (and not simplified), and checked to 1444make 1445sure that none are ground: an error is raised otherwise. It then 1446essentially call lp_add, but unlike lp_add_constraints/3, the row 1447indicies 1448are returned. Note also that adding constraints using this 1449predicate 1450will not trigger the external solver. 1451<h3>lp_add_columns/3</h3> 1452This is used by the column generation library (and in addition is 1453accessable 1454by the user) to add possibly non-empty columns to the solver's matrix. 1455The column information is specified by a list of pairs of Var:ColInfo, 1456where Var is the variable representing the new column, and ColInfo is a 1457list of Idx:Value pair, where Idx is either obj for the objective, or a 1458integer specifying the row number, and Value is the corresponding 1459coefficient. 1460All unspecified row/objective coefficients are taken to be zero. 1461<p>The steps performed are: 1462</p> 1463<div style="margin-left: 40px;"> 1464<ul> 1465 <li>extract the indivdual column data into the format required 1466(separate 1467lists 1468for the objectives, row coefficients, etc., number of non-zero 1469coefficents, 1470etc.). Index each new column with a new column index by calling 1471set_var_index: 1472this creates a new eplex attribute for the variable representing the 1473column 1474and add the index to it.</li> 1475 <li>pass the extracted data to the C level buffer arrays with 1476setup_new_cols</li> 1477 <li>flush the data from the buffer arrays to the solver state with 1478cplex_flush_new_rowcols</li> 1479 <li value="4">If var_names option is set, pass any variable names for 1480the new 1481varaibles 1482to the solver state.</li> 1483 <li>extend the basis by retaining the last basis and giving 0 to the 1484new 1485columns</li> 1486</ul> 1487</div> 1488In 5.7, the amount of code sharing between the various predicates 1489that add data to the external solver was increased: set_var_index is 1490used 1491to setup a new variable's column index in its attribute. setup_new_cols 1492is used to pass the new problem data in column-wise format (for 1493existing 1494rows) to the C level buffer arrays (expanding the buffer arrays if 1495necessary 1496in C), and cplex_flush_new_rowcols is used to pass C level data to the 1497solver. set_var_index was separated out from setup_new_cols to minimize 1498the number of traversal of the list of new variables. 1499<p>The initial setup of a matrix in lp_setup does not use 1500setup_new_cols, 1501because the processing of the constraints are done differently. 1502However, 1503it does use the same C calls to pass the column-wise data to the buffer 1504arrays: cplex_set_obj_coeff(), cplex_set_matbeg(), 1505cplex_set_obj_coeff(). 1506</p> 1507<h3>lp_eq, lp_ge, lp_le</h3> 1508These are called when the linear constraints (=:=, >=, =< and 1509their 1510$ equivalents, respectively) are posted to an eplex instance. The 1511actiions performed are described <a href="#lincon-action">here</a>. 1512<h3>lp_impose_interval</h3> 1513This is called when bounds constraints (::, $::) are posted to an eplex 1514instance. Type checking (integer/real/don't care) may be done. 1515Variables 1516are extracted from the LHS (wuth subscript being a special case), and 1517the 1518interval from the RHS. The actions performed are described <a 1519 href="#bdcon-action">here</a>. 1520<h3>integers</h3> 1521This is called when integers constraints are posted to an eplex 1522instance. 1523The argument is a list of variables or integers. Type check is 1524performed, 1525and for the variables, the action performed are described <a 1526 href="#intcon-action">here</a>. 1527<br> 1528<i>(5.8 development branch: the solver is invoked if the nc_trigger 1529field is set to yes, and the integers constraint was applied to 1530existing 1531variables ('old integers')).</i> 1532<h3>lp_read, lp_write</h3> 1533lp_write is a simple wrapper around the C level <a 1534 href="#cplex_lpwrite">cplex_lpwrite</a> call. <br> 1535lp_read does:<br> 1536<ul> 1537 <li>creates a new problem handle</li> 1538 <li>calls <a href="#cplex_lpread">cplex_lpread</a> to read in the C 1539level representation of the problem</li> 1540 <li>extract the problem variables and types for the problem handle</li> 1541 <li>retrieve the objective coeffs for the problem handle. Currently 1542only the linear objective is retrieved, as Xpress did not 1543properly support the retrieval of the quadratic objective coeffs. [this 1544has changed with Xpress 16, and retreival of the quadratic objective 1545should be added]<br> 1546 </li> 1547</ul> 1548the quadratic objective in the problem handle is used to set and reset 1549the quadratic objective during an objective probe only, so the 1550quadratic objective will not be cleared without the quadratic objective 1551coefficients.<br> 1552<h3>lp_probe</h3> 1553lp_probe teomprarily modifies a problem and solves it, reutrning the 1554problem 1555to the original, unmodified, state upon exiting. The code is 1556strcutred 1557as: 1558<br> 1559 1560<dd><tt>lp_probe:</tt></dd> 1561<dd> <tt> extract the probes from the 1562specifications</tt></dd> 1563<dd> <tt> modify Handle's problem as specified 1564by 1565the 1566probes</tt></dd> 1567<dd> <tt> invoke lp_solve on Handle</tt></dd> 1568<dd> <tt> restore Handle's problem back to the 1569original 1570one</tt></dd> 1571<br> 1572<p>The problem can be modified by multiple probes, but not all 1573combinations 1574are allowed. This is checked for when the probes are extracted: if an 1575unknown 1576probe or an illegal combination of probes are found, an error message 1577is 1578printed and lp_probe aborts. 1579</p> 1580<p>The problem is modified by applying the probe changes to the problem 1581individually. After the problem is solved, the modified problem 1582is 1583restored by reversing the modifications done by the probes in the 1584reverse 1585order. Both the modification and solving of the problem catches 1586failure 1587and exceptions (via <font face="Courier New,Courier">block/3</font>) 1588so 1589that the probes that have been applied so far can be undone before the 1590failure or exception is allowed to continue. 1591</p> 1592<p>For each probe, code must be written for: 1593</p> 1594<ul> 1595 <li>extract_one_probe(+ProbeSpec, +ProbeInfo, +ExtractedIn, 1596-ExtractedOut): 1597ProbSpec is the specification for one probe, and ProbeInfo is the <font 1598 face="Courier New,Courier">probes</font> 1599data structure which is used to unify with the extracted probe 1600information. 1601This unification should fail if there has already been an incompatible 1602probe specified. ExtractedIn/Out is a list of the extracted probes. 1603ExtractedOut 1604should add to ExtractedIn the probes extracted from ProbeSpec, and the 1605priority the probe should run at, in the form 1606<probe>-<prio>. At 1607the end of extracting the probes, Extracted will be a list of the 1608extracted 1609probes, and this list will be sorted according to their priorities, so 1610that the setting of the probes can then be done according to the sorted 1611Extracted list.</li> 1612 <li>problem modification handler , wrapped inside a <font 1613 face="Courier New,Courier">block_with_probes </font>call 1614in<font face="Courier New,Courier"> set_probes/4. </font>This modifies 1615the problem according to the appropriate entry in the <tt>probes</tt> 1616strcture 1617(and will probably involve C calls to perform the modification). The 1618handler 1619should add an entry to the head of the <tt>SetProbes</tt> list that 1620contains 1621the information needed for performing the correct problem restoration 1622handler 1623to undo the modifications. Note that any changes made by the current 1624handler 1625is not automatically undone. To avoid this problem, the handlers do not 1626make incremental changes to the external solver state. Instead, each 1627handler 1628phould makeall the changes it is required in one go to the external 1629solver.</li> 1630 <li>problem restoration handler, which undoes the modifications for 1631the 1632probe. 1633This should be added as a <tt>unset_one_probe(+Handle, +SetProbe) </tt>clause. 1634 <tt>SetProbe</tt> 1635is the entry in the <tt>SetProbes</tt> list added by the problem 1636modification 1637handler for the probe, which is used to select (and supply the needed 1638information 1639for) the restoration handler to call.</li> 1640</ul> 1641The priority is needed in setting the probe because some probes need to 1642be set/unset before others. For example, CPLEX does not allowed a fixed 1643problem to be further modified, so this probe must be set last (and 1644unset 1645first). Currently only two priorities are used: 1 and 3. 1646<p>For the `ints' probes (fixed and relaxed, which modifies a MIP 1647problem 1648and solves the modified problem as an LP problem) has a complication: 1649during 1650the problem modification, the problem type is set to the appropriate 1651type 1652(fixed or related) by a call to <tt>cplex_set_problem_type.</tt> This 1653change 1654the problem type at the C level. For CPLEX, which maintains its 1655own 1656problem type, the CPLEX problem type is not changed, and this is 1657specified 1658by a 0 for the last argument in c<tt>plex_set_problem_type</tt>. The 1659reason 1660for this is that for these <tt>ints</tt> problem type (which CPLEX 1661partially 1662supports directly), CPLEX cannot change to these problem types 1663without 1664having first solved the corresponding MIP problem. As we do not 1665restrict 1666the user to having first solved the MIP problem, there may not be 1667a solved MIP problem to permit the problem type change. The CPLEX 1668problem 1669type is only changed when the problem is solved in the C procedure <tt>p_cpx_optimise</tt>. 1670When undoing the change in the problem restoration handler, c<tt>plex_set_problem_type</tt>is 1671called with 1 for the last argument so that the CPLEX level problem 1672type 1673is also reset (the CPLEX problem type cannot be reset earlier as 1674changing 1675the problem type prevents CPLEX from accessing the information 1676associated 1677with the solution). 1678</p> 1679<p>When column-related information is modified by the probe, the change 1680must take into account that multiple columns may be represented by one 1681variable, and that these merged columns must be considered as one. For 1682example, the bounds probe, which changes the bounds on columns, 1683must 1684apply the same bounds to all the merged columns. The perturb_obj probe 1685works correctly because it changes the objective coefficients (rather 1686than 1687speciffying the new coefficients) and is cumulative (thus changing more 1688than one merged variable will behave correctly); and the objective 1689probe 1690behaves correctly because eplex keeps a representation of the objective 1691using the column numbers directly (rather than variables). 1692</p> 1693<p>Note that unlike the other modifications done to the problem, 1694modifications 1695done by the probes does not need to be backtrackable, because 1696modifications 1697done when setting the probe are undone when unsetting. At the C level, 1698it means that an untrail function is not needed. 1699</p> 1700<h3>reduced_cost_pruning</h3> 1701reduced _cost_pruning implements an optional functionality that the 1702programmer 1703can invoke on a solved handle (see for example Michela Manela's work). 1704If we are solving the lp-relaxation of a more complex global problem, 1705and 1706we have a maximum (minimum) of the relaxation, and a lower (upper) 1707bound 1708on the global problem, then we can use the reduced cost information of 1709the relaxed solution to prune variable values that cannot possibly 1710yield 1711a better solution to the global problem. 1712<center><img src="redcost.png" alt="reduced cost pruning" align="bottom" 1713 height="277" width="424"></center> 1714For those variables whose solution value is at one of their bounds, the 1715reduced cost gives a gradient which says how much the objective 1716deteriorates 1717(at least) when the value moves away from the bound. Values that are so 1718far away that the relaxed cost gets worse than the known bound on the 1719global 1720cost, are useless and so the opposite bound may be pruned to that 1721value. 1722<br> 1723 1724<h2><a name="cutpool"></a>Cutpool constraints</h2> 1725Cutpools implement the functionality of global constraints/cutpools, 1726needed for techniques such as cut generation. It provides the following 1727functionality:<br> 1728<br> 1729<ul> 1730 <li>store constraints non-logically (i.e. they are not removed on 1731backtracking), which can then be taken into account in all subsequent 1732invocations of the solver.</li> 1733 <li>flexibility in how the constraints are taken into account when 1734the solver is invoked. The constraints can be</li> 1735 <ul> 1736 <li>added to the problem matrix initially, just before the external 1737solver is invoked (specified by add_initially status)</li> 1738 <li>added to the problem matrix only if the constraint is violated 1739by a solution returned by the solver. The solver is then re-invoked 1740until no constraints are violated. <br> 1741 </li> 1742 <li>not considered for adding to the problem at all</li> 1743 </ul> 1744 <li>organise the constraints into named groups<br> 1745 </li> 1746</ul> 1747<p>The cutpool constraints are passed to the C level for non-logical 1748storage. Conceptually they can be considered to be in a cutpool matrix 1749with the same columns as the normal problem matrix, and the rows 1750representing the cutpool constraints. The `raw' index for a cutpool 1751constraint is the row number for this cutpool matrix. At the ECLiPSe 1752level, the raw index is wrapped by a structure to distinguish it from 1753the normal constraint index: <br> 1754 g(2,RawIdx). <br> 17552 indicates the constraint type -- cutpool constraints. This allows 1756other constraints type to be added in the future. (it was also used to 1757distinguish conditional and unconditional cutpool constraints in the 1758first version of the cutpool constraints, but these have been combined 1759into the single cutpool constraint type in the current implementation). 1760The predicate <span style="font-family: monospace;">rawidx_cstridx/3 </span>is 1761used for conversion (and indentification) between the `raw' and 1762full index of a constraint.<br> 1763<br> 1764To setup/access the constraints, the same routines as for the normal 1765constraints are generally used, with the constraint type and raw index 1766used to identify the constraint. For these routines, 0 is the 1767constraint 1768type for normal constraints. 1769</p> 1770Each time the problem is solved, the cutpool constraints are appended 1771selectively to the end of the problem matrix. Only active 1772constraints which are either labelled as add_initially or are violated 1773by an intermediate solve are added to the matrix. The problem 1774matrix's constraints (rows) can be classified as<br> 1775<br> 1776<ol> 1777 <li>'Normal' problem constraints<br> 1778 </li> 1779 <li>cutpool constraints - this consists of all the added cutpool 1780constraints <br> 1781 </li> 1782</ol> 1783The number of `normal' constraints is stored in the <span 1784 style="font-family: monospace;">mr </span>field of the Eclipse 1785handle. F<br> 1786<pre> <br><br> Normal cutpool<br><br> |------------------|--------------|<br><br> <------- mr ------><br></pre> 1787<p><a name="cutpoolmap"></a>The row-wise data arrays for the solved 1788problem 1789(dual, slack values) are arranged as showned above, i.e. those rows 1790beyond index <span style="font-family: monospace;">mr</span> are the 1791cutpool constraints. In order to map the cutpool constraints from 1792the cutpool into the actual row for the problem matrix.<br> 1793</p> 1794<p>To map the raw 1795index of the constraint into the row index in the solved problem matrix 1796shown above, a `Map' is returned as part of the result state by 1797cplex_optimise. This is stored in the <span 1798 style="font-family: monospace;">cp_cond_map field </span>of the 1799Eclipse handle. This Map shows the status for each cutpool constraint 1800in the last solve. The cutpool constraints are indexed by their `raw' 1801cutpool index, and their value in the Map indicates:<br> 1802</p> 1803<ul> 1804 <li>value >= 0 : the constraint was added to the matrix. Value is 1805the row number displacement from the end of the normal constraints, 1806i.e. the row index in the result arrays is<span 1807 style="font-family: monospace;"> mr + Map[rawidex] <br> 1808 </span></li> 1809 <li><span style="font-family: monospace;"></span>value < 0: the 1810constraint was not added to the matrix. The actual value indicates</li> 1811 <ul> 1812 <li><span style="font-style: italic;">satisfied</span> 1813the constraint was satisfied but not binding, so it was not added to 1814the problem matrix<br> 1815 </li> 1816 <li><span style="font-style: italic;">binding</span> 1817the constraint was satisfied and binding, so it was not added to the 1818problem mattrix</li> 1819 <li><span style="font-style: italic;">inactive </span> 1820the constraint was inactive, so it was not added to the problem matrix</li> 1821 <li><span style="font-style: italic;">violated </span> the 1822constraint was violated. This status should not be seen if problem was 1823solved successfully [because the constraint would have been added to 1824the problem and resolved]</li> 1825 <li><span style="font-style: italic;">invalid </span> the 1826constraint was invalid. Some problem occurred at the C level when 1827trying to add the constraint to the problem matrix. This status 1828should not be seen normally.</li> 1829 </ul> 1830</ul> 1831<div style="margin-left: 40px;">these status are mapped to their 1832numeric value by the predicate cp_cstr_state_code/2, which should also 1833correspond to the C level numeric values for these Map values (defined 1834by the macros CSTR_STATE_*)<br> 1835</div> 1836<p></p> 1837<p>Cut pool constraints can only involve variables that are present in 1838the problem at set up. This is done to avoid the problem of 1839backtracking 1840pass the creation of the variables. While it is possible to relax this 1841restriction to variables that exist at set up time rather than those 1842that 1843have been added to the problem, this condition is harder to enforce and 1844understand. For this purpose, the number of columns after problem set 1845up 1846is remembered in the problem handle (in problem parameter 15, accessed 1847via cplex_get_prob_param), and variables with larger column numbers are 1848not allowed in the cut pool constraints. A subtlety arises with a 1849problem 1850variable that represents multiple columns -- we cannot reject a 1851variable 1852simply by looking at its first column number, we can only reject the 1853variable 1854as a new variable after going through all the column numbers. 1855</p> 1856<p>User level predicate to add cutpool constraints: 1857</p> 1858<h3>lp_add_cutpool_constraints</h3> 1859add constraints to cutpools respectively. Options allow the active and 1860add_initially status to be specified (both can be changed later on), as 1861well as a named group for the constraints.<br> 1862<br> 1863<p style="font-family: monospace;"> 1864lp_add_cutpool_constraints 1865<br> 1866 1867normalise and check that the constraints are non-ground<br> 1868 1869extract the options<br> 1870 1871add constraints to cutpool (using setup_newrows) <br> 1872 1873add cutpool constraint information <br> 1874 1875(named group, add_initially and active states) 1876</p> 1877<p>note that the failure can occur while adding constraints. In this 1878case, 1879the cutpool will be restored to its original size before the 1880constraints 1881are added. It is assumed that once the constraints have been added, 1882adding 1883the cutpool information cannot fail.<br> 1884</p> 1885<p>It is a deliberate design decision not to provide an eplex_* version 1886of lp_add_cutpool_constraints for eplex instances. One reason is that 1887we don't have a good abstraction for constraint indexes for eplex 1888instance. Secondly, other eplex_* family of predicates allow the 1889predicate to be called before problem setup, and as cutpool constraints 1890are implemented at the C level using the C problem handle, cutpool 1891constraints cannot be added before problem setup without more 1892infrastructure at the ECLiPSe level to do so.<br> 1893However, note that it is possible to add cutpool constraints to eplex 1894instances using lp_add_cutpool_constraints and the handle for the eplex 1895instance.<br> 1896</p> 1897<h3>lp_get, lp_set</h3> 1898these are used to get information for cutpool constraints 1899(cutpool_info), 1900and to change coptions for cutpool constraints (cutpool_option), 1901and also to create new named groups (cutpool_name). Setting the options 1902is effective immeidately, and is non-logical (i.e. it is not undone on 1903backtracking).<br> 1904<br> 1905Predicates affected by cutpool constraints:<br> 1906<h3>lp_write</h3> 1907the problem that is dumped includes all the active cutpool constraints<br> 1908<h3>cplex_optimise</h3> 1909if there are cutpool constraints, the external solver can be invoked 1910multiple times. As cplex_optimise is the C-level interface predicate 1911for solving a problem, this affects all user level problem solving 1912predicates like lp_solve, lp_proble. The<span 1913 style="font-family: monospace;"> write_before_solve </span>option now 1914dumps the problem at the C level rather than call lp_write. This ensure 1915that the problem is dumped for each invocation of the solver. <br 1916 style="font-family: monospace;"> 1917<br> 1918<h2> 1919<a name="C Code Level"></a><u>C Code Level</u></h2> 1920<h3> 1921Versions</h3> 1922The C code needs to be compiled separately for every version of the 1923Cplex 1924or Xpress solver , and every solver interfaced trhough OSI that we want 1925to support. The makefile builds 1926differently 1927named shared libraries from the single eplex.c source file, e.g. 1928<ul> 1929 <li>secplex65.so for Cplex 6.5 (compiled with -D<i>CPLEX=6</i> and -D<i> 1930CPLEXMINOR=5</i>)</li> 1931 <li>sexpress1412.so for Xpress 14.12 (compiled with -D<i>XPRESS=14</i>)</li> 1932 <li>seosiclpcbc.so OSI with Clp (linear) and Cbc (MIP) (compiled with 1933-DOSI for seplex.c, -DCOIN_USE_CLP for conplex.cpp)<br> 1934 </li> 1935</ul> 1936One Eclipse distribution can contain several versions of the compiled C 1937code for different solvers and different solver versions. At runtime 1938however, 1939when lib(eplex) is loaded, it can only load one of them. Which one gets 1940loaded depends on the information in the <b>eplex_lic_info.ecl</b> 1941file, 1942see the loader code at the beginning of eplex.pl.<br> 1943<br> 1944For OSI, the `version' information is used to give the actual solver 1945(or combination of solvers) interfaced through OSI. Currently we do not 1946provide separate interfaces to different versions of these solvers, 1947because the COIN solvers do not have a very clearly defined concept of 1948version, as the source is constantly updated. <br> 1949<p>The C code links in the external solver library code statically if 1950possible, 1951and is itself dynamically loaded when lib(eplex) is loaded. However, 1952static 1953linking is not possible with Xpress 14, and in addition two dynamic 1954libraries: 1955the solver itself, and the licensing code, have to be loaded. In 1956addition, 1957the files must be loaded with their full name, including the minor 1958version 1959numbers at the end (e.g. libxprl.so.1.0.3), as this is checked in some 1960systems. To make our code as generic as possible, we ensure that only 1961one 1962copy of each dynamic library is copied into the right subdirectory and 1963preload (in ECLiPSe code) the library by specifying the file name 1964partially 1965(e.g. libxprl.so.* ). 1966</p> 1967<h3>Problem descriptor</h3> 1968We maintain a C-level problem descriptor (which is itself referred to 1969by 1970the Prolog level problem handle) 1971<ul> 1972 <li>struct lp_desc {}</li> 1973</ul> 1974This descriptor stores: 1975<ul> 1976 <li>the solver-specific problem descriptor (CPXLPptr for Cplex, 1977XPRSprob 1978for Xpress 13+, COINprob for OSI)</li> 1979 <li>additional data about the problem we want to maintain in 1980non-backtracked 1981storage (e.g. success and failure counters)</li> 1982 <li>all data (esp. arrays) that need to be built up incrementally 1983during 1984problem 1985setup, and that are then used as input to the solver's own problem 1986setup 1987function. These are not maintained after the data is passed to the 1988external 1989solver.</li> 1990 <li>cutpool constraints (the constraints arrays, along with the 1991status arrays, and the arrays for maintaining the name groups) are 1992stored in the descriptor. Unlike the other data, this information is 1993maintained in the descriptor, and is passed to the external solver 1994before each invocation. <br> 1995 </li> 1996 <li>some problem specific settings that are more convenient/efficient 1997to 1998maintain 1999at the C level, e.g. the presolve state</li> 2000</ul> 2001The descriptor has a state which is either one of the solution states 2002described 2003under lp_solve/2, or 2004<ul> 2005 <li>DESCR_LOADED during setup, no solve attempted yet</li> 2006 <li>DESCR_EMPTY after cleanup</li> 2007</ul> 2008<h3> 2009Initialization and finalization</h3> 2010Two C externals are provided for initialise and finalise the whole 2011subsystem, 2012essentially this means dealing with the licences: 2013<ul> 2014 <li> <b>cplex_init(LicenceLocation, SerialNum, SubDir), p_cpx_init</b></li> 2015 <br> 2016tries to obtain a solver licence, fails if this is not possible. The 2017arguments come from the eplex_lic_info.ecl file. SerialNum is only 2018relevant 2019for Cplex runtime licences. SubDir is needed for Xpress 15: this is the 2020directory where the license manager is stored, and is used to set 2021the PATH environment variable, as Xpress calls the license manager 2022without 2023any qualification during initialisation. For OSI, nothing is done.<br> 2024 <br> 2025 <li><b>cplex_exit, p_cpx_exit</b></li> 2026 <br> 2027releases the solver licence (if required), and deallocation of some of 2028the storage 2029</ul> 2030<h3> 2031Problem name</h3> 2032Xpress requires a problem name when initialising. Moreover, the problem 2033name is used to generate various intermediate results files (mostly 2034during 2035MIP search). If more than one Xpress is running at the same time within 2036the same file space, then name clashes are possible which might lead to 2037incorrect behaviour. In order to avoid this, the problem name is 2038generated 2039from the machine's host id and the current process's id. 2040<p>For Xpress, the problem name can contain directory paths, so that 2041the 2042intermediate files can be written in other directory than the current 2043directory. 2044To allow for this, we allow the user to specifiy a "tem_dir" option for 2045the path. This can have a large impact on performance (elasped time), 2046because 2047the accessing the current directory can be slow (e.g. a NFS file store, 2048like our local file space), and in addition this will allow the user to 2049run their program in a directory they do not have write permission for. 2050</p> 2051<h3>Problem setup and cleanup</h3> 2052Problem setup requires calling many small C externals from the Eclipse 2053code. It is done is three steps. First, cplex_prob_init/8 allocates a C 2054level descriptor including sufficiently large arrays. These arrays are 2055the filled successively using the cplex_set_xxx or cplex_loadxxx 2056functions. 2057When this is finished, cplex_loadprob calls the actual Cplex/Xpress/Osi 2058setup 2059routine, passing the previously prepared arrays. In the following, CPH 2060stands for the C level handle, I stands for row numbers, J for column 2061numbers: 2062<ul> 2063 <li> <b>cplex_prob_init(PreSolve,UseCopy,Rows,Cols,NonZeros,TempDir,Sense,-Handle), 2064p_cpx_prob_init</b></li> 2065 <br> 2066allocates the C-level handle and stores it into the first argument 2067of the Eclipse-level handle. Also allocates arrays for a complete 2068column-wise 2069representation of a problem of the given size (number of rows, columns, 2070nonzeros). An undo-function is trailed which will deallocate the handle 2071with all its arrays on backtracking or garbage collection. The Presolve 2072argument is either 1 or 0, and the C level descriptor's presolve field 2073is set to this value. Before calling any external 2074solver 2075library calls that may be affected by the presolve state, the presolve 2076state is set according to the presolve field. This allows the presolve 2077state to be set on a per-problem basis. TempDir is the path for a 2078temporary 2079working directory, which is needed by Xpress. For better performance, 2080this 2081directory should be on a local disk. 2082</ul> 2083<ul> 2084 <li> <b>cplex_set_rhs_coeff(CPH,I,SenseCode,Rhs), p_cpx_set_rhs_coeff</b></li> 2085</ul> 2086 set constraint 2087sense 2088and right hand side for constraint row I. 2089<ul> 2090 <li> <b>cplex_set_obj_coeff(CPH,J,Val), p_cpx_set_obj_coeff</b></li> 2091 <br> 2092set objective coefficient for variable column J. <br> 2093 <li><b>cplex_set_qobj_coeff(CPH,J1,J2,Val), p_cpx_set_qobj_coeff</b></li> 2094 <br> 2095set quadratic objective coefficient for the product of variables column 2096J1 and J2<br> 2097 <br> 2098 <li><span style="font-weight: bold;">cplex_set_type(CPH,J,TypeCode), 2099p_cpx_set_type</span></li> 2100 <br> 2101set type of variable column J. TypeCode is a ASCII code for C, 2102I or B. This is done only for a column that has not yet been passed to 2103the solver, i.e. the type is set in the buffer array ctype, which is 2104later 2105passed to the external solver. For modifying an existing column 2106type, 2107cplex_change_col_type/4 should be used. 2108</ul> 2109<ul> 2110 <li> <b>cplex_set_matbeg(CPH,J,K,K1), p_cpx_set_matbeg</b></li> 2111 <br> 2112coefficient array locations K to K1-1 contain entries for column J. <br> 2113 <li><b>cplex_set_matval(CPH,K,I,Cij), p_cpx_set_matval</b></li> 2114 <br> 2115set the matrix coefficient for row I and column J (implicit) in 2116coefficient 2117array location K. <br> 2118 <li style="font-weight: bold;"><b>cplex_init_new_col_bound(CPH,Cj, 2119Lo, Hi),p_cpx_init_new_col_bound</b></li> 2120</ul> 2121<div style="margin-left: 40px;"> 2122Initialise the bounds for a new column J in the external 2123solver 2124to Lo..Hi. This should be used only for setting the initial bounds of a 2125column (during setup and also when a new column is added). This is 2126because 2127no undo function is setup to restore a previous bound. For modification 2128of existing bounds of a column, use the cplex_impose_col_* family of 2129functions 2130instead. 2131</div> 2132<ul> 2133 <li> <span style="font-weight: bold;">cplex_new_col_bound(CPH,Cj,Bd,Which),p_cpx_new_col_bound</span></li> 2134</ul> 2135<div style="margin-left: 40px;"> 2136This is for the special case of updating the Which bound 2137(<0: 2138lower, 0: both, >0: upper) of column J that has been initialised, 2139but the 2140new bound(s) does not need to be backtracked, so there is no need to 2141use 2142the cplex_impose_col_* functions. This occurs for example when bound 2143constraints 2144were posted to a problem before solver setup. A column's bound would 2145initially 2146be initialised with cplex_init_new_col_bounds(), but the bound(s) can 2147then 2148be updated by the bound constraint(s) during solver setup. 2149</div> 2150<ul> 2151 <li> <b>cplex_set_var_name(CPH, Cj, Name), p_cpx_set_var_name</b></li> 2152</ul> 2153 set the name for 2154the variable column J in the external solver. This name will 2155<br> 2156 be used when 2157the external solver prints the problem. 2158<ul> 2159 <li> <b>cplex_loadbase(CPH,Basis), p_cpx_loadbase</b></li> 2160 <br> 2161load a basis (a string buffer, obtained by retrieving from the handle 2162earlier) <br> 2163 <li><b>cplex_loadorder(CPH,Length,OrderList), p_cpx_loadorder</b></li> 2164 <br> 2165load MIP branching order preferences (undocumented feature) <br> 2166 <li><b>cplex_loadsos(CPH,SosType,Size,Js), p_cpx_loadsos</b></li> 2167 <br> 2168load definition of an SOS 1 or 2. Js is a list of length Size of the 2169column numbers that make up the SOS. <br> 2170 <li><b>cplex_loadprob(CPH), p_cpx_loadprob</b></li> 2171 <br> 2172set up the actual solver problem using the (now filled) arrays in the 2173C level handle. <br> 2174 <li><b>cplex_cleanup(CPH), p_cpx_cleanup</b></li> 2175 <br> 2176free the problem descriptor (this also happens on untrailing and 2177garbage 2178collection). 2179</ul> 2180<h3> 2181Problem modification</h3> 2182Most of the modification functions are split into the transfer of the 2183information 2184into growable arrays (hidden on the C level), and a flush-function 2185which 2186conveys the array contents to the actual solver: 2187<ul> 2188 <li> <b>cplex_new_obj_coeff(CPH,J,Val), p_cpx_new_obj_coeff</b></li> 2189 <br> 2190set new linear objective coefficients <br> 2191 <li><b>cplex_flush_obj(CPH), p_cpx_flush_obj</b></li> 2192 <br> 2193actually transfer new linear objective coefficients to the solver <br> 2194 <li><b>cplex_new_qobj_coeff(CPH,J1,J2,Val), p_cpx_new_qobj_coeff</b></li> 2195 <br> 2196set new quadratic objective coefficients <br> 2197 <li><span style="font-weight: bold;">cplex_set_new_cols(CPH, 2198NAdded, 2199NewObjCoeffs,NZeros), 2200p_cpx_set_new_cols</span></li> 2201 <br> 2202prepare the column-wise buffer arrays for NAdded new columns, with 2203NZeros non-zero coefficients in these columns. NewObjCoeffs is either 2204an 2205empty list if the new objective coefficients are all zero, or a list of 2206length NAdded of the objective coefficients for the new columns. <br> 2207 <li><b>cplex_new_row(CPH,SenseCode,Rhs,CType,Idx), p_cpx_new_row</b></li> 2208 <br> 2209start adding a new row with given constraint sense and right hand side, 2210for constraint type CType (normal or 2211cutpool). Idx is returned with the row index of the row <br> 2212 <li> <b>cplex_add_coeff(CPH,J,Cij,CType), p_cpx_add_coeff</b></li> 2213 <br> 2214set coefficient for column J in currently added row (of type CType: 2215normal or cutpool) <br> 2216 <li><b>cplex_flush_new_rowcols(Handle,HasObjs), 2217p_cpx_flush_new_rowcols</b></li> 2218 <br> 2219actually transfer zero or more new rows and columns to the solver. <br> 2220HasObjs is zero if the new columns have zero objective coefficients. 2221If this is non-zero, then the objective coefficients for the new 2222columns 2223are also passed to the solver. The new columns can have non-zero values 2224for the existing (pre-addition) rows; all the data should have been 2225correctly 2226transferred to the C level buffer arrays before this function is 2227called. 2228Note the Prolog handle is taken rather than CPH; the timestamp in the 2229Prolog 2230handle is for the undo function _cpx_del_rowcols to remove the added 2231rows 2232and columns. <br> 2233 <li style="font-weight: bold;"><b>cplex_impose_col_bounds(Handle, 2234Attr, J, Flag, Lo, Hi, Changed), p_cpx_impose_col_bounds</b></li> 2235</ul> 2236<div style="margin-left: 40px;"> 2237try to impose the bounds Lo..Hi on column J. Fail if 2238the interval for the column becomes empty after the bounds change. If 2239Flag 2240is 1, both new bounds are only imposed (passed to the external solver) 2241if the new bound is more narrow. If Flag is 0, the new bounds are not 2242checked 2243against the existing bounds (this is only used by external libraries, 2244not 2245by eplex). If either bound is imposed, an undo function 2246_cpx_restore_bounds 2247is trailed using the Attr's timestamp. Because of the time stamp, the 2248function 2249can be trailed at most once, and it restores both bounds, regardless of 2250which was changed. Also, because it uses the Attr as the time stamp, 2251the 2252column number must stay the same for the same Attri - this is the first 2253column in the column index list. <br> 2254Handle is needed during the execution of the undo function to obtain 2255the CPH. Changed is set to 1 if either bound was changed. This is 2256needed at the Prolog level, e.g. to schedule the demon solver because 2257the 2258bound has changed. Note this can be used to impose bounds on a newly 2259added 2260column which has not yet been passed to the external solver. In this 2261case, 2262it is regarded as initialising the column's bounds, no undo function is 2263trailed, and Changed is set to 0. 2264</div> 2265<ul> 2266 <li style="font-weight: bold;"> <b>cplex_impose_col_lwb(Handle, 2267Attr, J, Lo, Changed), 2268p_cpx_impose_col_lwb</b></li> 2269</ul> 2270<div style="margin-left: 40px;"> 2271try to impose the lower bound Lo on column J. Fail if the 2272interval 2273for the column becomes empty after the bound change. Lo is only imposed 2274(passed to the external solver) if it is greater than the current lower 2275bound. In this case, an undo function _cpx_restore_bounds is 2276trailed 2277using the Attr's timestamp, which restores both bounds, regardless of 2278which 2279was changed. Changed is set to 1 if the bound was changed. This 2280is 2281needed at the Prolog level, e.g. to schedule the demon solver because 2282the 2283bound has changed. 2284</div> 2285<ul> 2286 <li style="font-weight: bold;"> <b>cplex_impose_col_upb(Handle, 2287Attr, J, Hi, Changed), 2288p_cpx_impose_col_upb</b></li> 2289</ul> 2290<div style="margin-left: 40px;"> 2291try to impose the upper bound Hi on column J. Fail if the 2292interval 2293for the column becomes empty after the bound change. Hi is only imposed 2294(passed to the external solver) if it is less than the current upper 2295bound. 2296In this case, an undo function _cpx_restore_bounds is trailed 2297using 2298the Attr's timestamp, which restores both bounds, regardless of which 2299was 2300changed. Changed is set to 1 if the bound was changed. This is 2301needed 2302at the Prolog level, e.g. to schedule the demon solver because the 2303bound 2304has changed. 2305</div> 2306<ul> 2307 <li> <b>cplex_change_col_type(Handle, J, TypeCode), 2308p_cpx_change_type</b></li> 2309</ul> 2310<ul> 2311 <a name="cplex_change_col_type"></a>change the type of column J to 2312TypeCode (the code for the type obtained from 2313type_to_cplex_type/4). 2314Handle's timestamp is needed for the undo function _cpx_reset_col_type 2315to reset the column type on backtracking. Attr is the eplex attribute 2316for 2317this solver state for the variable representing column J. This is 2318needed 2319to avoid warnings from Xpress 14 when a column is changed to integer 2320type 2321with bounds greater than representable with 32 bits 2322(XPRS_MAXINT): 2323if a column bound originally has greater bounds, they are set to 2324XPRS_MAXINT, 2325and an undo function _cpx_restore_bounds is used to restore the bounds. 2326No timestamp is used in this case because the column type can be 2327changed 2328for merged columns, which no longer have a unique Attr. This should 2329happen 2330at most once per forward execution per column, so it should not be too 2331expensive. <br> 2332 <li><b>cplex_change_lp_to_mip(Handle), p_cpx_change_lp_to_mip</b></li> 2333 <p> changes a lp type probelm to a mip type problem. Change is 2334undone on backtracking.<br> 2335 </p> 2336 <li> <b>cplex_change_obj_sense(CPH, Sense), 2337p_cpx_change_obj_sense</b></li> 2338 <br> 2339 <p>used for probing. Sets the sense of the objective to Sense. <br> 2340 </p> 2341 <li><b>cplex_change_rhs(CPH, Size, RowIdxs, RhsCoeffs), 2342p_cpx_change_rhs</b></li> 2343 <br> 2344 <p>used for probing, Change the rhs coeffs in the rows 2345specifiied 2346in RowIdxs to RhsCoeffs. RowIdxs and RhsCoeffs are lists of the same 2347length, 2348Size is the length of these lists. <br> 2349 </p> 2350 <li><b>cplex_change_column_bounds(CPH, Size, Idxs, Los, His), 2351p_cpx_change_column_bounds</b></li> 2352 <br> 2353 <p>used for probing. Change the column bounds specified in Idxs to 2354Los 2355(lower bound) and His (upper bound). Idxs, Los and His are lists of 2356length 2357Size. The bounds are changed without an untrail function to undo the 2358change 2359on backtracking. <br> 2360 </p> 2361 <li><b>cplex_set_problem_type(CPH, Type, SetSolverType), 2362p_cpx_set_problem_type</b></li> 2363 <br> 2364 <p>used for probing. Sets the eplex problem type to Type. If 2365SetSolverType 2366is 1, then the solver's problem type is also set to Type. <br> 2367 </p> 2368</ul> 2369For Xpress, only the bounds for a MIP problem can be modified once the 2370MIP search is started. To get round this restriction, we make a copy of 2371the problem, which is pointed to by lpcopy, and solve the problem using 2372the copy so that the original can still be modified. This produces the 2373problem of : 2374<br> 2375 2376<ul> 2377 <li>The problem pointers lp and lpcopy are always present, even when 2378it is 2379not needed. In these cases, lpcopy and lp points to the same problem.</li> 2380</ul> 2381<ul> 2382 <li>When copying is needed, the problem is copied from lp to lpcopy 2383just 2384before 2385it is solved as a MIP problem, and any modifications to the problem is 2386always done to lp, not lpcopy. Once solved, solution data is obtained 2387from 2388the copy until it becomes invalid when the problem is modified (either 2389by forward execution or backtracking in ECLiPSe; the appropriate 2390function 2391must make the copy invalid by changing the copystatus, see next item).</li> 2392</ul> 2393<ul> 2394 <li>In XPRESS 13+, which needs the problem copy for MIP modification, 2395an 2396extra 2397field in lp_desc, <span style="font-weight: bold;">copystatus</span>, 2398is used to specify the status of the copy:</li> 2399</ul> 2400<ul> 2401 <ul> 2402 <li>XP_COPYOFF: we are not using a copy (MIP modification would not 2403be 2404possible, 2405but solving single MIP problems will avoid the copying overhead)</li> 2406 <li>XP_COPYINVALID: the problem in lpcopy is invalid.</li> 2407 <li>XP_COPYCURRENT: the problem in lpcopy is current</li> 2408 </ul> 2409</ul> 2410<div style="margin-left: 40px;">The copystatus is used to determine if 2411information is extracted from lp or lpcopy in procedures that are 2412called 2413independently from ECLiPSe. Currently this applies only to 2414p_cpx_lpwrite(). 2415Other accesses to lpcopy are done in code that occurs in 2416p_cpx_optimise(), 2417after the call to optimise. Here, lpcopy is either valid and pointing 2418to 2419the problem copy with the result of the optimisation, or to lp, if 2420copying 2421is not needed (Cplex, or LP/QP in Xpress).</div> 2422<span style="font-weight: normal;"></span>An LP problem can change into 2423a MIP problem if integers constraints are added. This may happen after 2424the problem is initially loaded. This is not a problem for Cplex, which 2425loads all problems with the same routine. Xpress however, has different 2426routines for loading different problem types. We get around this by 2427always 2428using the `global' loading routine (XPRSloadglobal()) for both LP and 2429MIP 2430problems. If the problem is an LP problem, it is simply solved as an LP 2431problem in XPRSminim/maxim. This apparently has no implications in 2432performance 2433for an LP problem. An LP problem can thus be changed to a MIP problem. 2434On backtracking, this change is undone by _cpx_reset_mip_to_lp() undo 2435function. 2436<h3>Problem solving and result retrieval</h3> 2437Running the solver is always done with cplex_optimise, regardless of 2438the 2439problem type or the solver method used. 2440<ul> 2441 <li> <b>cplex_optimise(+Handle,+SolvingMethods,+TimeOut,+DumpOpt,+StateArrays-Result,-Status,-Best, 2442-Worst), p_cpx_optimise</b></li> 2443 <br> 2444run the solver, using the given Method (primal,dual,barrier,...), with 2445SolvingMethods specifying the solving methods to be used: 2446m(Method,AuxMethod, 2447NodeMethod,AuxNodeMethod), where AuxMethod specifying the auxiliary 2448method 2449if the method requires it (e.g. crossover for barrier). For mip 2450problems.,Method 2451specifies the method for solving the root node., while NodeMethod 2452specifies 2453the method for the other nodes in the MIP search-tree. If the `default' 2454method is specified but not supported by the solver (e.g. older 2455CPLEXes), 2456this is translated to what the `default' method is, as specified in the 2457solver's manual. If the specified method is not supported by the 2458solver, the default method is used instead (with a warning printed). 2459 <p>If TimeOut is non-zero, set the solver's timeout to TimeOut. 2460Timeout 2461should be in the correct type and value for the solver [this is ensured 2462at the ECLiPSe level]. In the case of CPLEX, the timeout is always set 2463- if it is zeo, it is set to the default value (a large number).<br> 2464 </p> 2465 <p>Result is the resulting descriptor state (DESCR_XXX) and Status is 2466the 2467underlying solver's own return code (the latter is never interpreted by 2468the Eclipse level code, it is just printed or passed to a user error 2469handler). </p> 2470 <p>Best and Worst are the best and worst bounds on the optimal 2471objective 2472value. See <a href="bestworst">this</a> for more description.<br> 2473 </p> 2474 <p>DumpOpt specifies if the problem should be dumped before solving. 2475If it is to be dumped, DumpOpt is a structure <span 2476 style="font-family: monospace;">write_before_solve(Format,File)</span> 2477specifying the dump format and file name. The problem will then be 2478dumped before the external solver is invoked. In particular, if the 2479external solver is invoked multiple times because of cutpool 2480constraints, the problem is dumped for each invocation.<br> 2481 </p> 2482 <p>If there are no cutpool constraints, the external solver is 2483invoked once to solve the problem. If there are cutpool constraints, 2484the external solver can be invoked multiple times. See <a 2485 href="#cpsupportcplex_opt">here</a> for more description of cutpool 2486constraint related code in cplex_optimise().</p> 2487 <p>The solution state is passed back to the ECLiPSe level by binding 2488the 2489correct field in the ECLiPSe handle problem structure. The 2490argument 2491position of the field in the structure is giving by StateArrays: 2492out(Sols, 2493Pis, Slacks,Djs,ColBase,RowBase,Map), corresponding to the 2494solutions, 2495dual solutions, slack variables, reduced costs, column basis, row 2496basis and condtional mapping arrays in the ECLiPSe Handle problem 2497structure. 2498The Map array is not really a result, but a mapping for the cutpool raw 2499index to the problem matrix (see <a href="#cutpoolmap">here</a> 2500) If any of 2501the other arrays are not required, their corresponding argument 2502position 2503in the Handle is left as a variable. Otherwise, the corresponding 2504values for the arrays are obtained from the solved problem. Note that 2505values 2506may be unavailable for some arrays if the problem is a mixed-integer 2507type. </p> 2508 <p>After solving the problem and extracting the state results, 2509the 2510cutpool constraints are removed from the problem by resetting the 2511problem 2512matrix -- this must be done after all the required results are 2513extracted, 2514because in some solvers, results cannot be extracted after the matrix 2515is 2516changed in this way. <br> 2517This restoration of the original problem is also done if 2518p_cpx_optimise 2519need to be aborted. <br> 2520The cutpool constraints are added and removed in this way to allow 2521normal constraints to be added to and removed from the problem in 2522the normal way. </p> 2523 <p>For Xpress, the problem is not post-solved when aborted (i.e. the 2524problem 2525was not solved to completion), for LP problems, the problem is 2526postsolved 2527after extracting any solution information from it, as otherwise the 2528problem 2529can no longer be modified. This is done via the undocumented 2530XPRSpostsolve(), 2531which is available for Xpress > 15 only.</p> 2532</ul> 2533There is one function to return the objective value: 2534<ul> 2535 <li> <b>cplex_get_objval(+CPH,-Cost), p_cpx_get_objval</b></li> 2536 <br> 2537get the cost of the solution found. This is now obtained from 2538the problem descriptor field objval, which is set in 2539p_cpx_optimise. <br> 2540 <li><b>get_darray_element(+Darray,+I,-Value), 2541p_get_darray_element</b></li> 2542 <br> 2543get element I of a darray <br> 2544 <li><b>darray_list(+Darray,+M,-List), p_darray_list</b></li> 2545</ul> 2546<div style="margin-left: 40px;"> 2547<blockquote>convert the first M entries of a darray to a list of 2548doubles, 2549returns an out of range error if array size < M. M is 2550there 2551so that irrelevant data at the end of the array (e.g. the rows 2552generated 2553for cut pool constraints in the row results array) can be omitted.</blockquote> 2554</div> 2555<ul> 2556 <li>d<b>array_size(+Darray, -Size), p_darray_size</b></li> 2557</ul> 2558<div style="margin-left: 40px;"> 2559<blockquote>get the size (number of elements) of a darray</blockquote> 2560</div> 2561<ul> 2562 <li> <b>get_iarray_element(+Iarray,+I,-Value), p_get_iarray_element</b></li> 2563</ul> 2564<div style="margin-left: 40px;"> 2565<blockquote>get element I of an iarray</blockquote> 2566</div> 2567<ul> 2568 <li> <b>set_iarray_element(+Iarray,+I,+Value), p_set_iarray_element</b></li> 2569</ul> 2570<div style="margin-left: 40px;"> 2571<blockquote>set element I of an iarray</blockquote> 2572</div> 2573<ul> 2574 <li> <b>iarray_list(+Iarray,-List), p_iarray_list</b></li> 2575</ul> 2576<div style="margin-left: 40px;"> 2577<blockquote>convert an iarray to a list of integers</blockquote> 2578</div> 2579<ul> 2580 <li> <b>iarray_size(+Iarray,-Size), p_iarray_size</b></li> 2581</ul> 2582<div style="margin-left: 40px;">get the size (number of elements) of an 2583iarray</div> 2584<ul> 2585 <li> <b>create_iarray(+Size,-Iarray), p_create_iarray</b></li> 2586</ul> 2587<div style="margin-left: 40px;"> 2588<blockquote>create an iarray of size Size.</blockquote> 2589</div> 2590A darray (iarray) is actually an Eclipse string, but it contains 2591doubles 2592(integers) rather than characters. We use these as the most efficient 2593way 2594of saving large floating point result arrays to the Eclipse global 2595stack. 2596<p>The various results arrays (solution, dual, slacks, reduced costs 2597and 2598basis) are retrieved inside p_cpx_optimise(). This is done either by 2599setting 2600up a callback function (Xpress 13+, MIP problems), or directly after a 2601(successful) optimisation. In Xpress 13+, setting the callback function 2602avoids Xpress writing solution files during MIP. Note that some files 2603are 2604still created during the MIP search, however. The cleanup routines 2605(p_cpx_cleanup()) 2606will delete any such file for the current session, but if it is not 2607called 2608(e.g. because of some crash), then extra files may be left behind. 2609</p> 2610<h3><a name="bestworst"></a>Dealing with best and worst obj bounds</h3> 2611After invoking the solver, p_cpx_optimise determines the best and worst 2612bounds on the objective value, regardless of the status of the solve. 2613We 2614use best/worst bounds so that we don't need to worry about the 2615optimisation 2616direction when computing these bounds: for minimisation, best bound is 2617the lower bound, and worst bound the upper bound. 2618<p>The way the bounds are determined depends on the optimisation method 2619used and the status of the solve. 2620</p> 2621<p>For LP/QP: 2622</p> 2623<ul> 2624 <li>no (primal/dual) feasible solution, e.g. phase 1 of two phase 2625Simplex: 2626no information on bounds [According to Oliver Bastert of DASH, 2627the 2628primal and dual objective values can usually serve as bounds even if 2629they 2630are infesible, but there are degenerate cases where this is not true]</li> 2631 <li>primal feasible, e.g. phase 2 of primal simplex, or have a 2632primal 2633feasible solution for barrier: there is a feasible solution, and it is 2634a worst bound [the optimal objective is at least as good as our 2635possibly 2636suboptimal objective]</li> 2637 <li>dual feasible, e.g. phase 2 of dual simplex, or have a dual 2638feasible 2639solution 2640for barrier: the dual `solution' is superoptimal for the original 2641problem. 2642The dual objective is a best bound on the optimal objective</li> 2643</ul> 2644For MIP: 2645<ul> 2646 <li>a (best) feasible integer solution is a worst bound on the optimal</li> 2647 <li>after finding a feasible integer solution, the MIP search will 2648look for 2649a better integer solution, defined by the feasible integer solution + a 2650MIP tolerance. Thus, if an optimal is found, the best bound is the 2651objective 2652+ MIP tolerance</li> 2653 <li>best bound is the `worst' objective value at any 2654search-tree 2655node. Both CPLEX and Xpress provide function calls to obtain this *<span 2656 style="font-style: italic;">if 2657the MIP search (i.e. not counting the root node solve) have 2658started</span>*</li> 2659 <li>if any node was `cut-off', i.e. not branched on because its 2660objective 2661is 2662worse than the cut-off value, then if no solution is found, this 2663objective 2664is a best bound. Unfortunately, neither CPLEX and Xpress allow the user 2665to determine if any node had been cutoff during the MIP search, so 2666strictly 2667a infeasible MIP state means that that no feasible solution better than 2668the cut-off value exist, i.e. the cut-off value is the best bound 2669for an infeasible MIP.</li> 2670 <li>if MIP search was aborted at the root node:</li> 2671 <ul> 2672 <li>root node solve completed: objective is a best bound</li> 2673 <li>root node solve aborted: if primal feasible, objective is a 2674best bound</li> 2675 </ul> 2676</ul> 2677The tightest of the valid bounds are used. 2678<p>The bounds are computed when the solution result is determined: this 2679is because the same return code/statuses from the solver is needed to 2680determine 2681how to get the bounds, along with the exact method used to solve the 2682problem. 2683<br> 2684From the return codes after solving the problem, several macros are 2685defined for the various solvers, to determine the state: 2686<br> 2687 2688<br> 2689<table style="text-align: left; width: 100%;" border="1" cellpadding="2" 2690 cellspacing="2"> 2691 <caption><br> 2692 </caption><tbody> 2693 </tbody> <tbody> 2694 <tr> 2695 <td style="vertical-align: top;">SuccessState</td> 2696 <td style="vertical-align: top;">solution is optimal (may be 2697optimal within 2698tolerance)</td> 2699 </tr> 2700 <tr> 2701 <td style="vertical-align: top;">FailState</td> 2702 <td style="vertical-align: top;">problem is proven infesible or 2703(for MIP), 2704no feasible solution exists that is better than cutoff</td> 2705 </tr> 2706 <tr> 2707 <td style="vertical-align: top;">MIPSemiSuccessState</td> 2708 <td style="vertical-align: top;">MIP only: solution exists, but 2709may be 2710suboptimal</td> 2711 </tr> 2712 <tr> 2713 <td style="vertical-align: top;">MIPSemiFailState</td> 2714 <td style="vertical-align: top;">MIP only: no solution found, but 2715problme 2716not proven infeasible</td> 2717 </tr> 2718 <tr> 2719 <td style="vertical-align: top;">LPAbortedState</td> 2720 <td style="vertical-align: top;">solve was aborted in solving an 2721LP problem. 2722Depending on solver, this may include the root node LP solve of a MIP 2723probelm 2724(for Xpress). For LP, we cannot determine if problem is in a semi-fail 2725or semi-success state without looking at the solving method</td> 2726 </tr> 2727 <tr> 2728 <td style="vertical-align: top;">UnboundedState</td> 2729 <td style="vertical-align: top;">problem is unbounded</td> 2730 </tr> 2731 <tr> 2732 <td style="vertical-align: top;">MaybeFailState</td> 2733 <td style="vertical-align: top;">problem is either infeasible or 2734unbounded, 2735but solver cannot determine which</td> 2736 </tr> 2737 </tbody> 2738</table> 2739</p> 2740<p>For each state, we determine the bounds and the actual status 2741returned 2742(DESC_SOLVED_SOL etc.). This requires the actual solving method used in 2743the LP cases. For CPLEX, this can be obtained by calls to the solver, 2744but 2745for Xpress, we need to do this ourselves, by remembering the method 2746used 2747to call the solver, and figuring out what the `default' method maps to 2748-- this may change between versions and need to be updated. 2749</p> 2750<p>For FailState in MIP, the best bound is currently set to the cutoff. 2751This is because there does not appear to be a way of determining if any 2752search-tree node had been cutoff during the search, so there is no way 2753of distinguishing `true' infeasibility (where no cutoff occurred). 2754</p> 2755<p>The bounds are computed in all cases, even for failure cases, even 2756though 2757there is currently no way to make use of this information. A failure 2758handler 2759may be developed (this will only be useful if functionality is added to 2760access the solvers information on causes for failures, e.g. IIS) 2761<br> 2762 2763</p> 2764<h3>Retrieving problem data</h3> 2765These are non-essential functions, used to retrieve information from 2766the 2767C level handle: 2768<ul> 2769 <li> <b>cplex_get_prob_param(+CPH,+Which,-Value), 2770p_cpx_get_prob_param</b></li> 2771 <br> 2772retrieve handle-specific properties (problem type, last status) and 2773statistics (size, counters) <li><span style="font-weight: bold;">cplex_get_col_bounds(CPH, 2774J, Lo, 2775Hi), 2776p_cpx_get_col_bounds</span></li> 2777</ul> 2778<div style="margin-left: 40px;">get the column bounds Lo..Hi for column 2779J.</div> 2780<ul> 2781 <li> <span style="font-weight: bold;">cplex_get_col_type(CPH, J, 2782TypeCode), 2783p_cpx_get_col_type</span></li> 2784</ul> 2785<div style="margin-left: 40px;">get the column type for the column 2786J. 2787TypeCode is one of the ASCII code B, I or J.</div> 2788<ul> 2789 <li> <b>cplex_get_row(+CPH,+CType,+I,-Delta), p_cpx_get_row</b></li> 2790 <br> 2791prepare retrieval of row information for row I of constraint type 2792CType: 27930 for normal problem constraint, 1 for unconditional cut pool, 2 for 2794conditional 2795cut pool, Delta is the displacement into the row values arrays 2796(rmatind, 2797rmatval) for the start of the row.<br> 2798 <br> 2799 <li><b>cplex_get_rhs(+CPH,+CType,+I,-SenseCode,-Rhs), p_cpx_get_rhs</b></li> 2800 <br> 2801get current rowof type CType's sense and right hand side<br> 2802 <br> 2803 <li><b>cplex_get_col_coef(+CPH,+CType,+J,-Cij), p_cpx_get_col_coef</b></li> 2804 <br> 2805get coefficient of current row (of type CType), column J<br> 2806 <br> 2807 <li><b>cplex_get_obj_coef(+CPH,+J,-C), p_cpx_get_obj_coef</b></li> 2808 <br> 2809get objective coefficient for column J 2810</ul> 2811<h3> 2812Other functions</h3> 2813<ul> 2814 <li> <b>cplex_get_param(ParamName,Value), p_cpx_get_param</b></li> 2815 <br> 2816get a global parameter setting. The ParamName is an atom. The result 2817type is implicit (float,integer,string). This uses the name mapping 2818table 2819in eplex_params.h <li><b>cplex_set_param(ParamName,Value), 2820p_cpx_set_param</b></li> 2821 <br> 2822set a global parameter. The ParamName is an atom. The required value 2823type is determined by the parameter itself. <li><b><a 2824 name="cplex_lpwrite"></a>cplex_lpwrite(File,Format,CPH,CPCondSet), 2825p_cpx_lpwrite</b></li> 2826 <br> 2827write the problem in a prticular format to File. All active cutpool 2828constraints 2829are added to the problem first (see <a href="#condcpsetupcall">this</a> 2830). These constraints are removed before returning from the call.<br> 2831 <br> 2832 <li><b><a name="cplex_lpread"></a>cplex_lpread(File,Format,Handle), 2833p_cpx_lpread</b></li> 2834 <br> 2835read a problem from a file using the external solver's problem reading 2836routing. Various problem information, such as problem type and size, 2837are read from the problem to set their values in the problem 2838descriptor. For CPLEX, the optimisation sense (min or max) is read from 2839the problem, but this is assumed to be minimse for MPS files, which 2840does not include the optimisation sense. For Xpress, the optimisation 2841sense is assumed to be minimisation for all problems, as it ignores the 2842sense from the problem (the API requires the user to specify the sense 2843when solving a problem). <br> 2844Note that if the input file contain ranged constraints, these will be 2845read in by the external solver correctly, but they cannot be extracted 2846from the external solver correctly, as eplex does not support ranged 2847constraint.<br> 2848 <br> 2849 <li> <b>cplex_lo_hi(NegInf,PosInf), p_cpx_lo_hi</b></li> 2850 <br> 2851returns the solver's idea of negative and positive infinity (something 2852like 1e20) <br> 2853 <li style="font-weight: bold;"><b>cplex_matrix_base(Base), 2854p_cpx_matrix_base</b></li> 2855 <li style="font-weight: bold;"> <b>cplex_matrix_offset(Offset), 2856p_cpx_matrix_offset</b></li> 2857</ul> 2858<div style="margin-left: 40px;"> 2859these two functions are used for specifying the valid 2860column 2861values in the external solver. These are fixed for a particular solver, 2862but can be different between solvers. base is the index for the first 2863valid 2864column (this can generally be 0 or 1), offset is the offset this value 2865is from 0, the start of C arrays. Strictly speaking offset is not 2866needed 2867but can be calculated from base. The two functions are provided to 2868avoid 2869this calculation at runtime at the ECLiPSe level. 2870</div> 2871<p><br> 2872 2873|----|------------------------------------------| 2874<br> 2875 28760 2877base 2878mac-1 2879<br> 2880 2881<---><----------------------------------------> 2882<br> 2883 2884offset 2885valid columns 2886</p> 2887<ul> 2888 <li> <b>cplex_output_stream(ChannelNr,AddRem,StreamNr), 2889p_cpx_output_stream</b></li> 2890 <br> 2891associate or disassociate a Cplex I/O channel (result_channel (0), 2892error_channel(1), warning_channel(2), log_channel (3)) with the given 2893Eclipse 2894stream StreamNr. Xpress has a similar concept of 4 message levels 2895</ul> 2896<center><br> 2897<table nosave="" border="1" cols="5" width="80%"> 2898 <caption> 2899 <center> 2900 <p></p> 2901 </center> 2902 </caption><tbody> 2903 </tbody><tbody> 2904 </tbody><tbody> 2905 </tbody><tbody> 2906 </tbody><tbody> 2907 </tbody> <tbody> 2908 <tr nosave="" bgcolor="#cccccc"> 2909 <td nosave="">Eclipse level name</td> 2910 <td>ChannelNr</td> 2911 <td>Cplex</td> 2912 <td>Xpress msg type</td> 2913 <td>Default Eclipse stream</td> 2914 </tr> 2915 <tr nosave=""> 2916 <td>result_channel</td> 2917 <td>0</td> 2918 <td nosave="">result</td> 2919 <td>2</td> 2920 <td>-</td> 2921 </tr> 2922 <tr nosave=""> 2923 <td>error_channel</td> 2924 <td>1</td> 2925 <td nosave="">error</td> 2926 <td>4</td> 2927 <td>error</td> 2928 </tr> 2929 <tr> 2930 <td>warning_channel</td> 2931 <td>2</td> 2932 <td>warning</td> 2933 <td>3</td> 2934 <td>warning_output</td> 2935 </tr> 2936 <tr> 2937 <td>log_channel</td> 2938 <td>3</td> 2939 <td>log</td> 2940 <td>1</td> 2941 <td>-</td> 2942 </tr> 2943 </tbody> 2944</table> 2945</center> 2946<br> 2947 2948<h3>Undo functions</h3> 2949These functions are setup using ec_trail_undo, which places the 2950function 2951on the trail such that it is called when untrailed. Additionally, 2952ec_trail_undo 2953allows a time-stamped trailing so that the function will only be 2954trailed 2955if the time-stamp is `old' (older than the most recent choicepoint). 2956<ul> 2957 <li> <span style="font-weight: bold;">_untrail_cleanup </span>*non 2958time-stamped*</li> 2959</ul> 2960<div style="margin-left: 40px;">calls p_cpx_cleanup, and then free the 2961problem descriptor. Trailed during p_cpx_prob_init so problem space can 2962be freed upon backtracking</div> 2963<ul> 2964 <li> <span style="font-weight: bold;">_cpx_reset_probtype </span>*non 2965time-stamped*</li> 2966</ul> 2967<div style="margin-left: 40px;">reset a problem type to a non-integer 2968type 2969(LP or QP). CPLEX has to be informed of the changed as well (but 2970not XPRESS). Trailed when problem is changed from a non-integer 2971to 2972mixed-integer problem type.</div> 2973<ul> 2974 <li style="font-weight: bold;">_cpx_restore_bounds <span 2975 style="font-weight: normal;">*non 2976time-stamped*</span></li> 2977</ul> 2978<div style="margin-left: 40px;">restore both bounds of a column. 2979Trailed 2980when either the upper or lower (or both) bound of a column was changed. 2981The untrail data contains the column's number and the original 2982bounds. 2983This function is not time-stamped because each column can only 2984change 2985type at most twice (C -> I -> B).</div> 2986<ul> 2987 <li style="font-weight: bold;">_cpx_reset_col_type <span 2988 style="font-weight: normal;">*time-stamped*</span></li> 2989</ul> 2990<div style="margin-left: 40px;">change a column back to its original 2991type. 2992Trailed when a column type is changed in p_cpx_change_col_type. The 2993untrail 2994data contains the column's number and the original type.</div> 2995<ul> 2996 <li style="font-weight: bold;">_cpx_del_rowcols <span 2997 style="font-weight: normal;">*time-stamped*</span></li> 2998</ul> 2999<div style="margin-left: 40px;">delete added rows (and any added 3000columns) 3001from a problem matrix. Rows are always added incrementally, so only one 3002delete is needed per choice-point even if there were many row 3003additions. 3004The same time-stamp as _cpx_reset_col_type is used, as there is no need 3005to reset the types of columns that are deleted. Trailed during 3006p_cpx_flush_new_rows. 3007Untrail data contains the old column and row sizes.</div> 3008<br> 3009 3010<h3>Multiple handles</h3> 3011While Cplex has always had problem handles, these need to be simulated 3012for older (pres-13) versions of Xpress. We will not disucss 3013this further as more recent versions of Xpress also have problem 3014handles. 3015<h3>Memory allocation</h3> 3016Memory in eplex.c is allocated through the macros Malloc(), Realloc() 3017and 3018Free(), which are normally set to the standard C library's allocation 3019functions, 3020but can be redefined for debugging purposes. Note that we have no 3021control 3022over the memory allocation of the actual solver library! 3023<h3>Buffer Arrays<br> 3024</h3> 3025<p> 3026Various buffer arrays (defined as part of the solver handle) are 3027used to store the problem at the C level before the data is passed to 3028the 3029external solver. These arrays are show schematically below. 3030The arrays are used for the initial matrix (shown in green), and for 3031later 3032additions of rows and columns (shown in yellow). The name of the 3033array is shown in brackets. 3034<br> 3035 3036<br> 3037<table style="text-align: left; width: 100%;" border="0" cellpadding="2" 3038 cellspacing="2"> 3039 <caption> <br> 3040 </caption><tbody> 3041 </tbody><tbody> 3042 </tbody> <tbody> 3043 <tr> 3044 <td style="vertical-align: top;"> <br> 3045 <table style="text-align: left; width: 100%; height: 100%;" 3046 border="1" cellpadding="2" cellspacing="2"> 3047 <caption> <br> 3048 </caption><tbody> 3049 </tbody><tbody> 3050 </tbody> <tbody> 3051 <tr> 3052 <td 3053 style="vertical-align: top; background-color: rgb(102, 255, 153);">objective 3054coeffs (objx)</td> 3055 </tr> 3056 </tbody> 3057 </table> 3058 </td> 3059 <td style="vertical-align: top;"><br> 3060 </td> 3061 <td style="vertical-align: top;"> <br> 3062 <table style="text-align: left; width: 100%;" border="1" 3063 cellpadding="2" cellspacing="2"> 3064 <caption> <br> 3065 </caption><tbody> 3066 </tbody><tbody> 3067 </tbody> <tbody> 3068 <tr> 3069 <td 3070 style="vertical-align: top; background-color: rgb(255, 255, 204);">(objx)</td> 3071 </tr> 3072 </tbody> 3073 </table> 3074 </td> 3075 <td style="vertical-align: top;"><br> 3076 </td> 3077 <td style="vertical-align: top;"><br> 3078 </td> 3079 <td style="vertical-align: top;"><br> 3080 </td> 3081 <td style="vertical-align: top;"><br> 3082 </td> 3083 </tr> 3084 <tr> 3085 <td style="vertical-align: top;"> <br> 3086 <table style="text-align: left; width: 100%;" border="1" 3087 cellpadding="2" cellspacing="2"> 3088 <caption> <br> 3089 </caption><tbody> 3090 </tbody><tbody> 3091 </tbody> <tbody> 3092 <tr> 3093 <td 3094 style="vertical-align: top; background-color: rgb(102, 255, 153);">col 3095upper bounds (bdu)</td> 3096 </tr> 3097 </tbody> 3098 </table> 3099 </td> 3100 <td style="vertical-align: top;"><br> 3101 </td> 3102 <td style="vertical-align: top;"> <br> 3103 <table style="text-align: left; width: 100%;" border="1" 3104 cellpadding="2" cellspacing="2"> 3105 <caption> <br> 3106 </caption><tbody> 3107 </tbody><tbody> 3108 </tbody> <tbody> 3109 <tr> 3110 <td 3111 style="vertical-align: top; background-color: rgb(255, 255, 204);">(bdu)</td> 3112 </tr> 3113 </tbody> 3114 </table> 3115 </td> 3116 <td style="vertical-align: top;"><br> 3117 </td> 3118 <td style="vertical-align: top;"><br> 3119 </td> 3120 <td style="vertical-align: top;"><br> 3121 </td> 3122 </tr> 3123 <tr> 3124 <td style="vertical-align: top;"> <br> 3125 <table style="text-align: left; width: 100%;" border="1" 3126 cellpadding="2" cellspacing="2"> 3127 <caption> <br> 3128 </caption><tbody> 3129 </tbody><tbody> 3130 </tbody> <tbody> 3131 <tr> 3132 <td 3133 style="vertical-align: top; background-color: rgb(51, 255, 51);">col 3134lower bounds (bdl)</td> 3135 </tr> 3136 </tbody> 3137 </table> 3138 </td> 3139 <td style="vertical-align: top;"><br> 3140 </td> 3141 <td style="vertical-align: top;"> <br> 3142 <table style="text-align: left; width: 100%;" border="1" 3143 cellpadding="2" cellspacing="2"> 3144 <caption> <br> 3145 </caption><tbody> 3146 </tbody><tbody> 3147 </tbody> <tbody> 3148 <tr> 3149 <td 3150 style="vertical-align: top; background-color: rgb(255, 255, 204);">(bdl)</td> 3151 </tr> 3152 </tbody> 3153 </table> 3154 </td> 3155 <td style="vertical-align: top;"><br> 3156 </td> 3157 <td style="vertical-align: top;"><br> 3158 </td> 3159 <td style="vertical-align: top;"><br> 3160 </td> 3161 <td style="vertical-align: top;"><br> 3162 </td> 3163 </tr> 3164 <tr> 3165 <td colspan="7" style="vertical-align: top;"><br> 3166 </td> 3167 </tr> 3168 <tr> 3169 <td style="vertical-align: top;"> <br> 3170 <table style="text-align: left; width: 100%; height: 100%;" 3171 border="1" cellpadding="2" cellspacing="2"> 3172 <caption> <br> 3173 </caption><tbody> 3174 </tbody><tbody> 3175 </tbody> <tbody> 3176 <tr> 3177 <td style="background-color: rgb(51, 255, 51);">Matrix 3178 <br> 3179(matind, matval <br> 3180 matbeg, matcnt)</td> 3181 </tr> 3182 </tbody> 3183 </table> 3184 </td> 3185 <td style="vertical-align: top;"><br> 3186 </td> 3187 <td style="vertical-align: top;"> <br> 3188 <table style="text-align: left; width: 100%;" border="1" 3189 cellpadding="2" cellspacing="2"> 3190 <caption> <br> 3191 </caption><tbody> 3192 </tbody><tbody> 3193 </tbody> <tbody> 3194 <tr> 3195 <td 3196 style="vertical-align: top; background-color: rgb(255, 255, 204);">Added 3197cols <br> 3198(matind,matval <br> 3199 matbeg)</td> 3200 </tr> 3201 </tbody> 3202 </table> 3203 </td> 3204 <td style="vertical-align: top;"><br> 3205 </td> 3206 <td style="vertical-align: top;"> <br> 3207 <table style="text-align: left; width: 100%;" border="1" 3208 cellpadding="2" cellspacing="2"> 3209 <caption> <br> 3210 </caption><tbody> 3211 </tbody><tbody> 3212 </tbody> <tbody> 3213 <tr> 3214 <td 3215 style="vertical-align: top; background-color: rgb(51, 255, 51);">sense 3216 <br> 3217(senx) 3218 <p> </p> 3219 </td> 3220 </tr> 3221 </tbody> 3222 </table> 3223 </td> 3224 <td style="vertical-align: top;"><br> 3225 </td> 3226 <td style="vertical-align: top;"> <br> 3227 <table style="text-align: left; width: 100%;" border="1" 3228 cellpadding="2" cellspacing="2"> 3229 <caption> <br> 3230 </caption><tbody> 3231 </tbody><tbody> 3232 </tbody> <tbody> 3233 <tr> 3234 <td 3235 style="vertical-align: top; background-color: rgb(51, 255, 51);">rhs 3236 <br> 3237(rhs) 3238 <p> </p> 3239 </td> 3240 </tr> 3241 </tbody> 3242 </table> 3243 </td> 3244 </tr> 3245 <tr> 3246 <td colspan="7" style="vertical-align: top;"><br> 3247 </td> 3248 </tr> 3249 <tr> 3250 <td colspan="3" style="vertical-align: top;"> <br> 3251 <table style="text-align: left; width: 100%;" border="1" 3252 cellpadding="2" cellspacing="2"> 3253 <caption> <br> 3254 </caption><tbody> 3255 </tbody><tbody> 3256 </tbody> <tbody> 3257 <tr> 3258 <td 3259 style="vertical-align: top; background-color: rgb(255, 255, 204);">Added 3260rows <br> 3261(rmatind, rmatval, rmatbeg)</td> 3262 </tr> 3263 </tbody> 3264 </table> 3265 </td> 3266 <td style="vertical-align: top;"><br> 3267 </td> 3268 <td style="vertical-align: top;"> <br> 3269 <table style="text-align: left; width: 100%;" border="1" 3270 cellpadding="2" cellspacing="2"> 3271 <caption> <br> 3272 </caption><tbody> 3273 </tbody><tbody> 3274 </tbody> <tbody> 3275 <tr> 3276 <td 3277 style="vertical-align: top; background-color: rgb(255, 255, 204);">(rsense)</td> 3278 </tr> 3279 </tbody> 3280 </table> 3281 </td> 3282 <td style="vertical-align: top;"><br> 3283 </td> 3284 <td style="vertical-align: top;"> <br> 3285 <table style="text-align: left; width: 100%;" border="1" 3286 cellpadding="2" cellspacing="2"> 3287 <caption> <br> 3288 </caption><tbody> 3289 </tbody><tbody> 3290 </tbody> <tbody> 3291 <tr> 3292 <td 3293 style="vertical-align: top; background-color: rgb(255, 255, 204);">(rhs)</td> 3294 </tr> 3295 </tbody> 3296 </table> 3297 </td> 3298 </tr> 3299 </tbody> 3300</table> 3301</p> 3302<h3><a name="cutpoolc"></a>Cutpool Constraints<br> 3303</h3> 3304<p>The cutpool constraints are stored in the row-wise representation 3305used for CPLEX/XPRESS at 3306the C-level. They are maintained in the problem descriptor, and 3307their names are:</p> 3308<ul> 3309 <li>cp_rmatind2, cp_rmapval2, cp_rmapbeg2 - coefficients for 3310the 3311rows</li> 3312 <li>cp_rhsx2, cp_senx2 - RHS and sense for the rows</li> 3313 <li>cp_nr2 - the next row index (int)</li> 3314 <li>cp_nr_sz2 - size of cutpool row arrays (int)<br> 3315 </li> 3316 <li>cp_nnz2 - the next nonzero index (int)</li> 3317 <li>cp_nz_sz2 - size of cutpool nz array (int)<br> 3318 </li> 3319</ul> 3320In addition, the conditional cut pool matrix has extra structures to 3321manage 3322the named groups and default status: 3323<ul> 3324 <li>cp_active2 - the active state for each row (array of char, size 3325cp_nr_sz2)<br> 3326 </li> 3327 <li>cp_initial_add2 - the add_initially status for each row (array of 3328char, size cp_nr_sz2)<br> 3329 </li> 3330 <li>cp_npools2 - the number of used name groups (int)<br> 3331 </li> 3332 <li>cp_pools2 - an array of integer arrays, each integer array 3333represent 3334one named group. The entry in each array represents the raw index (into 3335cp_rampbeg2) for one constraint in the group.</li> 3336 <li>cp_names2 - an array of strings. Each string is the name for the 3337group. 3338This is used to map the names into the index used in cp_pools2. The 3339first 3340entry (index 0) is treated specially, for the default group, which use 3341the nil atom ([]), which is detected specially and not matched with the 3342names.</li> 3343</ul> 3344<h4><a name="cpsupportcplex_opt"></a>Support for cutpool constraints in 3345p_cpx_optimiseI</h4> 3346In cplex_optimise(), if there are cutpool constraints (lpd->cp_nr2 3347> 0), then:<br> 3348<br> 3349 1. Any active cutpool constraints with the add_initially 3350status are added to the problem matrix by <a 3351 href="#_setup_initial_cp_constraintslp_desc_">_setup_initial_cp_constraints().</a> 3352This is done at the start of cplex_optimise()<br> 3353 2. The solver is invoked inside a loop, and after 3354determining the status of the solution and solution state if available:<br> 3355<ul> 3356 <li> if there is a solution state (optimal or suboptimal), then 3357the active cutpool constraints not yet added to the problem are checked 3358to see if they are violated. This is done with calls to <a 3359 href="#cstr_state">_cstr_state()</a>. Any violated constraints are 3360added to the problem. </li> 3361 <li> if there is no solution state, but the problem status is 3362unknown or unbounded, then all unadded active cutpool constraints are 3363added to the problem. _cstr_state() calls are also made with 3364add_cp_cstr = 2, these are `dummy' calls that always cause the 3365constraints to be added.</li> 3366</ul> 3367 3. If any cutpool constraints have been added to the 3368problem, invoke the solver again (step 2).<br> 3369<br> 3370The violation check is done by looping through the cp_unadded array, 3371which hold information on the unadded cutpool constraints. This array 3372is initialised by the call to _setup_initial_cp_constraints() so that 3373initially the successive elements contains the raw index of the unadded 3374constraints, e.g. if there are 6 cutpool constraints, and constraints 0 3375and 2 are added initially to the matrix, then cp_unadded will be 3376initialised to {1,3,4,5}, i.e. constraints 1,3,4 and 5 are not yet 3377added.<br> 3378<br> 3379On looping through the cp_unadded array, _cstr_state() is called to 3380check if the constraint is violated. If it is, it is added to the 3381problem matrix. The cp_unadded array is modified to reflect this change 3382by allowing the next cycle of solver invocation/checking constraints to 3383skip over these added constraints. This is done by changing the first 3384added constraint in a consecutive block of added constraints to a 3385negative number representing the displacement to the next unadded 3386constraint, e.g. for the above example, if constraints 2 and 3 are 3387added, then the cp_unadded array is changed to {1,-2,_,5}, i.e. 3388constraints 1 and 5 are still unadded, but the -2 in cp_unadded[1] will 3389cause the check to skip the block of added constraints from this cycle. 3390Note that because the block is skipped, the value for cp_unadded[2] is 3391no longer important (so it is represented by _).<br> 3392<br> 3393<br> 3394<p>The cutpool constraints are added to a problem initially by calling: 3395</p> 3396<h4><a name="_setup_initial_cp_constraintslp_desc_"></a><a 3397 name="condcpsetupcall"></a>_setup_initial_cp_constraints(lp_desc * 3398lpd, 3399int add_all, int * unadded_cntp, int * cp_unadded, int * cp_map2)</h4> 3400set up and add the initial cutpool constraints to the problem 3401represented 3402by the problem descriptor lpd. If add_all is 0, then the active cutpool 3403constraints with the add_initially status set (in cp_initial_add2 3404array) are added to the problem. If add_all is 1, then all active 3405cutpool constraints are added to the problem.<br> 3406<br> 3407unadded_cntp is a pointer to the counter of number of unadded active 3408cutpool constraints constraints. This is set by the procedure.<br> 3409<br> 3410cp_unadded is an array of the indexes of the unadded constraints. 3411This must be created before calling the procedure, and is currently 3412conservatively given the size of the number of cutpool constraints. <br> 3413<br> 3414cp_map2 is an array mapping all the cutpool constraints to how they are 3415used. This is eventually returned to the user by p_cpx_optimise().<br> 3416<br> 3417<p>This routine is called in p_cpx_optimise (add_all=0), and 3418p_cpx_lpwrite (add_all=1).<br> 3419</p> 3420<h4><a name="cstr_state"></a>_cstr_state(lp_desc * lpd, int nrow, char 3421add_cp_cstr, double * sols)</h4> 3422check and return the state of the cutpool constraint with raw index 3423nrow (row nrow in the cutpool matrix). The return states are:<br> 3424<br> 3425<div style="margin-left: 40px;">CSTR_STATE_VIOLATED - constraint 3426is violated<br> 3427CSTR_STATE_BINDING - constraint is satisfied and binding <br> 3428CSTR_STATE_SAT - constraint is satisfied but not binding<br> 3429CSTR_STATE_INVALID - error with constraint (e.g. a unsupported 3430constraint type)<br> 3431<br> 3432</div> 3433sols is the solution values array for the last solved problem. The 3434solution values are used with the column coefficients of the 3435constraint to calculate the lhs , and this is compared with the 3436rhs to see if the constraint is violated/binding/satisfied.<br> 3437<br> 3438A binding constraint is a constraint which is satisfied, and the lhs 3439and rhs values are equal within the feasibility tolerance -- the 3440external solver's feasibility tolerance parameter value is used for 3441this test. <br> 3442<br> 3443add_cp_cstr is a state variable used by the parent procedure 3444p_cpx_optimise(). In p_cpx_optimise() it specifies if adding 3445cutpool constraint should be considered for this external solver 3446invocation or not (== 0 for not adding cutpool constraint, > 0 for 3447adding cutpool constraint). _cstr_state() should only be called with 3448add_cp_cstr > 0. Normally, add_cp_cstr == 1, and the state checking 3449is done. However, if the last solved state is unbounded or unknown, 3450_cstr_state() is called with add_cp_cstr == 2, and no checking is done 3451in this case, and DESCR_STATE_VIOLATED is returned to force the adding 3452of the constraint. This is done to allow the same code to be used for 3453both both the normal and the unbonded/unknown case for checking and 3454adding constraints.<br> 3455<br> 3456The following routines are called from the ECLiPSe level: 3457<ul> 3458 <li> <b>cplex_get_cutpool_size(+CPH, -NRows, -NNzs), 3459p_get_cutpool_size</b></li> 3460 <br> 3461returns the size (number of rows, number of non-zeros) of the cutpool 3462CType. This is called before constraints 3463are added to the cutpool, so that the original <br> 3464cutpool state can be restored if failure occurs while the constraints 3465are added (e.g. because of an invalid constraint). The restoration is 3466done 3467by calling cplex_reset_cutpool_size. <br> 3468 <li><b>cplex_reset_cutpool_size(+CPH, +NRows, +NNzs), 3469p_reset_cutpool_size</b></li> 3470 <br> 3471resets the cutpool to the size in NRows and NNzs. <br> 3472 <li><b>cplex_set_cpcstr_cond(+CPH,+RawIdx, +OType,+ActVal), 3473p_set_cpcstr_defaults</b></li> 3474 <br> 3475sets the cutpool option OType to the value ActVal for the cutpool 3476constraint with the cutpool raw index RawIdx.<br> 3477 <br> 3478 <li> <b>cplex_init_cpcstr(+CPH, +RawIdx, +GrpIdx, +Active,+AddInit), 3479p_init_cpcstr</b></li> 3480 <br> 3481initialise the cutpool constraint specific data of a 3482new constraint with raw index RawIdx. The constraint must already have 3483been added to the cutpool. This routine add the group information 3484(adding its index to cp_pools2[GrpIdx] etc.), and sets the active and 3485add_initially status.<br> 3486 <li><b>cplex_get_named_cp_index(+CPH, +Name, +OptSet, -GrpIdx), 3487p_cpx_get_named_cp_index</b></li> 3488 <br> 3489get the GrpIdx for a named group with name Name. This creates 3490and set a new named group if OptSet is 1. Otherwise, failure 3491occurs 3492if Name does not exist. The default group ([]) is treated specially, 3493and 3494is always created if it does not already exist. It is also tested for 3495with 3496test for nil atom rather than a name match. The default group is only 3497created 3498when needed to avoid the overhead when conditional cut pools are not 3499used. <br> 3500 <li><b>cplex_get_named_cpcstr_indices(+CPH, +GrpIdx, -RawIdxs), 3501p_cpx_get_named_cpcstr_indices</b></li> 3502 <br> 3503returns all the raw indexes for the named group represented by GrpIdx. <br> 3504 3505</ul> 3506<h3>COIN/OSI solvers</h3> 3507<span style="font-family: times new roman,times,serif;">The COIN/OSI 3508interface is organised as follow:</span><br 3509 style="font-family: times new roman,times,serif;"> 3510<span style="font-family: monospace;"><br> 3511 3512_______________________________<br> 3513_______________ | 3514____________|______ 3515________ V<br> 3516| 3517| | 3518| 3519| | | 3520--> CBC<br> 3521| seplex.c | --|-> | 3522coinplex.cpp | --> | OSI | 3523--> CLP<br> 3524|______________| | 3525|__________________| |_______| 3526--> SYMPHONY<br> 3527 3528 | 3529 3530--> ,,,<br> 3531 3532C 3533C++</span><br> 3534<br> 3535coinplex.cpp effectively provides the solver API as used previously: 3536where eplex call XPRESS/CPLEX C API routines, it calls routines in 3537coinplex instead. The code in coinplex.cpp then calls OSI, which can be 3538interfaced to different solvers, or combination of solvers (such as CLP 3539as the linear solver, and CBC for MIP solver). The normal usage is<br> 3540to use the appropriate OsiXxxSolverInterface, where Xxx is the solver 3541specific interface,<br> 3542and coinplex.cpp is compiled with <span style="font-family: monospace;">-DCOIN_USE_XXX</span> 3543flag, with<span style="font-family: monospace;"> #ifdef COIN_USE_XXX </span><span 3544 style="font-family: times new roman,times,serif;">macros</span><span 3545 style="font-family: monospace;"><br> 3546</span><span style="font-family: times new roman,times,serif;">to 3547specify any solver specific code.<br> 3548<br> 3549In the case of solver specific code, coinplex would make direct calls 3550to the solver, e.g. CBC as shown in the figure above. Solver 3551specific code is needed because the required feature is not supported 3552by the OSI API (e.g. timeouts), or the specific solver provide better 3553support for the feature (e.g. branch and bound in CBC).<br> 3554</span><span style="font-family: monospace;"></span><br> 3555To maximise the amount of shared code, the routines defined in the 3556coinplex API mimic those in CPLEX/XPRESS API as much as possible, so 3557that the same code can be used for the various solvers, with macros 3558mapping the CPLEX or XPRESS routine names to coinplex equivalent.<br> 3559<br> 3560The coinplex.cpp routines that are to be called by seplex.c are 3561listed <a href="#coinplexapi">here</a>. To define a new call for 3562the API:<br> 3563<br> 3564in seplex.c/h:<br> 3565<ul> 3566 <li>declare the call (with prefix "<span 3567 style="font-family: monospace;">coin_</span>") with the rest of the 3568coinplex procedure declarations, with the types for the arguments, in 3569seplex.h. Data 3570contructs which are C++ specific (such as the <span 3571 style="font-family: monospace;">COINprob *</span>) should be passed as 3572void pointers (and in C++ used as pointers to the data contructs), and 3573should not be used at all in seplex.c.<br> 3574 </li> 3575 <li>if the call is used within code that is shared with CPLEX/XPRESS, 3576the macro transformation of the code into the coinplex procedure should 3577be defined (with the rest of the COIN-specific macro transformations)</li> 3578</ul> 3579in coinplex.cpp:<br> 3580<ul> 3581 <li>write the code (in C++) for the procedure. The arguments for the 3582procedure must be compatible with its declaration in seplex.c. <br> 3583 </li> 3584 <li>the procedure should be prefixed by the `<span 3585 style="font-family: monospace;">extern "C"</span>' declaration, 3586to make it visible externally.<br> 3587 </li> 3588</ul> 3589The C to coinplex API in seplex.h is only needed by the C code, and is 3590compiled with the <span style="font-family: monospace;">-DC_TO_COIN </span>flag 3591for C code (seplex.c, logged code), and not for C++ code (coinplex.cpp),<br> 3592<br> 3593The code in seplex.c should be generic for OSI, i.e. not specific to 3594any solver. In coinplex.cpp, solver specific code can be given, but no 3595ECLiPSe specific code -- so that coinplex.cpp can be sent as part of 3596the <a href="logging">logged code</a> for reporting bugs (some ECLiPSe 3597specific code for I/O was needed so that messages from OSI can be 3598sent to ECLiPSe steams, but these are in a NOECLIPSE macro that can be 3599defined to exclude them).<br> 3600<span style="font-family: monospace;"><br> 3601</span> 3602<h4>Problem descriptor</h4> 3603The C level descriptor (lp_desc) contains a field that points to the 3604solver problem pointer, COINprob* in the case of COIN/OSI. This is 3605defined as a void* in C, but is defined as a structure in coinplex.cpp 3606as follow:<br> 3607<br> 3608struct {<br> 3609 OsiXxxSolverInterface * Solver;<br> 3610 char** varnames; /* for names of variables (columns) 3611*/<br> 3612 unsigned int vnsize; /* number of variable names */<br> 3613 char notfirst; /* has problem been solved? */<br> 3614 3615....... 3616/* solver specific fields */<br> 3617}<br> 3618<br> 3619notfirst is required to determine if OSI's initialSolve() or resolve() 3620should be called to solve the linear problem. <br> 3621<br> 3622varnames is used to store the variable names (if passed by eplex) that 3623are printed when the problem is written out in LP or MPS format). 3624vnsize is 0 if no names have been passed from the ECLIpSe level.<br> 3625<br> 3626For example, for the CLP/CBC solver, there are the following fields:<br> 3627<br> 3628 char mipIsShared; /* 1 if shared with Solver, 0 if 3629copied */<br> 3630 CbcModel* mipmodel; /* pointer to the MIP model */<br> 3631 ClpInterior* interiormodel; /* pointer to the 3632interior point model */<br> 3633 double 3634timeout; 3635/* timeout value */<br> 3636<br> 3637This contain information not supported by OSI (such as the timeout 3638value), and specific features required, such as the CbcModel pointer 3639for use by CBC.<br> 3640<br> 3641Note the combination of CLP/CBC solver is done using the 3642OsiClpSolverInterface, and the CBC MIP solver is accessed via CbcModel 3643and CBC API, instead of using the OsiCbcSolverInterface, because this 3644is the recommended method from John Forrest, who is the main person 3645behind both CLP and CBC. <br> 3646<br> 3647<h4>Solver specific Information</h4> 3648As much as possible, the external solver is accessed via OSI in <span 3649 style="font-family: monospace;">coinplex.cpp</span>, so that common 3650code could be used for the different solvers. However, some features 3651are not available or poorly supported by OSI, and specific solver 3652support for these features should be provided if possible:<br> 3653<ul> 3654 <li>OSI does not provide much control over MIP solving. The 3655default <span style="font-family: monospace;"> 3656coin_branchAndBound() </span>call OSI's <span 3657 style="font-family: monospace;">branchAndBound()</span>. Solver 3658specific <span style="font-family: monospace;">coin_branchAndBound() </span>can 3659provide more control over the MIP solving. <br> 3660 </li> 3661 <li>OSI does not support the setting of solving methods beyond if a 3662primal or dual method should be used. <span 3663 style="font-family: monospace;">coin_solveLinear() </span>allow 3664solver specific solving methods (such as interior point methods) to be 3665used.</li> 3666 <li>Timeouts are not supported. <span style="font-family: monospace;">coin_set_timeout() 3667 </span>allows solver specific methods of setting timeout.</li> 3668 <li>OSI is not very good at determining semi-fail or semi-success 3669state when a problem solve is aborted, and the unknown result 3670status have to be returned. Solver specific code can be 3671added to <span style="font-family: monospace;">coin_get_result_state() </span> 3672to better determine the result status.</li> 3673 <li>Obtaining best and worst objective value bounds is also 3674very solver specific. The default non-solver specific return value is 3675the `infinity' value of the right sign. <br> 3676 </li> 3677 <li>OSI supports only a small set of solver parameters. Solver 3678specific parameters are supported via <span 3679 style="font-family: monospace;">coin_set/get_*param() </span>routines. 3680See <a href="#osiparams">here for more detail.<br> 3681 </a></li> 3682 <li>SOS (Special Order Sets) are not supported. <span 3683 style="font-family: monospace;">coin_load_sos()</span> allows solver 3684specific support for SOS.<br> 3685 </li> 3686</ul> 3687<br> 3688Most of the solver specific code are implemented for osI_clpcbc 3689currently, and there are also some code to work around some features of 3690Cbc:<br> 3691<ul> 3692 <li>mipmodel is a ClpModel* in COINprob for supporting specialised 3693MIP code in <span style="font-family: monospace;">coin_branchAndBound().</span> 3694The code is largely taken from sample2 example driver for Cbc<br> 3695 </li> 3696 <li>Cbc fixes bounds of some variables to their potential solution 3697value during MIP presolve and solve. These bounds have to be undone 3698after the probelm solve to allow the problem to be correctly resolved. 3699This is done by copying the bounds before doing the presolve, and 3700restore these bounds before exiting <span 3701 style="font-family: monospace;">coin_branchAndBound()</span>.<br> 3702 </li> 3703 <li>the method CbcModel <span style="font-family: monospace;"> 3704isContinuousUnbounded()</span> method is used in <span 3705 style="font-family: monospace;">coin_get_result_state()</span>, this 3706method is currently (Nov 2006) only available on the trunk and 3707development branches of Cbc, and not in the stable branch. </li> 3708 <li><br> 3709 </li> 3710</ul> 3711<h4><a name="coinplexapi"></a>API between seplex.c and coinplex.cpp</h4> 3712<br> 3713The following procedures are defined:<br> 3714<br> 3715<ul style="font-weight: bold;"> 3716 <li> 3717 <h4>int coin_get_objsen(COINprob * lp)</h4> 3718 </li> 3719</ul> 3720<div style="margin-left: 40px;">return the sense (SENSE_MIN or 3721SENSE_MAX) of the objective function for the problem<br> 3722</div> 3723<ul style="font-weight: bold;"> 3724 <li> 3725 <h4>int coin_get_numcols(COINprob* lp)</h4> 3726 </li> 3727</ul> 3728<div style="margin-left: 40px;">returns the number of columns for the 3729problem<br> 3730</div> 3731<ul style="font-weight: bold;"> 3732 <li> 3733 <h4>int coin_get_numrows(COINprob* lp)</h4> 3734 </li> 3735</ul> 3736<div style="margin-left: 40px;">returns the number of rows for the 3737problem<br> 3738</div> 3739<ul style="font-weight: bold;"> 3740 <li> 3741 <h4>int coin_get_probtype(COINprob* lp)</h4> 3742 </li> 3743</ul> 3744<div style="margin-left: 40px;">returns the problem type of the problem<br> 3745</div> 3746<ul style="font-weight: bold;"> 3747 <li> 3748 <h4>int coin_getrhs(COINprob * lp, double *rhs, int start, int end)</h4> 3749 </li> 3750</ul> 3751<div style="margin-left: 40px;">returns in rhs the right hand side 3752coeff. of rows from start to end. rhs should be pointing at a double 3753array of at least end-start elements. Returns -1 if error<br> 3754</div> 3755<ul style="font-weight: bold;"> 3756 <li> 3757 <h4>int coin_getrowsense(COINprob * lp, char *rsense, int start, 3758int end)</h4> 3759 </li> 3760</ul> 3761<div style="margin-left: 40px;">returns in rsense the row senses for 3762rows from start to end. rsense should be pointing at a char array of at 3763least end-start elements. Returns -1 if error<br> 3764</div> 3765<ul style="font-weight: bold;"> 3766 <li> 3767 <h4>int coin_getlb(COINprob * lp, double *lb, int start, int end)</h4> 3768 </li> 3769</ul> 3770<div style="margin-left: 40px;">returns in lb the lower bounds of 3771columns from start to end. lb should be pointing at a double array of 3772at least end-start elements. Returns -1 if error<br> 3773</div> 3774<ul style="font-weight: bold;"> 3775 <li> 3776 <h4>int coin_getub(COINprob * lp, double *ub, int start, int end)</h4> 3777 </li> 3778</ul> 3779<div style="margin-left: 40px;">returns in ub the upper bounds of 3780columns from start to end. ub should be pointing at a double array of 3781at least end-start elements. Returns -1 if error<br> 3782</div> 3783<div style="margin-left: 40px;"></div> 3784<ul style="font-weight: bold;"> 3785 <li> 3786 <h4>int coin_getcoltype(COINprob * lp, char *ctype, int start, int 3787end)</h4> 3788 </li> 3789</ul> 3790<h4 style="margin-left: 40px; font-weight: normal;">returns in ctype 3791the types of 3792columns from start to end. ctype should be pointing at a char array of 3793at least end-start elements. Returns -1 if error<br> 3794</h4> 3795<ul style="font-weight: bold;"> 3796 <li> 3797 <h4>int coin_chgcoltype(COINprob * lp, int cnt, int *idxs, char 3798*ctype)</h4> 3799 </li> 3800</ul> 3801<div style="margin-left: 40px;">change the column types for cnt columns 3802specified in idxs to the types given in ctype. idxs and ctype are 3803arrays of at least cnt elements. Returns -1 if error<br> 3804</div> 3805<ul style="font-weight: bold;"> 3806 <li> 3807 <h4>int coin_chgbds(COINprob * lp, int cnt, int * idxs, char * lu, 3808double *bd)</h4> 3809 </li> 3810</ul> 3811<div style="margin-left: 40px;">change the bounds for cnt columns 3812specified in idxs to the bounds given in bd, with lu specifying which 3813bound to change. idxs, lu and bd are 3814arrays of at least cnt elements. Returns -1 if error<br> 3815</div> 3816<ul style="font-weight: bold;"> 3817 <li> 3818 <h4>int coin_loadbasis(COINprob * lp, int *cbase, int *rbase)</h4> 3819 </li> 3820</ul> 3821<div style="margin-left: 40px;">loads the column (cbase) and row 3822(rbase) basis array into the problem if supported. cbase and rbase 3823should be previously obtained with coin_getbasis()<br> 3824</div> 3825<ul style="font-weight: bold;"> 3826 <li> 3827 <h4>int coin_getbasis(COINprob * lp, int *cbase, int *rbase)</h4> 3828 </li> 3829</ul> 3830<div style="margin-left: 40px;">get the current basis. cbase is the 3831column basis, rbase is the row basis if supported<br> 3832</div> 3833<ul style="font-weight: bold;"> 3834 <li> 3835 <h4>int coin_get_lpobjval(COINprob * lp, double * objvalp)</h4> 3836 </li> 3837</ul> 3838<div style="margin-left: 40px;">returns the current linear objective 3839value for the the problem in objvallp if supported. Otherwise the 3840current objective value is reutrned instead.<br> 3841</div> 3842<ul style="font-weight: bold;"> 3843 <li> 3844 <h4>int coin_get_mipobjval(COINprob * lp, double * objvalp)</h4> 3845 </li> 3846</ul> 3847<div style="margin-left: 40px;">returns the MIP objective value for the 3848most recent solution to the problem.<br> 3849</div> 3850<ul style="font-weight: bold;"> 3851 <li> 3852 <h4>int coin_get_bestmipbound(COINprob * lp, double * bound)</h4> 3853 </li> 3854</ul> 3855<div style="margin-left: 40px;">returns in bound the best bound on the 3856optimal MIP objective value, generally the best relaxed objective value 3857in an open node in the search tree. If not supported by the solver, 3858infinity of the right sign is returned.<br> 3859</div> 3860<ul style="font-weight: bold;"> 3861 <li> 3862 <h4>int coin_get_objcoeffs(COINprob * lp, double *objc, int start, 3863int end)</h4> 3864 </li> 3865</ul> 3866<div style="margin-left: 40px;">returns the objective coeffs in objc 3867for columns from start to end. objc should point to a double array of 3868at least end-start elements. Returns -1 if error<br> 3869</div> 3870<ul style="font-weight: bold;"> 3871 <li> 3872 <h4>int coin_chg_objcoeffs(COINprob * lp, int cnt, int * idxs, 3873double * values)</h4> 3874 </li> 3875</ul> 3876<div style="margin-left: 40px;">changes the objective coeffs for cnt 3877columns with indices specified in idxs to values. idxs and values 3878should point at arrays that have at least cnt elements. Returns -1 if 3879error<br> 3880</div> 3881<ul style="font-weight: bold;"> 3882 <li> 3883 <h4>int coin_get_order(COINprob * lp, int cnt, int * idxs, int * 3884prio, int * direction)</h4> 3885 </li> 3886</ul> 3887<div style="margin-left: 40px;">currently unimplemented. For support of 3888cplex_loadorder/3.<br> 3889</div> 3890<ul style="font-weight: bold;"> 3891 <li> 3892 <h4>int coin_chgqobj(COINprob * lp, int i, int j, double value)</h4> 3893 </li> 3894</ul> 3895<div style="margin-left: 40px;">currently unimplemented. For changing 3896an quadratic objective coefficient.<br> 3897</div> 3898<ul style="font-weight: bold;"> 3899 <li> 3900 <h4>int coin_chgrhs(COINprob * lp, int cnt, int * idxs, double * 3901values)</h4> 3902 </li> 3903</ul> 3904<div style="margin-left: 40px;">changes the right hand side coeffs for 3905cnt rows with indices specified in idxs to values. idxs and 3906values should point at arrays of at least cnt size. Returns -1 if error<br> 3907</div> 3908<ul style="font-weight: bold;"> 3909 <li> 3910 <h4>int coin_loadprob(COINprob* lp, int mac, int mar, int objsen, 3911double* objx, double* rhsx, char* senx, int * matbeg, int* matcnt, int* 3912matind, double* matval,double* lb, double* ub)</h4> 3913 </li> 3914</ul> 3915<div style="margin-left: 40px;">loads the column-wise specified 3916problem. In the format used by the Coin function, matbeg needs to be 3917size mac+1, because matbeg[i+i] is used to specify the end of column i. 3918This is set by coin_loadprob() from matcnt[mac-1]+matbeg[mac-1], 3919so it does not need to be calculated in seplex.c, but the space for 3920matbeg[mac] must be allocated. <br> 3921</div> 3922<ul style="font-weight: bold;"> 3923 <li> 3924 <h4>int coin_setcoltype(COINprob* lp, char *ctype)</h4> 3925 </li> 3926</ul> 3927<div style="margin-left: 40px;">sets the column types for all columns 3928in the problem. ctype should be a char array of the same size as the 3929number of columns. Returns -1 if error<br> 3930</div> 3931<ul style="font-weight: bold;"> 3932 <li> 3933 <h4>int coin_addcols(COINprob* lp, int coladded, int matnz, double* 3934objx, int* matbeg, int* matind, double* matval, double* bdl, double* 3935bdu)</h4> 3936 </li> 3937</ul> 3938<div style="margin-left: 40px;">add coladded columns to the problem<br> 3939</div> 3940<ul style="font-weight: bold;"> 3941 <li> 3942 <h4>int coin_addrows(COINprob* lp, int rowadded, int nzadded, 3943double* rhsx, char* senxm int* rmatbeg, int* rmatind, double* rmatval)</h4> 3944 </li> 3945</ul> 3946<div style="margin-left: 40px;">add rowadded rows to the problem<br> 3947</div> 3948<ul style="font-weight: bold;"> 3949 <li> 3950 <h4>int coin_chgobjsen(COINprob* lp, int objsen)</h4> 3951 </li> 3952</ul> 3953<div style="margin-left: 40px;">change sense of objective function to 3954objsen (SENSE_MIN or SENSE_MAX)<br> 3955</div> 3956<ul style="font-weight: bold;"> 3957 <li> 3958 <h4>int coin_get_row(COINprob* lp, int* nnz, int* rmatind, double* 3959rmatval, int idx)</h4> 3960 </li> 3961</ul> 3962<div style="margin-left: 40px;">returns in nnz, rmatind, rmatval the 3963values for row idx. Returns -1 if error<br> 3964</div> 3965<ul style="font-weight: bold;"> 3966 <li> 3967 <h4>int coin_delrows(COINprob* lp, int ndr, int* idx)</h4> 3968 </li> 3969</ul> 3970<div style="margin-left: 40px;">delete ndr rows from the problem, with 3971indices specified in idx.<br> 3972</div> 3973<ul style="font-weight: bold;"> 3974 <li> 3975 <h4>int coin_delcols(COINprob* lp, int ndr, int* idx)</h4> 3976 </li> 3977</ul> 3978<h4 style="margin-left: 40px; font-weight: normal;">delete ndr columns 3979from the problem, with indices specified in idx.<br> 3980</h4> 3981<ul style="font-weight: bold;"> 3982 <li> 3983 <h4>int coin_get_bar_primal_objval(COINprob* lp, double* objval)</h4> 3984 </li> 3985</ul> 3986<div style="margin-left: 40px;">currently unimplemented. Returns the 3987primal objective value when using barrier<br> 3988</div> 3989<ul style="font-weight: bold;"> 3990 <li> 3991 <h4>int coin_get_bar_dual_objval(COINprob* lp, double* objval)</h4> 3992 </li> 3993</ul> 3994<div style="margin-left: 40px;">currently unimplemented. Returns the 3995dual objective value when using barrier<br> 3996</div> 3997<ul style="font-weight: bold;"> 3998 <li> 3999 <h4>state_t coin_get_result_state(lp_desc* lpd)</h4> 4000 </li> 4001</ul> 4002<div style="margin-left: 40px;">returns the result state for the most 4003recent optimisation<br> 4004</div> 4005<ul style="font-weight: bold;"> 4006 <li> 4007 <h4>int coin_get_mipcutoff(COINprob* lp, double* bestbound)</h4> 4008 </li> 4009</ul> 4010<div style="margin-left: 40px;">returns in bestbound the cutoff if 4011supported by the solver, otheriwise infinity of the right sign is 4012returned. Function returns -1 if error.<br> 4013</div> 4014<ul style="font-weight: bold;"> 4015 <li> 4016 <h4>double coin_infinity(COINprob* lp)</h4> 4017 </li> 4018</ul> 4019<div style="margin-left: 40px;">returns the solver's value for infinity<br> 4020</div> 4021<ul style="font-weight: bold;"> 4022 <li> 4023 <h4>int coin_getdblparam(COINprob* lp, int key, double* value)</h4> 4024 </li> 4025</ul> 4026<div style="margin-left: 40px;">return the value of double OSI 4027parameter specified by key in value. <br> 4028</div> 4029<ul style="font-weight: bold;"> 4030 <li> 4031 <h4>int coin_getintparam(COINprob* lp, int key, int* value)</h4> 4032 </li> 4033</ul> 4034<div style="margin-left: 40px;">return the value of integer OSI 4035parameter specified by key in value. <br> 4036</div> 4037<ul style="font-weight: bold;"> 4038 <li> 4039 <h4>int coin_setdblparam(COINprob* lp, int key, double value)</h4> 4040 </li> 4041</ul> 4042<div style="margin-left: 40px;">set the double OSI parameter specified 4043by key to value<br> 4044</div> 4045<ul style="font-weight: bold;"> 4046 <li> 4047 <h4>int coin_setintparam(COINprob* lp, int key, int value)</h4> 4048 </li> 4049</ul> 4050<div style="margin-left: 40px;">set the integer OSI parameter specified 4051by key to value<br> 4052</div> 4053<ul style="font-weight: bold;"> 4054 <li> 4055 <h4>int coin_get_solver_dblparam(COINprob* lp, int key, double* 4056value)</h4> 4057 </li> 4058</ul> 4059<div style="margin-left: 40px;">return the value of double 4060solver-specific parameter specified by key in value. <br> 4061</div> 4062<ul style="font-weight: bold;"> 4063 <li> 4064 <h4>int coin_get_solver_intparam(COINprob* lp, int key, int* value)</h4> 4065 </li> 4066</ul> 4067<div style="margin-left: 40px;">return the value of integer 4068solver-specific parameter specified by key in value. <br> 4069</div> 4070<ul style="font-weight: bold;"> 4071 <li> 4072 <h4>int coin_set_solver_dblparam(COINprob* lp, int key, double 4073value)</h4> 4074 </li> 4075</ul> 4076<div style="margin-left: 40px;">set the double solver-specific 4077parameter specified by key to value</div> 4078<ul style="font-weight: bold;"> 4079 <li> 4080 <h4>int coin_set_solver_intparam(COINprob* lp, int key, int value)</h4> 4081 </li> 4082</ul> 4083<div style="margin-left: 40px;">set the integer solver-specific 4084parameter specified by key to value</div> 4085<ul style="font-weight: bold;"> 4086 <li> 4087 <h4>int coin_solve_problem(lp_desc* lpd, int meth, int auxmeth, int 4088node_meth, int node_auxmeth)</h4> 4089 </li> 4090</ul> 4091<div style="margin-left: 40px;">invoke the external solver to optimise 4092the problem with given methods.<br> 4093</div> 4094<ul style="font-weight: bold;"> 4095 <li> 4096 <h4>int coin_get_stats(lp_desc* lpd)</h4> 4097 </li> 4098</ul> 4099<div style="margin-left: 40px;">return the iteration count for last 4100solve<br> 4101</div> 4102<ul style="font-weight: bold;"> 4103 <li> 4104 <h4>int coin_get_soln_state(lp_desc* lpd, double* sols, double* 4105pis, double* slacks, double* djs, int* cbase, int* rbase)</h4> 4106 </li> 4107</ul> 4108<div style="margin-left: 40px;">returns the solution to the most recent 4109solve<br> 4110</div> 4111<ul style="font-weight: bold;"> 4112 <li> 4113 <h4>int coin_set_timeout(COINprob* lp, double timeout)</h4> 4114 </li> 4115</ul> 4116<div style="margin-left: 40px;">if supported by the solver, set the 4117timeout to timeout seconds. Otherwise do nothing.<br> 4118</div> 4119<ul style="font-weight: bold;"> 4120 <li> 4121 <h4>int coin_create_prob(COINprob** lp)</h4> 4122 </li> 4123</ul> 4124<div style="margin-left: 40px;">create a new COINprob handle and assign 4125a solver instance to it. <br> 4126</div> 4127<ul style="font-weight: bold;"> 4128 <li> 4129 <h4>int coin_reset_prob(lp_desc* lpd)</h4> 4130 </li> 4131</ul> 4132<div style="margin-left: 40px;">reset the problem sate so that problem 4133can be resolved [needed by CBC]<br> 4134</div> 4135<ul style="font-weight: bold;"> 4136 <li> 4137 <h4>int coin_writeprob(COINprob* lp, char* file, char* otype)</h4> 4138 </li> 4139</ul> 4140<div style="margin-left: 40px;">write out the problem in format 4141specified by otype into filename file. Note that currently COIN/OSI 4142does not support writing out of maximising problems very well - the 4143objective function's sign will be reversed and the problem written as a 4144minimsing problem, according to the documentation.<br> 4145</div> 4146<ul style="font-weight: bold;"> 4147 <li> 4148 <h4>int coin_readprob(COINprob* lp, char* file, char* otype)</h4> 4149 </li> 4150</ul> 4151<div style="margin-left: 40px;">read in the problem in format otype in 4152the file file.<br> 4153</div> 4154<ul style="font-weight: bold;"> 4155 <li> 4156 <h4>int coin_getnumnz(COINprob* lp)</h4> 4157 </li> 4158</ul> 4159<div style="margin-left: 40px;">returns the number of non-zero elements 4160in the problem<br> 4161</div> 4162<ul style="font-weight: bold;"> 4163 <li> 4164 <h4>int coin_getnumint(COINprob* lp)</h4> 4165 </li> 4166</ul> 4167<div style="margin-left: 40px;">returns the number of integer columns 4168in the problem<br> 4169</div> 4170<ul style="font-weight: bold;"> 4171 <li> 4172 <h4>int coin_get_dual_infeas(COINprob* lp, int* infeas)</h4> 4173 </li> 4174</ul> 4175<div style="margin-left: 40px;">if supported, returns the number of 4176dual infesibility for the current solution state (for Simplex solvers 4177only)<br> 4178</div> 4179<ul style="font-weight: bold;"> 4180 <li> 4181 <h4>int coin_get_primal_infeas(COINprob* lp, int* infeas)</h4> 4182 </li> 4183</ul> 4184<div style="margin-left: 40px;">if supported, returns the number of 4185primal infesibility for the current solution state (for Simplex solvers 4186only)<br> 4187</div> 4188<br> 4189<h3>Global Parameters</h3> 4190Cplex and Xpress have a large number of parameters that affect their 4191behaviour. 4192Only a few of them coincide with their meaning. We have therefore 4193decided 4194to map the parameter access one-to-one from the C level to the Eclipse 4195level. While the rest of eplex tries hard to hide all the differences 4196between 4197Cplex and Xpress, the parameter setting is the exception. 4198<br> 4199To make things worse, every new release of Cplex or Xpress comes with 4200a modified set of parameters. We have therefore introduced a fixed 4201mapping 4202from the parameter names in the solver's C interface to the (atomic) 4203parameter 4204name that is used on the Eclipse level, e.g. 4205<blockquote>Cplex's <tt>CPX_PARAM_NODELIM</tt> becomes <tt>nodelim</tt> 4206 <br> 4207Xpress's <tt>MAXNOD</tt> or <tt>N_MAXNOD</tt> becomes <tt>maxnod</tt></blockquote> 4208The mapping is defined in the file eplex_params.h, which unfortunately 4209must be updated for every new solver release. The comment at the 4210beginning 4211of the file explains how to do the job semi-automatically using editor 4212commands.<br> 4213<br> 4214<a name="osiparams"></a>Note for OSI: OSI provides only a small number 4215of parameters, whose 4216name starts with Osi. Similar mapping rules as CPLEX and Xpress 4217are applied, so <span style="font-family: monospace;">OsiDualObjectiveLimit</span> 4218becomes <span style="font-family: monospace;">dualobjectivelimit</span>. 4219In addition, because these parameters are not sufficient to cover some 4220common functionality (especially for MIP solving), we include a further 4221set of common parameters that will map to solver specific parameters. 4222Currently these are:<br> 4223<br> 4224<table style="width: 100%; text-align: left;" border="1" cellpadding="2" 4225 cellspacing="2"> 4226 <tbody> 4227 <tr> 4228 <td style="vertical-align: top; font-family: monospace;">node 4229limit<br> 4230 </td> 4231 <td style="vertical-align: top;">number of MIP search-tree nodes 4232allowed<br> 4233 </td> 4234 </tr> 4235 <tr> 4236 <td style="vertical-align: top; font-family: monospace;">solution_limit<br> 4237 </td> 4238 <td style="vertical-align: top;">number of MIP solution allowed<br> 4239 </td> 4240 </tr> 4241 <tr> 4242 <td style="vertical-align: top; font-family: monospace;">integrality<br> 4243 </td> 4244 <td style="vertical-align: top;">integer tolerance<br> 4245 </td> 4246 </tr> 4247 <tr> 4248 <td style="vertical-align: top; font-family: monospace;">abmipgap<br> 4249 </td> 4250 <td style="vertical-align: top;">absolute MIP gap<br> 4251 </td> 4252 </tr> 4253 <tr> 4254 <td style="vertical-align: top; font-family: monospace;">mipgap<br> 4255 </td> 4256 <td style="vertical-align: top;">MIP gap<br> 4257 </td> 4258 </tr> 4259 <tr> 4260 <td style="vertical-align: top; font-family: monospace;">objdifference<br> 4261 </td> 4262 <td style="vertical-align: top;">cutoff increment<br> 4263 </td> 4264 </tr> 4265 </tbody> 4266</table> 4267<br> 4268Two new parameter types are used: 3 for integer solver-specific 4269parameters, 4 for double solver-specific parameters.<br> 4270<h3>Solver Numerical Differences</h3> 4271The external solver may give different results depending on the 4272FPU 4273control settings. One example that affects XPRESS 13.26 under 4274i386_linux 4275is that the floats are normally in `extended precision' of 80 bits in 4276the 4277hardware registers. This is the default used when ECLiPSe is started. 4278However, 4279if embedded Java is used, Java sets the float precision to double, i.e. 428064 bits. With XPRESS 13.26, this can result in different behaviours of 4281the solver, e.g. Retimer can give different alternative answers. 4282<h3>Debugging the External Solver</h3> 4283When an error occurs in using eplex (program crash, unexpected abort, 4284or 4285incorrect result returned), the error can be due to ECLiPSe 4286(either 4287C or Prolog level), or the external solver. In the case of the external 4288solver, we cannot fix the bug, but we can report it so that it can be 4289fixed 4290(and perhaps workaround the problem in our own code). 4291<p>In order to report a problem to Dash or ILOG or COIN, we need to 4292show that 4293the 4294problem 4295<br> 4296is due to their external solver. Several methods are available to do 4297this: 4298</p> 4299<ul> 4300 <li>if the problem occur while the external solver is solving a 4301problem, 4302the 4303problem state can be saved before it is solved by the external solver. 4304If the problem also occurs when the saved problem is loaded back into 4305(an 4306interactive) session of the solver, then the saved problem can be used 4307in the bug report. Eplex supports the saving of a problem before 4308solving 4309it with the option write_before_solve when the problem is setup. 4310The problem is written using as high a precision as possible when 4311written 4312as lp or mps format. However, sometimes the problem may not occur with 4313these formats, but would occur when written using the binary format. 4314The 4315disadvantage of the binary format is that it is solver and platform 4316specific, 4317and is non human-readable.</li> 4318 <li>log the external solver calls by eplex. See next section for more 4319details.</li> 4320</ul> 4321Other useful methods to aid in debugging is to run the whole ECLiPSe 4322session 4323under a memory debugger like valgrind. This can show up problems both 4324in 4325ECLiPSe and the external solver. 4326<h4><a name="Logging"></a>Logging External Solver Calls</h4> 4327There are extra code at the C level which are used to generate a log of 4328the calls made to the external solver. These code are only compiled if 4329the macro LOG_CALLS is defined. The log consists of the calls, plus 4330extra 4331support code, so that only a header file and the toplevel procedure 4332need 4333to be added to generate a pure C program, which can then be used to 4334make 4335bug reports to Dash or ILOG. 4336<br> 4337<br> 4338Note that in the case of OSI, the logged calls are to 4339coinplex.cpp, rather than directly to OSI. coinplex.cpp needs to 4340be included in the code in the report. The LOG_CALLS macro should 4341be defined (and coinplex.cpp compiled with it) when generating the 4342logged code. For the report, LOG_CALLS should be undef, and NOECLIPSE 4343defined. <br> 4344<h4>Structure of the log code</h4> 4345The log code consists of a number of step_N procedures, where N is an 4346integer. 4347Each such procedure makes a call to the appropriate optimise function 4348of 4349the external procedure, after setting up the data and making the other 4350supporting calls to the solver. After the optimise call, a new step_N 4351procedure, 4352with N incremented by 1. 4353<p>The data needed for the calls is stored in the same C level problem 4354descriptor lp_desc that the eplex code used. This is defined in 4355seplex.h, which is for both normal and logged code, with the logged 4356code compiled with a <span style="font-family: monospace;">-DNOECLIPSE</span> 4357flag.<br> 4358 4359<br> 4360<br> 4361</p> 4362<p>The include file has the following support variables (with the <span 4363 style="font-family: monospace;">NOECLIPSE</span> flag): 4364</p> 4365<p>struct lp_desc *lpd; 4366<br> 4367struct lp_desc *lpdmat[20]; /* change size if more lpd used */ 4368<br> 4369double objval; 4370<br> 4371int res,err; 4372</p> 4373<p>lpdmat[] is an array to support multiple handles. The generated log 4374code loads the appropriate lp_desc from lpdmat into lpd at the start of 4375a step_N procedure, and at any time the handle changes. Note that the 4376size 4377of lpdmat may need to be adjusted upwards if the logged program uses 4378more 4379handles than is defined. objval is used to store the objective value if 4380required (getting the objective value is not automatically generated in 4381the log code), and res and err are used to store any return codes from 4382function calls. 4383</p> 4384<p>Finally, a main procedure needs to be added to call all the step_N 4385procedures 4386in sequence, e.g. if there are three steps, and the solver is 4387Xpress 438813+: 4389</p> 4390<p> main() { 4391<br> 4392 XPRSinit(NULL); 4393<br> 4394 XPRScreateprob(&cpx_env); 4395<br> 4396 step_0(); 4397<br> 4398 step_1(); 4399<br> 4400 step_2(); 4401<br> 4402} 4403</p> 4404<p>In this case, the cpx_env is the dummy problem where all the default 4405parameter values are stored. 4406<br> 4407 4408</p> 4409<h4><a name="Logging_macros"></a>Logging macros</h4> 4410Several macros are defined to minimise the amount of special logging 4411code 4412needed: 4413<ul> 4414 <li> <span style="font-weight: bold;">Call(Ret, Proc)</span>: 4415Generates 4416a call to Proc in the form Ret = Proc, and a log for Proc if LOG_CALLS 4417is 4418defined.</li> 4419 <li> <span style="font-weight: bold;">CallN(Proc)</span>: Generates 4420a 4421call to 4422Proc in the form Proc, and a log for Proc if LOG_CALLS is defined. This 4423should be used if Proc should be called without getting the return code.</li> 4424 <li><span style="font-weight: bold;">Log0(Proc)</span>: Generate a 4425log for Proc if LOG_CALLS is defined. No actual call is generated, so 4426seperate 4427code for the call is needed. This macro should be used instead of Call 4428or CallN in case where the actual calls are in places where 4429logging cannot be done, or for code that is for the logging only, 4430and not in the actual eplex code.<br> 4431 </li> 4432 <li> <span style="font-weight: bold;">Log1(Proc, A1)</span>: 4433Generates a 4434log 4435for Proc if LOG_CALLS is defined. No actual call is generated, so 4436seperate 4437code for the call is needed. This macro should be used when an argument 4438for Proc needs to be supplied dynamically at run-time. Proc can be 4439written 4440in printf style with a leading % for the argument supplied in A1.</li> 4441 <li> <span style="font-weight: bold;">Log2(Proc, A1, A2)</span>: 4442Same as 4443Log1, 4444except it allows two dynamic arguments.</li> 4445 <li> <span style="font-weight: bold;">Log3(Proc, A1, A2, A3)</span>: 4446Same as 4447Log1, except it allows three dynamic arguments.</li> 4448 <li> <span style="font-weight: bold;">Log4(Proc, A1, A2, A3, A4)</span>: 4449Same 4450as Log1, except it allows four dynamic arguments.</li> 4451</ul> 4452<ul> 4453 <li> <b>Log5(Proc,A1,A2,A3,A4,A5):</b> Same as Log1, except it 4454allows 4455five dynamic 4456arguments.</li> 4457 <li> <b>Log6(Proc,A1,A2,A3,A4,A5,A6):</b> Same as Log1, except it 4458allows six dynamic 4459arguments.</li> 4460</ul> 4461<p><br> 4462In addition, logging code is also given between #ifdef LOG_CALLS, 4463e.g. for loading the various data structures. 4464</p> 4465<p>The logged call is generated by printfs, to the log_output stream. 4466In 4467order to allow macro transformation for the logged code to be 4468performed, 4469the call is wrapped in a Transform_Quoted macro, which performs the 4470transformation 4471even though the logged call occurs inside the printf quotes. 4472<br> 4473 4474<br> 4475 4476</p> 4477</body> 4478</html> 4479
