1% BEGIN LICENSE BLOCK 2% Version: CMPL 1.1 3% 4% The contents of this file are subject to the Cisco-style Mozilla Public 5% License Version 1.1 (the "License"); you may not use this file except 6% in compliance with the License. You may obtain a copy of the License 7% at www.eclipse-clp.org/license. 8% 9% Software distributed under the License is distributed on an "AS IS" 10% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See 11% the License for the specific language governing rights and limitations 12% under the License. 13% 14% The Original Code is The ECLiPSe Constraint Logic Programming System. 15% The Initial Developer of the Original Code is Cisco Systems, Inc. 16% Portions created by the Initial Developer are 17% Copyright (C) 2006 Cisco Systems, Inc. All Rights Reserved. 18% 19% Contributor(s): Andrew Eremin, IC-Parc 20% 21% END LICENSE BLOCK 22 23:- comment(categories, ["Algorithms","Constraints"]). 24:- comment(summary, "Column generation library"). 25:- comment(author, "Andrew Eremin"). 26:- comment(copyright, "Cisco Systems, Inc."). 27:- comment(date, "$Date: 2012/07/31 02:17:06 $"). 28:- comment(status, prototype). 29 30:- comment(desc, html("\ 31<P> 32 33 This library lets you use hybrid column generation. Partial linear 34 constraints are posted to a solver and further variables added to 35 them during search as they become profitable. The generated 36 variables will have a column of coefficients in the constraints of 37 the colgen instance associated with them corresponding to 38 particular instantiations of the variables of a subproblem. The 39 predicate to find profitable subproblem variable instantiations is 40 supplied by the user. When a user-defined branching predicate is 41 provided, the library can also be used for hybrid branch-and-price. 42</P><P> 43 The library uses the eplex library to solve LP master 44 problems, from which dual values are used to create cost functions 45 for the user-defined subproblem. Solution of master and subproblems 46 will iterate until no further subproblem solutions are posted to 47 the colgen instance. 48</P> ")). 49 50:- comment(minimize/3, [ 51template: "ColgenInstance:minimize(+SolveSubProblem, +Obj, -ObjVal)", 52 args: ["SolveSubProblem": "Subproblem solution predicate", 53 "Obj": "The objective function to minimize", 54 "ObjVal": "The optimal solution cost" 55 ], 56 summary: "Minimizes the problem associated with the colgen instance ColgenInstance.", 57 desc: html("\ 58 <P> 59 Minimize the partial linear expression <TT>Obj</TT> for the problem 60 associated with the colgen instance <TT>ColgenInstance</TT>, using 61 the user-defined predicate <TT>SolveSubProblem</TT> to provide 62 profitable variables during solution. The optimal solution cost is 63 unified with <TT>ObjVal</TT>. 64 </P><P> 65 The first argument of the subproblem solution predicate must be a 66 subproblem structure, as specified in solver_setup/3. 67 </P> 68 "), 69 see_also:[solver_setup/3] 70]). 71 72:- comment(solver_setup/2, [ 73template: "ColgenInstance:solver_setup(+SolveSubProblem, +Obj)", 74 args: ["SolveSubProblem": "Subproblem solution predicate", 75 "Obj": "The objective function to minimize" 76 ], 77 summary: "Define subproblem and objective for ColgenInstance.", 78 desc: html("\ 79 Equivalent to solver_setup/3 with default options. 80 "), 81 see_also:[colgen:solver_setup/3] 82]). 83 84:- comment(solver_setup/3, [ 85template: "ColgenInstance:solver_setup(+SolveSubProblem, +Obj, +Options)", 86 args: ["SolveSubProblem": "Subproblem solution predicate", 87 "Obj": "The objective function to minimize", 88 "Options": "A list of options" 89 ], 90 summary: "Define subproblem, objective and options for ColgenInstance.", 91 desc: html("\ 92 <P> 93 Define the partial linear expression <TT>Obj</TT> as the objective to 94 minimize for the problem associated with the colgen instance 95 <TT>ColgenInstance</TT>. It will typically contain implicit_sum terms. 96 </P><P> 97 Associate the user-defined predicate <TT>SolveSubProblem</TT> to provide 98 profitable variables during the solution process. 99 </P><P> 100 The first argument of the subproblem solution predicate must be a 101 subproblem structure: 102 <PRE> 103 sp_prob(master_pool, cutoff, cost, coeff_vars, aux, ...) 104 </PRE> 105 where and <TT>master_pool</TT> will be unified with the colgen 106 instance <TT>ColgenInstance</TT> so that solutions can be posted to 107 it from within the solution predicate, <TT>cutoff</TT> is a minimum 108 acceptable value for the cost of subproblem solutions that will be 109 updated before calling the predicate, <TT>cost</TT> is the variable 110 occurring in the implicit sum term of <TT>obj</TT> (if any) 111 representing the contribution of new subproblem solutions to the 112 master problem solution cost, <TT>coeff_vars</TT> is a list of all 113 subproblem variables occurring in the implicit sum terms of master 114 problem constraints. 115 </P> 116 <P> 117 The following options are accepted: 118 <DL> 119 <DT><TT>separate(+SeparationGoal)</TT><DD> 120 a user-specified separation goal (XXX). 121 <DT><TT>node_select(+Val)</TT><DD> 122 node selection criterion passed to bfs instance 123 <TT>(best_first|depth_first|best_estimate)</TT>. 124 <DT><TT>eplex_option(+EplexOption)</TT><DD> 125 Option to be passed to the associated eplex solver instance. 126 <DT><TT>disallow(+Policy)</TT><DD> 127 policy for active prevention of duplicate columns <TT>(off|lp|clp)</TT>. 128 <DT><TT>int_tolerance(+Tol)</TT><DD> 129 tolerance for optimality <TT>(1e-5|float)</TT>. 130 <DT><TT>basis_perturbation(+OffOn)</TT><DD> 131 should we try and perturb the external solver basis when we appear 132 to be at optimal and external solver returns same basis after adding 133 columns ('off' - no, 'on' - temporarily set the external solver 134 to always perturb) 135 <DT><TT>info_messages(+OffOn)</TT><DD> 136 print messages while solving. 137 <DT><TT>on_degeneracy(+Action)</TT><DD> 138 should we halt when we find degeneracy (default 'stop'), or 139 continue and let the subproblem solver deal with it ('continue'). 140 <DT><TT>stabilisation(+Policy)</TT><DD> 141 the policy to perform basis stabilisation: 142 <DL> 143 <DT><TT>off</TT><DD> 144 no stabilisation is performed. 145 <DT><TT>on(BoundIter, BoundUpdate, CoeffIter, CoeffUpdate)</TT><DD> 146 then the default policy is used with var bounds/coefficients 147 updated by BoundUpdate/CoeffUpdate after BoundIter/CoeffIter 148 iterations respectively. 149 <DT><TT>stab_pred(UpdatePred, StoppingPred)</TT><DD> 150 a user defined policy is employed and UpdatePred/ StoppingPred 151 should be predicates that perform the updates and test for 152 stopping conditions. 153 </DL> 154 </DL> 155 <P> 156 "), 157 see_also: [colgen:set/2] 158]). 159 160:- comment(cg_subproblem_solution/1, [ 161template: "ColgenInstance:cg_subproblem_solution(++Value)", 162 args: ["Value": "Subproblem solution (sp_sol structure) or list" 163 " of subproblem solutions" 164 ], 165 summary: "Posts new subproblem solution(s) to the colgen instance ColgenInstance.", 166 desc: html("\ 167 <P> 168 Post subproblem solution(s) corresponding to a column of coefficients 169 for a new master problem variable to the colgen instance 170 <TT>ColgenInstance</TT>. The argument must be a <TT>sp_sol</TT> 171 structure or list of such structures: 172 <PRE> 173 sp_sol(cost, coeff_vars, aux) 174 </PRE> 175 where <TT>cost</TT> is the master problem cost function coefficient 176 of the solution, <TT>coeff_vars</TT> is a list of <TT>Id-Val</TT> 177 pairs corresponding to the subproblem variable solution values and 178 identifier of the constraint in which it occurred as an implicit sum 179 term for those subproblem variables with a non-zero solution 180 value. <TT>aux</TT> should contain any problem specific information 181 which is of interest that is not represented uniquely by the cost 182 and objective coefficients. 183 </P> 184 ") 185]). 186 187:- comment(identified_constraint/2, [ 188template: "ColgenInstance:identified_constraint(+Cstr, ?Id)", 189 args: ["Cstr": "colgen constraint"], 190 summary: "Post an identified constraint to the colgen instance ColgenInstance.", 191 desc: html("\ 192 <P> 193 Post a constraint to the colgen instance <TT>ColgenInstance</TT> 194 which will be associated with the identifier <TT>Id</TT>. The 195 constraint <TT>Cstr</TT> must be a valid colgen constraint of type 196 <TT>>=/2,=:=/2,=</2,$>=/2,$=/2,$=</2</TT>. If <TT>Id</TT> is 197 uninstantiated it will be unified with the external solver row 198 number of the constraint when this is set up. The identifier can 199 later be used to retrieve the dual value or subproblem cost function 200 term associated with the constraint. 201 </P> "), 202 see_also: [(>=)/2,(=:=)/2,(=<)/2,($>=)/2,($=)/2,($=<)/2,get/2 ] ]). 203 204:- comment(get/2, [ 205template: "ColgenInstance:get(++What, -Value)", 206args: ["What": "Specification for information wanted (atom)", 207 "Value": "Returned value of What" 208 ], 209summary: "Obtain global problem information.", 210desc: html("\ 211<P> 212 Retrieve information about solver constraints and results, for the 213 colgen instance ColgenInstance. What can take one of the following values: 214 215<DL> 216 <DT><TT>dual(+Id)</TT> 217 <DD>Returns the floating-point value of the 218 current dual value for the constraint having identifier Id. See 219 also <TT>sp_obj</TT> below. 220<P> 221 <DT><TT>sp_obj(+Id)</TT> 222 <DD>Returns the sub problem objective terms currently associated 223 associated with the constraint having identifier Id. This will 224 be a term <TT>Val*Var</TT> where Val is the current dual value 225 for the constraint as also returned by 226 <TT>ColgenInstance:get(dual(Id), Val)</TT> and Var is the 227 subproblem variable in the implicit sum term of the 228 constraint. It is the users responsibility to get all relevant 229 terms of the current cost function and ensure that subproblem 230 solutions posted to the colgen instance have a non-negative 231 cost. 232<P> 233 <DT><TT>vars</TT> 234 <DD>Returns a list of all variables currently 235 associated with the colgen instance <TT>ColgenInstance</TT>. 236<P> 237 <DT><TT>non_zero_vars</TT> 238 <DD>Returns a list of all variables currently associated with 239 the colgen instance <TT>ColgenInstance</TT> that have a non-zero 240 optimal solution. This may be more efficient than retrieving all 241 problem variables after solution, since very many variables can 242 be generated and most will have a zero value in the optimal 243 solution. 244<P> 245 <DT><TT>frac_vars</TT> 246 <DD>Returns a list of all variables currently associated with 247 the colgen instance <TT>ColgenInstance</TT> that have a 248 fractional optimal solution. This is intended for use primarily 249 in user-defined problem branching predicates. 250<P> 251 <DT><TT>column_count</TT><DD> 252 Number of generated columns. 253<P> 254 <DT><TT>obj_val</TT><DD> 255 Current objective value. 256<P> 257 <DT><TT>unsatisfiable_cstrs</TT><DD> 258<P> 259 <DT><TT>satisfiable_cstrs</TT><DD> 260<P> 261 <DT><TT>generated_non_zero_vars</TT><DD> 262<P> 263 <DT><TT>non_zero_vars</TT><DD> 264<P> 265 <DT><TT>vars</TT><DD> 266<P> 267 <DT><TT>sep_goal</TT><DD> 268 Separation goal. 269<P> 270 <DT><TT>sp_solver</TT><DD> 271 Subproblem solver goal. 272<P> 273 <DT><TT>stab_coeff/bound_minus/plus(Ident)</TT><DD> 274 Stabilisation parameters per constraint. 275 276</DL>") ]). 277 278:- comment(var_get/3, [ 279template: "ColgenInstance:var_get(+Var, ++What, -Value)", 280args: ["Var": "A solver problem variable for the solver associated with ColgenInstance", 281 "What": "Specification for information wanted (atom)", 282 "Value": "Returned value of What" 283 ], 284summary: "Obtain information for an individual solver problem variable Var.", 285desc: html("\ 286<P> 287 Retrieve information about solver constraints and results related to a 288 particular variable, for the colgen instance ColgenInstance. 289 What can take one of the following values: 290<DL> 291 <DT><TT>mp_val</TT> 292 <DD>Returns the floating-point solution for variable Var. 293<P> 294 <DT><TT>cost</TT> 295 <DD>Returns the master problem objective coefficient 296 associated with the variable Var. 297<P> 298 <DT><TT>coeffs</TT> 299 <DD>Returns a list of Id-Val pairs representing the constraint 300 identifiers and coefficient values for the master problem 301 constraints in which the coefficient is non-zero associated 302 with the variable Var. 303<P> 304 <DT><TT>aux</TT> 305 <DD>Returns the auxiliary information associated with the 306 variable Var. The intended use is for subproblem information 307 not represented in the master problem constraint coefficients. 308</DL>") 309]). 310 311:- comment(colgen_instance/1, [ 312 amode:colgen_instance(++), 313 args: ["ColgenInstance": "Colgen instance name (atom)" 314 ], 315 summary: "Initialises the colgen instance ColgenInstance.", 316 desc: html("\ 317 <P> 318 Initialises the colgen instance ColgenInstance. A colgen instance is an 319 instance of the colgen solver, to which colgen partial linear arithmetic 320 constraints can be posted, and to which an external LP solver can be 321 associated and used to optimise the posted constraints with respect 322 to some objective. 323 </P><P> 324 If ColgenInstance is not an already existing colgen instance, a new colgen 325 instance will be created and initialised. If it is an existing colgen 326 instance, and it is not currently being used (having no outstanding posted 327 constraints and no associated solver), it is effectively reinitialised. 328 Otherwise, the predicate aborts with an error. Note that a colgen instance 329 is a module, and each colgen instance can be associated with at most one 330 solver at any time and vice versa. 331 </P> 332 "), 333 see_also: [(>=)/2,(=:=)/2,(=<)/2,($>=)/2,($=)/2,($=<)/2,var_get/3] 334]). 335 336%:- comment((>=)/2, [ 337% template: "ColgenInstance:(?X >= ?Y)", 338% args: ["X": "Partial linear expression", 339% "Y": "Partial linear expression" 340% ], 341% see_also: [(=:=)/2,(=<)/2,($=)/2,($=<)/2,($>=)/2,var_get/3], 342% 343% summary: "Constrains X to be greater than or equal to Y.", 344% desc: html("\ 345% Logically: Constrains X to be greater than or equal to Y. X 346% and Y are partial linear expressions. Partial linear 347% expressions may contain terms of the form 348% <TT>implicit_sum(+Var)</TT> in addition to any terms allowed 349% within a standard linear expression. Variables occurring 350% inside <TT>implicit_sum/1</TT> terms are taken to be 351% subproblem variables whose instantiation will correspond to 352% the coefficient of a generated master problem variable in this 353% constraint. Operationally, the constraint gets delayed until 354% the external solver state for ColgenInstance is invoked.") 355% ]). 356% 357%:- comment((=<)/2, [ 358% template: "ColgenInstance:(?X =< ?Y)", 359% args: ["X": "Partial linear expression", 360% "Y": "Partial linear expression" 361% ], 362% see_also: [(=:=)/2,(>=)/2,($=)/2,($=<)/2,($>=)/2,var_get/3], 363% summary: "Constrains X to be less than or equal to Y.", 364% desc: html("\ 365% Logically: Constrains X to be less than or equal to Y. X and 366% Y are partial linear expressions. Partial linear expressions 367% may contain terms of the form <TT>implicit_sum(+Var)</TT> in 368% addition to any terms allowed within a standard linear 369% expression. Variables occurring inside <TT>implicit_sum/1</TT> 370% terms are taken to be subproblem variables whose instantiation 371% will correspond to the coefficient of a generated master 372% problem variable in this constraint. Operationally, the 373% constraint gets delayed until the external solver state for 374% ColgenInstance is invoked.") ]). 375% 376%:- comment((=:=)/2, [ 377% template: "ColgenInstance:(?X =:= ?Y)", 378% args: ["X": "Partial linear expression", 379% "Y": "Partial linear expression" 380% ], 381% see_also: [(=<)/2,(>=)/2,($=)/2,($=<)/2,($>=)/2,var_get/3], 382% summary: "Constrains X to be equal to Y.", 383% desc: html("\ 384% Logically: Constrains X to be equal to Y. X and Y are partial 385% linear expressions. Partial linear expressions may contain 386% terms of the form <TT>implicit_sum(+Var)</TT> in addition to 387% any terms allowed within a standard linear 388% expression. Variables occurring inside <TT>implicit_sum/1</TT> 389% terms are taken to be subproblem variables whose instantiation 390% will correspond to the coefficient of a generated master 391% problem variable in this constraint. Operationally, the 392% constraint gets delayed until the external solver state for 393% ColgenInstance is invoked.") ]). 394 395:- comment(($>=)/2, [ 396 template: "ColgenInstance:(?X $>= ?Y)", 397 args: ["X": "Partial linear expression", 398 "Y": "Partial linear expression" 399 ], 400 see_also: [($=)/2,($=<)/2,(=:=)/2,(=<)/2,(>=)/2,var_get/3], 401 402 summary: "Constrains X to be greater than or equal to Y.", 403 desc: html("\ 404 <P> 405 Logically: Constrains X to be greater than or equal to Y. X and Y 406 are partial linear expressions. Partial linear expressions may 407 contain terms of the form <TT>implicit_sum(+Var)</TT> in addition 408 to any terms allowed within a standard linear 409 expression. Variables occurring inside <TT>implicit_sum/1</TT> 410 terms are taken to be subproblem variables whose instantiation 411 will correspond to the coefficient of a generated master problem 412 variable in this constraint. Operationally, the constraint gets 413 delayed until the external solver state for ColgenInstance is 414 invoked. 415 </P> 416 ") 417]). 418 419:- comment(($=<)/2, [ 420 template: "ColgenInstance:(?X $=< ?Y)", 421 args: ["X": "Partial linear expression", 422 "Y": "Partial linear expression" 423 ], 424 see_also: [($=)/2,($>=)/2,(=:=)/2,(=<)/2,(>=)/2,var_get/3], 425 summary: "Constrains X to be less than or equal to Y.", 426 desc: html("\ 427 <P> 428 Logically: Constrains X to be less than or equal to Y. X and Y 429 are partial linear expressions. Partial linear expressions may 430 contain terms of the form <TT>implicit_sum(+Var)</TT> in addition 431 to any terms allowed within a standard linear 432 expression. Variables occurring inside <TT>implicit_sum/1</TT> 433 terms are taken to be subproblem variables whose instantiation 434 will correspond to the coefficient of a generated master problem 435 variable in this constraint. Operationally, the constraint gets 436 delayed until the external solver state for ColgenInstance is 437 invoked. 438 </P> 439 ") 440]). 441 442:- comment(($=)/2, [ 443 template: "ColgenInstance:(?X $= ?Y)", 444 args: ["X": "Partial linear expression", 445 "Y": "Partial linear expression" 446 ], 447 see_also: [($=<)/2,($>=)/2,(=:=)/2,(=<)/2,(>=)/2,var_get/3], 448 summary: "Constrains X to be equal to Y.", 449 desc: html("\ 450 <P> 451 Logically: Constrains X to be less than or equal to Y. X and Y 452 are partial linear expressions. Partial linear expressions may 453 contain terms of the form <TT>implicit_sum(+Var)</TT> in addition 454 to any terms allowed within a standard linear 455 expression. Variables occurring inside <TT>implicit_sum/1</TT> 456 terms are taken to be subproblem variables whose instantiation 457 will correspond to the coefficient of a generated master problem 458 variable in this constraint. Operationally, the constraint gets 459 delayed until the external solver state for ColgenInstance is 460 invoked. 461 </P> 462 ") 463]). 464 465 466:- comment(set/2, [ 467 template: "ColgenInstance:set(+What,++Value)", 468 args: ["What": "Parameter name", 469 "Value":"Parameter value" 470 ], 471 see_also: [colgen:get/2, colgen:solver_setup/3], 472 summary: "Set parameters for column generation instance.", 473 desc: html("\ 474 <P> 475 Set parameters for the give column generation instance: 476 </P> 477<DL> 478<DT><TT>disallow (off|lp|clp)</TT><DD> 479 policy for active preventions of duplicate columns. 480<DT><TT>int_tolerance (1e-5|float)</TT><DD> 481 tolerance for optimality. 482<DT><TT>basis_perturbation (off|on)</TT><DD> 483 should we try and perturb the external solver basis when we appear 484 to be at optimal and external solver returns same basis after adding 485 columns ('off' - no, 'on' - temporarily set the external solver 486 to always perturb) 487<DT><TT>info_messages (off|on)</TT><DD> 488 print messages while solving. 489<DT><TT>on_degeneracy (stop|continue)</TT><DD> 490 should we halt when we find degeneracy (default 'stop'), or 491 continue and let the subproblem solver deal with it ('continue'). 492<DT><TT>stabilisation (off|on()|stab_pred())</TT><DD> 493 the policy to perform basis stabilisation: 494 <DL> 495 <DT><TT>off</TT><DD> 496 no stabilisation is performed. 497 <DT><TT>on(BoundIter, BoundUpdate, CoeffIter, CoeffUpdate)</TT><DD> 498 then the default policy is used with var bounds/coefficients 499 updated by BoundUpdate/CoeffUpdate after BoundIter/CoeffIter 500 iterations respectively. 501 <DT><TT>stab_pred(UpdatePred, StoppingPred)</TT><DD> 502 a user defined policy is employed and UpdatePred/ StoppingPred 503 should be predicates that perform the updates and test for 504 stopping conditions. 505 </DL> 506<DT><TT>stab_coeff/bound_minus/plus(Ident)</TT><DD> 507 parameters for stabilisation, per constraint. 508</DL> 509 ") 510]). 511 512 513 514/* 515:- comment(integers/1, [ 516 template: "ColgenInstance:integers(?Vars)", 517 args: ["Vars": "Variable or a list or variables"], 518 see_also: [_:integers/1,reals/1,(::)/2], 519 summary: "Constrains Vars to integers for ColgenInstance.", 520 desc: html("<P>\ 521 Constrains list Vars to integers in the eplex instance 522 EplexInstance. If a variable in Vars is not already a problem 523 variable for EplexInstance, it will be added as a new problem 524 variable. The external solver will then take the integrality into 525 account, i.e. to solve a MIP/MIQP rather than a relaxed LP/QP 526 problem. Unlike integers/1 constraints from other solvers, the 527 variables are not constrained to be integer type at the ECLiPSe 528 level. However, when a typed_solution is retrieved (e.g. via 529 eplex_var_get/3), this will be rounded to the nearest integer. 530 <P> 531 Note that even when problem variables have been declared as 532 integers in other solvers (ic or other external solver 533 states), if the integrality constraint is not made known to this 534 EplexInstance, any invocation of the eplex external solver (e.g. via 535 eplex_solve/1) will only solve a continuous relaxation. 536 <P> 537 ") 538 ]). 539 540*/ 541