lemon-project-template-glpk

annotate deps/glpk/src/glpapi13.c @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
rev   line source
alpar@9 1 /* glpapi13.c (branch-and-bound interface routines) */
alpar@9 2
alpar@9 3 /***********************************************************************
alpar@9 4 * This code is part of GLPK (GNU Linear Programming Kit).
alpar@9 5 *
alpar@9 6 * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
alpar@9 7 * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
alpar@9 8 * Moscow Aviation Institute, Moscow, Russia. All rights reserved.
alpar@9 9 * E-mail: <mao@gnu.org>.
alpar@9 10 *
alpar@9 11 * GLPK is free software: you can redistribute it and/or modify it
alpar@9 12 * under the terms of the GNU General Public License as published by
alpar@9 13 * the Free Software Foundation, either version 3 of the License, or
alpar@9 14 * (at your option) any later version.
alpar@9 15 *
alpar@9 16 * GLPK is distributed in the hope that it will be useful, but WITHOUT
alpar@9 17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
alpar@9 18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
alpar@9 19 * License for more details.
alpar@9 20 *
alpar@9 21 * You should have received a copy of the GNU General Public License
alpar@9 22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.
alpar@9 23 ***********************************************************************/
alpar@9 24
alpar@9 25 #include "glpios.h"
alpar@9 26
alpar@9 27 /***********************************************************************
alpar@9 28 * NAME
alpar@9 29 *
alpar@9 30 * glp_ios_reason - determine reason for calling the callback routine
alpar@9 31 *
alpar@9 32 * SYNOPSIS
alpar@9 33 *
alpar@9 34 * glp_ios_reason(glp_tree *tree);
alpar@9 35 *
alpar@9 36 * RETURNS
alpar@9 37 *
alpar@9 38 * The routine glp_ios_reason returns a code, which indicates why the
alpar@9 39 * user-defined callback routine is being called. */
alpar@9 40
alpar@9 41 int glp_ios_reason(glp_tree *tree)
alpar@9 42 { return
alpar@9 43 tree->reason;
alpar@9 44 }
alpar@9 45
alpar@9 46 /***********************************************************************
alpar@9 47 * NAME
alpar@9 48 *
alpar@9 49 * glp_ios_get_prob - access the problem object
alpar@9 50 *
alpar@9 51 * SYNOPSIS
alpar@9 52 *
alpar@9 53 * glp_prob *glp_ios_get_prob(glp_tree *tree);
alpar@9 54 *
alpar@9 55 * DESCRIPTION
alpar@9 56 *
alpar@9 57 * The routine glp_ios_get_prob can be called from the user-defined
alpar@9 58 * callback routine to access the problem object, which is used by the
alpar@9 59 * MIP solver. It is the original problem object passed to the routine
alpar@9 60 * glp_intopt if the MIP presolver is not used; otherwise it is an
alpar@9 61 * internal problem object built by the presolver. If the current
alpar@9 62 * subproblem exists, LP segment of the problem object corresponds to
alpar@9 63 * its LP relaxation.
alpar@9 64 *
alpar@9 65 * RETURNS
alpar@9 66 *
alpar@9 67 * The routine glp_ios_get_prob returns a pointer to the problem object
alpar@9 68 * used by the MIP solver. */
alpar@9 69
alpar@9 70 glp_prob *glp_ios_get_prob(glp_tree *tree)
alpar@9 71 { return
alpar@9 72 tree->mip;
alpar@9 73 }
alpar@9 74
alpar@9 75 /***********************************************************************
alpar@9 76 * NAME
alpar@9 77 *
alpar@9 78 * glp_ios_tree_size - determine size of the branch-and-bound tree
alpar@9 79 *
alpar@9 80 * SYNOPSIS
alpar@9 81 *
alpar@9 82 * void glp_ios_tree_size(glp_tree *tree, int *a_cnt, int *n_cnt,
alpar@9 83 * int *t_cnt);
alpar@9 84 *
alpar@9 85 * DESCRIPTION
alpar@9 86 *
alpar@9 87 * The routine glp_ios_tree_size stores the following three counts which
alpar@9 88 * characterize the current size of the branch-and-bound tree:
alpar@9 89 *
alpar@9 90 * a_cnt is the current number of active nodes, i.e. the current size of
alpar@9 91 * the active list;
alpar@9 92 *
alpar@9 93 * n_cnt is the current number of all (active and inactive) nodes;
alpar@9 94 *
alpar@9 95 * t_cnt is the total number of nodes including those which have been
alpar@9 96 * already removed from the tree. This count is increased whenever
alpar@9 97 * a new node appears in the tree and never decreased.
alpar@9 98 *
alpar@9 99 * If some of the parameters a_cnt, n_cnt, t_cnt is a null pointer, the
alpar@9 100 * corresponding count is not stored. */
alpar@9 101
alpar@9 102 void glp_ios_tree_size(glp_tree *tree, int *a_cnt, int *n_cnt,
alpar@9 103 int *t_cnt)
alpar@9 104 { if (a_cnt != NULL) *a_cnt = tree->a_cnt;
alpar@9 105 if (n_cnt != NULL) *n_cnt = tree->n_cnt;
alpar@9 106 if (t_cnt != NULL) *t_cnt = tree->t_cnt;
alpar@9 107 return;
alpar@9 108 }
alpar@9 109
alpar@9 110 /***********************************************************************
alpar@9 111 * NAME
alpar@9 112 *
alpar@9 113 * glp_ios_curr_node - determine current active subproblem
alpar@9 114 *
alpar@9 115 * SYNOPSIS
alpar@9 116 *
alpar@9 117 * int glp_ios_curr_node(glp_tree *tree);
alpar@9 118 *
alpar@9 119 * RETURNS
alpar@9 120 *
alpar@9 121 * The routine glp_ios_curr_node returns the reference number of the
alpar@9 122 * current active subproblem. However, if the current subproblem does
alpar@9 123 * not exist, the routine returns zero. */
alpar@9 124
alpar@9 125 int glp_ios_curr_node(glp_tree *tree)
alpar@9 126 { IOSNPD *node;
alpar@9 127 /* obtain pointer to the current subproblem */
alpar@9 128 node = tree->curr;
alpar@9 129 /* return its reference number */
alpar@9 130 return node == NULL ? 0 : node->p;
alpar@9 131 }
alpar@9 132
alpar@9 133 /***********************************************************************
alpar@9 134 * NAME
alpar@9 135 *
alpar@9 136 * glp_ios_next_node - determine next active subproblem
alpar@9 137 *
alpar@9 138 * SYNOPSIS
alpar@9 139 *
alpar@9 140 * int glp_ios_next_node(glp_tree *tree, int p);
alpar@9 141 *
alpar@9 142 * RETURNS
alpar@9 143 *
alpar@9 144 * If the parameter p is zero, the routine glp_ios_next_node returns
alpar@9 145 * the reference number of the first active subproblem. However, if the
alpar@9 146 * tree is empty, zero is returned.
alpar@9 147 *
alpar@9 148 * If the parameter p is not zero, it must specify the reference number
alpar@9 149 * of some active subproblem, in which case the routine returns the
alpar@9 150 * reference number of the next active subproblem. However, if there is
alpar@9 151 * no next active subproblem in the list, zero is returned.
alpar@9 152 *
alpar@9 153 * All subproblems in the active list are ordered chronologically, i.e.
alpar@9 154 * subproblem A precedes subproblem B if A was created before B. */
alpar@9 155
alpar@9 156 int glp_ios_next_node(glp_tree *tree, int p)
alpar@9 157 { IOSNPD *node;
alpar@9 158 if (p == 0)
alpar@9 159 { /* obtain pointer to the first active subproblem */
alpar@9 160 node = tree->head;
alpar@9 161 }
alpar@9 162 else
alpar@9 163 { /* obtain pointer to the specified subproblem */
alpar@9 164 if (!(1 <= p && p <= tree->nslots))
alpar@9 165 err: xerror("glp_ios_next_node: p = %d; invalid subproblem refer"
alpar@9 166 "ence number\n", p);
alpar@9 167 node = tree->slot[p].node;
alpar@9 168 if (node == NULL) goto err;
alpar@9 169 /* the specified subproblem must be active */
alpar@9 170 if (node->count != 0)
alpar@9 171 xerror("glp_ios_next_node: p = %d; subproblem not in the ac"
alpar@9 172 "tive list\n", p);
alpar@9 173 /* obtain pointer to the next active subproblem */
alpar@9 174 node = node->next;
alpar@9 175 }
alpar@9 176 /* return the reference number */
alpar@9 177 return node == NULL ? 0 : node->p;
alpar@9 178 }
alpar@9 179
alpar@9 180 /***********************************************************************
alpar@9 181 * NAME
alpar@9 182 *
alpar@9 183 * glp_ios_prev_node - determine previous active subproblem
alpar@9 184 *
alpar@9 185 * SYNOPSIS
alpar@9 186 *
alpar@9 187 * int glp_ios_prev_node(glp_tree *tree, int p);
alpar@9 188 *
alpar@9 189 * RETURNS
alpar@9 190 *
alpar@9 191 * If the parameter p is zero, the routine glp_ios_prev_node returns
alpar@9 192 * the reference number of the last active subproblem. However, if the
alpar@9 193 * tree is empty, zero is returned.
alpar@9 194 *
alpar@9 195 * If the parameter p is not zero, it must specify the reference number
alpar@9 196 * of some active subproblem, in which case the routine returns the
alpar@9 197 * reference number of the previous active subproblem. However, if there
alpar@9 198 * is no previous active subproblem in the list, zero is returned.
alpar@9 199 *
alpar@9 200 * All subproblems in the active list are ordered chronologically, i.e.
alpar@9 201 * subproblem A precedes subproblem B if A was created before B. */
alpar@9 202
alpar@9 203 int glp_ios_prev_node(glp_tree *tree, int p)
alpar@9 204 { IOSNPD *node;
alpar@9 205 if (p == 0)
alpar@9 206 { /* obtain pointer to the last active subproblem */
alpar@9 207 node = tree->tail;
alpar@9 208 }
alpar@9 209 else
alpar@9 210 { /* obtain pointer to the specified subproblem */
alpar@9 211 if (!(1 <= p && p <= tree->nslots))
alpar@9 212 err: xerror("glp_ios_prev_node: p = %d; invalid subproblem refer"
alpar@9 213 "ence number\n", p);
alpar@9 214 node = tree->slot[p].node;
alpar@9 215 if (node == NULL) goto err;
alpar@9 216 /* the specified subproblem must be active */
alpar@9 217 if (node->count != 0)
alpar@9 218 xerror("glp_ios_prev_node: p = %d; subproblem not in the ac"
alpar@9 219 "tive list\n", p);
alpar@9 220 /* obtain pointer to the previous active subproblem */
alpar@9 221 node = node->prev;
alpar@9 222 }
alpar@9 223 /* return the reference number */
alpar@9 224 return node == NULL ? 0 : node->p;
alpar@9 225 }
alpar@9 226
alpar@9 227 /***********************************************************************
alpar@9 228 * NAME
alpar@9 229 *
alpar@9 230 * glp_ios_up_node - determine parent subproblem
alpar@9 231 *
alpar@9 232 * SYNOPSIS
alpar@9 233 *
alpar@9 234 * int glp_ios_up_node(glp_tree *tree, int p);
alpar@9 235 *
alpar@9 236 * RETURNS
alpar@9 237 *
alpar@9 238 * The parameter p must specify the reference number of some (active or
alpar@9 239 * inactive) subproblem, in which case the routine iet_get_up_node
alpar@9 240 * returns the reference number of its parent subproblem. However, if
alpar@9 241 * the specified subproblem is the root of the tree and, therefore, has
alpar@9 242 * no parent, the routine returns zero. */
alpar@9 243
alpar@9 244 int glp_ios_up_node(glp_tree *tree, int p)
alpar@9 245 { IOSNPD *node;
alpar@9 246 /* obtain pointer to the specified subproblem */
alpar@9 247 if (!(1 <= p && p <= tree->nslots))
alpar@9 248 err: xerror("glp_ios_up_node: p = %d; invalid subproblem reference "
alpar@9 249 "number\n", p);
alpar@9 250 node = tree->slot[p].node;
alpar@9 251 if (node == NULL) goto err;
alpar@9 252 /* obtain pointer to the parent subproblem */
alpar@9 253 node = node->up;
alpar@9 254 /* return the reference number */
alpar@9 255 return node == NULL ? 0 : node->p;
alpar@9 256 }
alpar@9 257
alpar@9 258 /***********************************************************************
alpar@9 259 * NAME
alpar@9 260 *
alpar@9 261 * glp_ios_node_level - determine subproblem level
alpar@9 262 *
alpar@9 263 * SYNOPSIS
alpar@9 264 *
alpar@9 265 * int glp_ios_node_level(glp_tree *tree, int p);
alpar@9 266 *
alpar@9 267 * RETURNS
alpar@9 268 *
alpar@9 269 * The routine glp_ios_node_level returns the level of the subproblem,
alpar@9 270 * whose reference number is p, in the branch-and-bound tree. (The root
alpar@9 271 * subproblem has level 0, and the level of any other subproblem is the
alpar@9 272 * level of its parent plus one.) */
alpar@9 273
alpar@9 274 int glp_ios_node_level(glp_tree *tree, int p)
alpar@9 275 { IOSNPD *node;
alpar@9 276 /* obtain pointer to the specified subproblem */
alpar@9 277 if (!(1 <= p && p <= tree->nslots))
alpar@9 278 err: xerror("glp_ios_node_level: p = %d; invalid subproblem referen"
alpar@9 279 "ce number\n", p);
alpar@9 280 node = tree->slot[p].node;
alpar@9 281 if (node == NULL) goto err;
alpar@9 282 /* return the node level */
alpar@9 283 return node->level;
alpar@9 284 }
alpar@9 285
alpar@9 286 /***********************************************************************
alpar@9 287 * NAME
alpar@9 288 *
alpar@9 289 * glp_ios_node_bound - determine subproblem local bound
alpar@9 290 *
alpar@9 291 * SYNOPSIS
alpar@9 292 *
alpar@9 293 * double glp_ios_node_bound(glp_tree *tree, int p);
alpar@9 294 *
alpar@9 295 * RETURNS
alpar@9 296 *
alpar@9 297 * The routine glp_ios_node_bound returns the local bound for (active or
alpar@9 298 * inactive) subproblem, whose reference number is p.
alpar@9 299 *
alpar@9 300 * COMMENTS
alpar@9 301 *
alpar@9 302 * The local bound for subproblem p is an lower (minimization) or upper
alpar@9 303 * (maximization) bound for integer optimal solution to this subproblem
alpar@9 304 * (not to the original problem). This bound is local in the sense that
alpar@9 305 * only subproblems in the subtree rooted at node p cannot have better
alpar@9 306 * integer feasible solutions.
alpar@9 307 *
alpar@9 308 * On creating a subproblem (due to the branching step) its local bound
alpar@9 309 * is inherited from its parent and then may get only stronger (never
alpar@9 310 * weaker). For the root subproblem its local bound is initially set to
alpar@9 311 * -DBL_MAX (minimization) or +DBL_MAX (maximization) and then improved
alpar@9 312 * as the root LP relaxation has been solved.
alpar@9 313 *
alpar@9 314 * Note that the local bound is not necessarily the optimal objective
alpar@9 315 * value to corresponding LP relaxation; it may be stronger. */
alpar@9 316
alpar@9 317 double glp_ios_node_bound(glp_tree *tree, int p)
alpar@9 318 { IOSNPD *node;
alpar@9 319 /* obtain pointer to the specified subproblem */
alpar@9 320 if (!(1 <= p && p <= tree->nslots))
alpar@9 321 err: xerror("glp_ios_node_bound: p = %d; invalid subproblem referen"
alpar@9 322 "ce number\n", p);
alpar@9 323 node = tree->slot[p].node;
alpar@9 324 if (node == NULL) goto err;
alpar@9 325 /* return the node local bound */
alpar@9 326 return node->bound;
alpar@9 327 }
alpar@9 328
alpar@9 329 /***********************************************************************
alpar@9 330 * NAME
alpar@9 331 *
alpar@9 332 * glp_ios_best_node - find active subproblem with best local bound
alpar@9 333 *
alpar@9 334 * SYNOPSIS
alpar@9 335 *
alpar@9 336 * int glp_ios_best_node(glp_tree *tree);
alpar@9 337 *
alpar@9 338 * RETURNS
alpar@9 339 *
alpar@9 340 * The routine glp_ios_best_node returns the reference number of the
alpar@9 341 * active subproblem, whose local bound is best (i.e. smallest in case
alpar@9 342 * of minimization or largest in case of maximization). However, if the
alpar@9 343 * tree is empty, the routine returns zero.
alpar@9 344 *
alpar@9 345 * COMMENTS
alpar@9 346 *
alpar@9 347 * The best local bound is an lower (minimization) or upper
alpar@9 348 * (maximization) bound for integer optimal solution to the original
alpar@9 349 * MIP problem. */
alpar@9 350
alpar@9 351 int glp_ios_best_node(glp_tree *tree)
alpar@9 352 { return
alpar@9 353 ios_best_node(tree);
alpar@9 354 }
alpar@9 355
alpar@9 356 /***********************************************************************
alpar@9 357 * NAME
alpar@9 358 *
alpar@9 359 * glp_ios_mip_gap - compute relative MIP gap
alpar@9 360 *
alpar@9 361 * SYNOPSIS
alpar@9 362 *
alpar@9 363 * double glp_ios_mip_gap(glp_tree *tree);
alpar@9 364 *
alpar@9 365 * DESCRIPTION
alpar@9 366 *
alpar@9 367 * The routine glp_ios_mip_gap computes the relative MIP gap with the
alpar@9 368 * following formula:
alpar@9 369 *
alpar@9 370 * gap = |best_mip - best_bnd| / (|best_mip| + DBL_EPSILON),
alpar@9 371 *
alpar@9 372 * where best_mip is the best integer feasible solution found so far,
alpar@9 373 * best_bnd is the best (global) bound. If no integer feasible solution
alpar@9 374 * has been found yet, gap is set to DBL_MAX.
alpar@9 375 *
alpar@9 376 * RETURNS
alpar@9 377 *
alpar@9 378 * The routine glp_ios_mip_gap returns the relative MIP gap. */
alpar@9 379
alpar@9 380 double glp_ios_mip_gap(glp_tree *tree)
alpar@9 381 { return
alpar@9 382 ios_relative_gap(tree);
alpar@9 383 }
alpar@9 384
alpar@9 385 /***********************************************************************
alpar@9 386 * NAME
alpar@9 387 *
alpar@9 388 * glp_ios_node_data - access subproblem application-specific data
alpar@9 389 *
alpar@9 390 * SYNOPSIS
alpar@9 391 *
alpar@9 392 * void *glp_ios_node_data(glp_tree *tree, int p);
alpar@9 393 *
alpar@9 394 * DESCRIPTION
alpar@9 395 *
alpar@9 396 * The routine glp_ios_node_data allows the application accessing a
alpar@9 397 * memory block allocated for the subproblem (which may be active or
alpar@9 398 * inactive), whose reference number is p.
alpar@9 399 *
alpar@9 400 * The size of the block is defined by the control parameter cb_size
alpar@9 401 * passed to the routine glp_intopt. The block is initialized by binary
alpar@9 402 * zeros on creating corresponding subproblem, and its contents is kept
alpar@9 403 * until the subproblem will be removed from the tree.
alpar@9 404 *
alpar@9 405 * The application may use these memory blocks to store specific data
alpar@9 406 * for each subproblem.
alpar@9 407 *
alpar@9 408 * RETURNS
alpar@9 409 *
alpar@9 410 * The routine glp_ios_node_data returns a pointer to the memory block
alpar@9 411 * for the specified subproblem. Note that if cb_size = 0, the routine
alpar@9 412 * returns a null pointer. */
alpar@9 413
alpar@9 414 void *glp_ios_node_data(glp_tree *tree, int p)
alpar@9 415 { IOSNPD *node;
alpar@9 416 /* obtain pointer to the specified subproblem */
alpar@9 417 if (!(1 <= p && p <= tree->nslots))
alpar@9 418 err: xerror("glp_ios_node_level: p = %d; invalid subproblem referen"
alpar@9 419 "ce number\n", p);
alpar@9 420 node = tree->slot[p].node;
alpar@9 421 if (node == NULL) goto err;
alpar@9 422 /* return pointer to the application-specific data */
alpar@9 423 return node->data;
alpar@9 424 }
alpar@9 425
alpar@9 426 /***********************************************************************
alpar@9 427 * NAME
alpar@9 428 *
alpar@9 429 * glp_ios_row_attr - retrieve additional row attributes
alpar@9 430 *
alpar@9 431 * SYNOPSIS
alpar@9 432 *
alpar@9 433 * void glp_ios_row_attr(glp_tree *tree, int i, glp_attr *attr);
alpar@9 434 *
alpar@9 435 * DESCRIPTION
alpar@9 436 *
alpar@9 437 * The routine glp_ios_row_attr retrieves additional attributes of row
alpar@9 438 * i and stores them in the structure glp_attr. */
alpar@9 439
alpar@9 440 void glp_ios_row_attr(glp_tree *tree, int i, glp_attr *attr)
alpar@9 441 { GLPROW *row;
alpar@9 442 if (!(1 <= i && i <= tree->mip->m))
alpar@9 443 xerror("glp_ios_row_attr: i = %d; row number out of range\n",
alpar@9 444 i);
alpar@9 445 row = tree->mip->row[i];
alpar@9 446 attr->level = row->level;
alpar@9 447 attr->origin = row->origin;
alpar@9 448 attr->klass = row->klass;
alpar@9 449 return;
alpar@9 450 }
alpar@9 451
alpar@9 452 /**********************************************************************/
alpar@9 453
alpar@9 454 int glp_ios_pool_size(glp_tree *tree)
alpar@9 455 { /* determine current size of the cut pool */
alpar@9 456 if (tree->reason != GLP_ICUTGEN)
alpar@9 457 xerror("glp_ios_pool_size: operation not allowed\n");
alpar@9 458 xassert(tree->local != NULL);
alpar@9 459 return tree->local->size;
alpar@9 460 }
alpar@9 461
alpar@9 462 /**********************************************************************/
alpar@9 463
alpar@9 464 int glp_ios_add_row(glp_tree *tree,
alpar@9 465 const char *name, int klass, int flags, int len, const int ind[],
alpar@9 466 const double val[], int type, double rhs)
alpar@9 467 { /* add row (constraint) to the cut pool */
alpar@9 468 int num;
alpar@9 469 if (tree->reason != GLP_ICUTGEN)
alpar@9 470 xerror("glp_ios_add_row: operation not allowed\n");
alpar@9 471 xassert(tree->local != NULL);
alpar@9 472 num = ios_add_row(tree, tree->local, name, klass, flags, len,
alpar@9 473 ind, val, type, rhs);
alpar@9 474 return num;
alpar@9 475 }
alpar@9 476
alpar@9 477 /**********************************************************************/
alpar@9 478
alpar@9 479 void glp_ios_del_row(glp_tree *tree, int i)
alpar@9 480 { /* remove row (constraint) from the cut pool */
alpar@9 481 if (tree->reason != GLP_ICUTGEN)
alpar@9 482 xerror("glp_ios_del_row: operation not allowed\n");
alpar@9 483 ios_del_row(tree, tree->local, i);
alpar@9 484 return;
alpar@9 485 }
alpar@9 486
alpar@9 487 /**********************************************************************/
alpar@9 488
alpar@9 489 void glp_ios_clear_pool(glp_tree *tree)
alpar@9 490 { /* remove all rows (constraints) from the cut pool */
alpar@9 491 if (tree->reason != GLP_ICUTGEN)
alpar@9 492 xerror("glp_ios_clear_pool: operation not allowed\n");
alpar@9 493 ios_clear_pool(tree, tree->local);
alpar@9 494 return;
alpar@9 495 }
alpar@9 496
alpar@9 497 /***********************************************************************
alpar@9 498 * NAME
alpar@9 499 *
alpar@9 500 * glp_ios_can_branch - check if can branch upon specified variable
alpar@9 501 *
alpar@9 502 * SYNOPSIS
alpar@9 503 *
alpar@9 504 * int glp_ios_can_branch(glp_tree *tree, int j);
alpar@9 505 *
alpar@9 506 * RETURNS
alpar@9 507 *
alpar@9 508 * If j-th variable (column) can be used to branch upon, the routine
alpar@9 509 * glp_ios_can_branch returns non-zero, otherwise zero. */
alpar@9 510
alpar@9 511 int glp_ios_can_branch(glp_tree *tree, int j)
alpar@9 512 { if (!(1 <= j && j <= tree->mip->n))
alpar@9 513 xerror("glp_ios_can_branch: j = %d; column number out of range"
alpar@9 514 "\n", j);
alpar@9 515 return tree->non_int[j];
alpar@9 516 }
alpar@9 517
alpar@9 518 /***********************************************************************
alpar@9 519 * NAME
alpar@9 520 *
alpar@9 521 * glp_ios_branch_upon - choose variable to branch upon
alpar@9 522 *
alpar@9 523 * SYNOPSIS
alpar@9 524 *
alpar@9 525 * void glp_ios_branch_upon(glp_tree *tree, int j, int sel);
alpar@9 526 *
alpar@9 527 * DESCRIPTION
alpar@9 528 *
alpar@9 529 * The routine glp_ios_branch_upon can be called from the user-defined
alpar@9 530 * callback routine in response to the reason GLP_IBRANCH to choose a
alpar@9 531 * branching variable, whose ordinal number is j. Should note that only
alpar@9 532 * variables, for which the routine glp_ios_can_branch returns non-zero,
alpar@9 533 * can be used to branch upon.
alpar@9 534 *
alpar@9 535 * The parameter sel is a flag that indicates which branch (subproblem)
alpar@9 536 * should be selected next to continue the search:
alpar@9 537 *
alpar@9 538 * GLP_DN_BRNCH - select down-branch;
alpar@9 539 * GLP_UP_BRNCH - select up-branch;
alpar@9 540 * GLP_NO_BRNCH - use general selection technique. */
alpar@9 541
alpar@9 542 void glp_ios_branch_upon(glp_tree *tree, int j, int sel)
alpar@9 543 { if (!(1 <= j && j <= tree->mip->n))
alpar@9 544 xerror("glp_ios_branch_upon: j = %d; column number out of rang"
alpar@9 545 "e\n", j);
alpar@9 546 if (!(sel == GLP_DN_BRNCH || sel == GLP_UP_BRNCH ||
alpar@9 547 sel == GLP_NO_BRNCH))
alpar@9 548 xerror("glp_ios_branch_upon: sel = %d: invalid branch selectio"
alpar@9 549 "n flag\n", sel);
alpar@9 550 if (!(tree->non_int[j]))
alpar@9 551 xerror("glp_ios_branch_upon: j = %d; variable cannot be used t"
alpar@9 552 "o branch upon\n", j);
alpar@9 553 if (tree->br_var != 0)
alpar@9 554 xerror("glp_ios_branch_upon: branching variable already chosen"
alpar@9 555 "\n");
alpar@9 556 tree->br_var = j;
alpar@9 557 tree->br_sel = sel;
alpar@9 558 return;
alpar@9 559 }
alpar@9 560
alpar@9 561 /***********************************************************************
alpar@9 562 * NAME
alpar@9 563 *
alpar@9 564 * glp_ios_select_node - select subproblem to continue the search
alpar@9 565 *
alpar@9 566 * SYNOPSIS
alpar@9 567 *
alpar@9 568 * void glp_ios_select_node(glp_tree *tree, int p);
alpar@9 569 *
alpar@9 570 * DESCRIPTION
alpar@9 571 *
alpar@9 572 * The routine glp_ios_select_node can be called from the user-defined
alpar@9 573 * callback routine in response to the reason GLP_ISELECT to select an
alpar@9 574 * active subproblem, whose reference number is p. The search will be
alpar@9 575 * continued from the subproblem selected. */
alpar@9 576
alpar@9 577 void glp_ios_select_node(glp_tree *tree, int p)
alpar@9 578 { IOSNPD *node;
alpar@9 579 /* obtain pointer to the specified subproblem */
alpar@9 580 if (!(1 <= p && p <= tree->nslots))
alpar@9 581 err: xerror("glp_ios_select_node: p = %d; invalid subproblem refere"
alpar@9 582 "nce number\n", p);
alpar@9 583 node = tree->slot[p].node;
alpar@9 584 if (node == NULL) goto err;
alpar@9 585 /* the specified subproblem must be active */
alpar@9 586 if (node->count != 0)
alpar@9 587 xerror("glp_ios_select_node: p = %d; subproblem not in the act"
alpar@9 588 "ive list\n", p);
alpar@9 589 /* no subproblem must be selected yet */
alpar@9 590 if (tree->next_p != 0)
alpar@9 591 xerror("glp_ios_select_node: subproblem already selected\n");
alpar@9 592 /* select the specified subproblem to continue the search */
alpar@9 593 tree->next_p = p;
alpar@9 594 return;
alpar@9 595 }
alpar@9 596
alpar@9 597 /***********************************************************************
alpar@9 598 * NAME
alpar@9 599 *
alpar@9 600 * glp_ios_heur_sol - provide solution found by heuristic
alpar@9 601 *
alpar@9 602 * SYNOPSIS
alpar@9 603 *
alpar@9 604 * int glp_ios_heur_sol(glp_tree *tree, const double x[]);
alpar@9 605 *
alpar@9 606 * DESCRIPTION
alpar@9 607 *
alpar@9 608 * The routine glp_ios_heur_sol can be called from the user-defined
alpar@9 609 * callback routine in response to the reason GLP_IHEUR to provide an
alpar@9 610 * integer feasible solution found by a primal heuristic.
alpar@9 611 *
alpar@9 612 * Primal values of *all* variables (columns) found by the heuristic
alpar@9 613 * should be placed in locations x[1], ..., x[n], where n is the number
alpar@9 614 * of columns in the original problem object. Note that the routine
alpar@9 615 * glp_ios_heur_sol *does not* check primal feasibility of the solution
alpar@9 616 * provided.
alpar@9 617 *
alpar@9 618 * Using the solution passed in the array x the routine computes value
alpar@9 619 * of the objective function. If the objective value is better than the
alpar@9 620 * best known integer feasible solution, the routine computes values of
alpar@9 621 * auxiliary variables (rows) and stores all solution components in the
alpar@9 622 * problem object.
alpar@9 623 *
alpar@9 624 * RETURNS
alpar@9 625 *
alpar@9 626 * If the provided solution is accepted, the routine glp_ios_heur_sol
alpar@9 627 * returns zero. Otherwise, if the provided solution is rejected, the
alpar@9 628 * routine returns non-zero. */
alpar@9 629
alpar@9 630 int glp_ios_heur_sol(glp_tree *tree, const double x[])
alpar@9 631 { glp_prob *mip = tree->mip;
alpar@9 632 int m = tree->orig_m;
alpar@9 633 int n = tree->n;
alpar@9 634 int i, j;
alpar@9 635 double obj;
alpar@9 636 xassert(mip->m >= m);
alpar@9 637 xassert(mip->n == n);
alpar@9 638 /* check values of integer variables and compute value of the
alpar@9 639 objective function */
alpar@9 640 obj = mip->c0;
alpar@9 641 for (j = 1; j <= n; j++)
alpar@9 642 { GLPCOL *col = mip->col[j];
alpar@9 643 if (col->kind == GLP_IV)
alpar@9 644 { /* provided value must be integral */
alpar@9 645 if (x[j] != floor(x[j])) return 1;
alpar@9 646 }
alpar@9 647 obj += col->coef * x[j];
alpar@9 648 }
alpar@9 649 /* check if the provided solution is better than the best known
alpar@9 650 integer feasible solution */
alpar@9 651 if (mip->mip_stat == GLP_FEAS)
alpar@9 652 { switch (mip->dir)
alpar@9 653 { case GLP_MIN:
alpar@9 654 if (obj >= tree->mip->mip_obj) return 1;
alpar@9 655 break;
alpar@9 656 case GLP_MAX:
alpar@9 657 if (obj <= tree->mip->mip_obj) return 1;
alpar@9 658 break;
alpar@9 659 default:
alpar@9 660 xassert(mip != mip);
alpar@9 661 }
alpar@9 662 }
alpar@9 663 /* it is better; store it in the problem object */
alpar@9 664 if (tree->parm->msg_lev >= GLP_MSG_ON)
alpar@9 665 xprintf("Solution found by heuristic: %.12g\n", obj);
alpar@9 666 mip->mip_stat = GLP_FEAS;
alpar@9 667 mip->mip_obj = obj;
alpar@9 668 for (j = 1; j <= n; j++)
alpar@9 669 mip->col[j]->mipx = x[j];
alpar@9 670 for (i = 1; i <= m; i++)
alpar@9 671 { GLPROW *row = mip->row[i];
alpar@9 672 GLPAIJ *aij;
alpar@9 673 row->mipx = 0.0;
alpar@9 674 for (aij = row->ptr; aij != NULL; aij = aij->r_next)
alpar@9 675 row->mipx += aij->val * aij->col->mipx;
alpar@9 676 }
alpar@9 677 return 0;
alpar@9 678 }
alpar@9 679
alpar@9 680 /***********************************************************************
alpar@9 681 * NAME
alpar@9 682 *
alpar@9 683 * glp_ios_terminate - terminate the solution process.
alpar@9 684 *
alpar@9 685 * SYNOPSIS
alpar@9 686 *
alpar@9 687 * void glp_ios_terminate(glp_tree *tree);
alpar@9 688 *
alpar@9 689 * DESCRIPTION
alpar@9 690 *
alpar@9 691 * The routine glp_ios_terminate sets a flag indicating that the MIP
alpar@9 692 * solver should prematurely terminate the search. */
alpar@9 693
alpar@9 694 void glp_ios_terminate(glp_tree *tree)
alpar@9 695 { if (tree->parm->msg_lev >= GLP_MSG_DBG)
alpar@9 696 xprintf("The search is prematurely terminated due to applicati"
alpar@9 697 "on request\n");
alpar@9 698 tree->stop = 1;
alpar@9 699 return;
alpar@9 700 }
alpar@9 701
alpar@9 702 /* eof */