lemon-project-template-glpk: 33de93886c88 deps/glpk/src/glpapi13.c

lemon-project-template-glpk

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

Import GLPK 4.47

author	Alpar Juttner <alpar@cs.elte.hu>
date	Sun, 06 Nov 2011 20:59:10 +0100
parents
children

line source

1 /* glpapi13.c (branch-and-bound interface routines) */

3 /***********************************************************************

4 * This code is part of GLPK (GNU Linear Programming Kit).

5 *

7 * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,

9 * E-mail: <mao@gnu.org>.

10 *

11 * GLPK is free software: you can redistribute it and/or modify it

12 * under the terms of the GNU General Public License as published by

13 * the Free Software Foundation, either version 3 of the License, or

14 * (at your option) any later version.

15 *

16 * GLPK is distributed in the hope that it will be useful, but WITHOUT

17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY

18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public

19 * License for more details.

20 *

21 * You should have received a copy of the GNU General Public License

22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.

23 ***********************************************************************/

25 #include "glpios.h"

27 /***********************************************************************

28 * NAME

29 *

30 * glp_ios_reason - determine reason for calling the callback routine

31 *

32 * SYNOPSIS

33 *

34 * glp_ios_reason(glp_tree *tree);

35 *

36 * RETURNS

37 *

38 * The routine glp_ios_reason returns a code, which indicates why the

39 * user-defined callback routine is being called. */

41 int glp_ios_reason(glp_tree *tree)

42 { return

43 tree->reason;

44 }

46 /***********************************************************************

47 * NAME

48 *

49 * glp_ios_get_prob - access the problem object

50 *

51 * SYNOPSIS

52 *

53 * glp_prob *glp_ios_get_prob(glp_tree *tree);

54 *

55 * DESCRIPTION

56 *

57 * The routine glp_ios_get_prob can be called from the user-defined

58 * callback routine to access the problem object, which is used by the

59 * MIP solver. It is the original problem object passed to the routine

60 * glp_intopt if the MIP presolver is not used; otherwise it is an

61 * internal problem object built by the presolver. If the current

62 * subproblem exists, LP segment of the problem object corresponds to

63 * its LP relaxation.

64 *

65 * RETURNS

66 *

67 * The routine glp_ios_get_prob returns a pointer to the problem object

68 * used by the MIP solver. */

70 glp_prob *glp_ios_get_prob(glp_tree *tree)

71 { return

72 tree->mip;

73 }

75 /***********************************************************************

76 * NAME

77 *

78 * glp_ios_tree_size - determine size of the branch-and-bound tree

79 *

80 * SYNOPSIS

81 *

82 * void glp_ios_tree_size(glp_tree *tree, int *a_cnt, int *n_cnt,

83 * int *t_cnt);

84 *

85 * DESCRIPTION

86 *

87 * The routine glp_ios_tree_size stores the following three counts which

88 * characterize the current size of the branch-and-bound tree:

89 *

90 * a_cnt is the current number of active nodes, i.e. the current size of

91 * the active list;

92 *

93 * n_cnt is the current number of all (active and inactive) nodes;

94 *

95 * t_cnt is the total number of nodes including those which have been

96 * already removed from the tree. This count is increased whenever

97 * a new node appears in the tree and never decreased.

98 *

99 * If some of the parameters a_cnt, n_cnt, t_cnt is a null pointer, the

100 * corresponding count is not stored. */

101

102 void glp_ios_tree_size(glp_tree *tree, int *a_cnt, int *n_cnt,

103 int *t_cnt)

104 { if (a_cnt != NULL) *a_cnt = tree->a_cnt;

105 if (n_cnt != NULL) *n_cnt = tree->n_cnt;

106 if (t_cnt != NULL) *t_cnt = tree->t_cnt;

107 return;

108 }

109

110 /***********************************************************************

111 * NAME

112 *

113 * glp_ios_curr_node - determine current active subproblem

114 *

115 * SYNOPSIS

116 *

117 * int glp_ios_curr_node(glp_tree *tree);

118 *

119 * RETURNS

120 *

121 * The routine glp_ios_curr_node returns the reference number of the

122 * current active subproblem. However, if the current subproblem does

123 * not exist, the routine returns zero. */

124

125 int glp_ios_curr_node(glp_tree *tree)

126 { IOSNPD *node;

127 /* obtain pointer to the current subproblem */

128 node = tree->curr;

129 /* return its reference number */

130 return node == NULL ? 0 : node->p;

131 }

132

133 /***********************************************************************

134 * NAME

135 *

136 * glp_ios_next_node - determine next active subproblem

137 *

138 * SYNOPSIS

139 *

140 * int glp_ios_next_node(glp_tree *tree, int p);

141 *

142 * RETURNS

143 *

144 * If the parameter p is zero, the routine glp_ios_next_node returns

145 * the reference number of the first active subproblem. However, if the

146 * tree is empty, zero is returned.

147 *

148 * If the parameter p is not zero, it must specify the reference number

149 * of some active subproblem, in which case the routine returns the

150 * reference number of the next active subproblem. However, if there is

151 * no next active subproblem in the list, zero is returned.

152 *

153 * All subproblems in the active list are ordered chronologically, i.e.

154 * subproblem A precedes subproblem B if A was created before B. */

155

156 int glp_ios_next_node(glp_tree *tree, int p)

157 { IOSNPD *node;

158 if (p == 0)

159 { /* obtain pointer to the first active subproblem */

160 node = tree->head;

161 }

162 else

163 { /* obtain pointer to the specified subproblem */

164 if (!(1 <= p && p <= tree->nslots))

165 err: xerror("glp_ios_next_node: p = %d; invalid subproblem refer"

166 "ence number\n", p);

167 node = tree->slot[p].node;

168 if (node == NULL) goto err;

169 /* the specified subproblem must be active */

170 if (node->count != 0)

171 xerror("glp_ios_next_node: p = %d; subproblem not in the ac"

172 "tive list\n", p);

173 /* obtain pointer to the next active subproblem */

174 node = node->next;

175 }

176 /* return the reference number */

177 return node == NULL ? 0 : node->p;

178 }

179

180 /***********************************************************************

181 * NAME

182 *

183 * glp_ios_prev_node - determine previous active subproblem

184 *

185 * SYNOPSIS

186 *

187 * int glp_ios_prev_node(glp_tree *tree, int p);

188 *

189 * RETURNS

190 *

191 * If the parameter p is zero, the routine glp_ios_prev_node returns

192 * the reference number of the last active subproblem. However, if the

193 * tree is empty, zero is returned.

194 *

195 * If the parameter p is not zero, it must specify the reference number

196 * of some active subproblem, in which case the routine returns the

197 * reference number of the previous active subproblem. However, if there

198 * is no previous active subproblem in the list, zero is returned.

199 *

200 * All subproblems in the active list are ordered chronologically, i.e.

201 * subproblem A precedes subproblem B if A was created before B. */

202

203 int glp_ios_prev_node(glp_tree *tree, int p)

204 { IOSNPD *node;

205 if (p == 0)

206 { /* obtain pointer to the last active subproblem */

207 node = tree->tail;

208 }

209 else

210 { /* obtain pointer to the specified subproblem */

211 if (!(1 <= p && p <= tree->nslots))

212 err: xerror("glp_ios_prev_node: p = %d; invalid subproblem refer"

213 "ence number\n", p);

214 node = tree->slot[p].node;

215 if (node == NULL) goto err;

216 /* the specified subproblem must be active */

217 if (node->count != 0)

218 xerror("glp_ios_prev_node: p = %d; subproblem not in the ac"

219 "tive list\n", p);

220 /* obtain pointer to the previous active subproblem */

221 node = node->prev;

222 }

223 /* return the reference number */

224 return node == NULL ? 0 : node->p;

225 }

226

227 /***********************************************************************

228 * NAME

229 *

230 * glp_ios_up_node - determine parent subproblem

231 *

232 * SYNOPSIS

233 *

234 * int glp_ios_up_node(glp_tree *tree, int p);

235 *

236 * RETURNS

237 *

238 * The parameter p must specify the reference number of some (active or

239 * inactive) subproblem, in which case the routine iet_get_up_node

240 * returns the reference number of its parent subproblem. However, if

241 * the specified subproblem is the root of the tree and, therefore, has

242 * no parent, the routine returns zero. */

243

244 int glp_ios_up_node(glp_tree *tree, int p)

245 { IOSNPD *node;

246 /* obtain pointer to the specified subproblem */

247 if (!(1 <= p && p <= tree->nslots))

248 err: xerror("glp_ios_up_node: p = %d; invalid subproblem reference "

249 "number\n", p);

250 node = tree->slot[p].node;

251 if (node == NULL) goto err;

252 /* obtain pointer to the parent subproblem */

253 node = node->up;

254 /* return the reference number */

255 return node == NULL ? 0 : node->p;

256 }

257

258 /***********************************************************************

259 * NAME

260 *

261 * glp_ios_node_level - determine subproblem level

262 *

263 * SYNOPSIS

264 *

265 * int glp_ios_node_level(glp_tree *tree, int p);

266 *

267 * RETURNS

268 *

269 * The routine glp_ios_node_level returns the level of the subproblem,

270 * whose reference number is p, in the branch-and-bound tree. (The root

271 * subproblem has level 0, and the level of any other subproblem is the

272 * level of its parent plus one.) */

273

274 int glp_ios_node_level(glp_tree *tree, int p)

275 { IOSNPD *node;

276 /* obtain pointer to the specified subproblem */

277 if (!(1 <= p && p <= tree->nslots))

278 err: xerror("glp_ios_node_level: p = %d; invalid subproblem referen"

279 "ce number\n", p);

280 node = tree->slot[p].node;

281 if (node == NULL) goto err;

282 /* return the node level */

283 return node->level;

284 }

285

286 /***********************************************************************

287 * NAME

288 *

289 * glp_ios_node_bound - determine subproblem local bound

290 *

291 * SYNOPSIS

292 *

293 * double glp_ios_node_bound(glp_tree *tree, int p);

294 *

295 * RETURNS

296 *

297 * The routine glp_ios_node_bound returns the local bound for (active or

298 * inactive) subproblem, whose reference number is p.

299 *

300 * COMMENTS

301 *

302 * The local bound for subproblem p is an lower (minimization) or upper

303 * (maximization) bound for integer optimal solution to this subproblem

304 * (not to the original problem). This bound is local in the sense that

305 * only subproblems in the subtree rooted at node p cannot have better

306 * integer feasible solutions.

307 *

308 * On creating a subproblem (due to the branching step) its local bound

309 * is inherited from its parent and then may get only stronger (never

310 * weaker). For the root subproblem its local bound is initially set to

311 * -DBL_MAX (minimization) or +DBL_MAX (maximization) and then improved

312 * as the root LP relaxation has been solved.

313 *

314 * Note that the local bound is not necessarily the optimal objective

315 * value to corresponding LP relaxation; it may be stronger. */

316

317 double glp_ios_node_bound(glp_tree *tree, int p)

318 { IOSNPD *node;

319 /* obtain pointer to the specified subproblem */

320 if (!(1 <= p && p <= tree->nslots))

321 err: xerror("glp_ios_node_bound: p = %d; invalid subproblem referen"

322 "ce number\n", p);

323 node = tree->slot[p].node;

324 if (node == NULL) goto err;

325 /* return the node local bound */

326 return node->bound;

327 }

328

329 /***********************************************************************

330 * NAME

331 *

332 * glp_ios_best_node - find active subproblem with best local bound

333 *

334 * SYNOPSIS

335 *

336 * int glp_ios_best_node(glp_tree *tree);

337 *

338 * RETURNS

339 *

340 * The routine glp_ios_best_node returns the reference number of the

341 * active subproblem, whose local bound is best (i.e. smallest in case

342 * of minimization or largest in case of maximization). However, if the

343 * tree is empty, the routine returns zero.

344 *

345 * COMMENTS

346 *

347 * The best local bound is an lower (minimization) or upper

348 * (maximization) bound for integer optimal solution to the original

349 * MIP problem. */

350

351 int glp_ios_best_node(glp_tree *tree)

352 { return

353 ios_best_node(tree);

354 }

355

356 /***********************************************************************

357 * NAME

358 *

359 * glp_ios_mip_gap - compute relative MIP gap

360 *

361 * SYNOPSIS

362 *

363 * double glp_ios_mip_gap(glp_tree *tree);

364 *

365 * DESCRIPTION

366 *

367 * The routine glp_ios_mip_gap computes the relative MIP gap with the

368 * following formula:

369 *

370 * gap = |best_mip - best_bnd| / (|best_mip| + DBL_EPSILON),

371 *

372 * where best_mip is the best integer feasible solution found so far,

373 * best_bnd is the best (global) bound. If no integer feasible solution

374 * has been found yet, gap is set to DBL_MAX.

375 *

376 * RETURNS

377 *

378 * The routine glp_ios_mip_gap returns the relative MIP gap. */

379

380 double glp_ios_mip_gap(glp_tree *tree)

381 { return

382 ios_relative_gap(tree);

383 }

384

385 /***********************************************************************

386 * NAME

387 *

388 * glp_ios_node_data - access subproblem application-specific data

389 *

390 * SYNOPSIS

391 *

392 * void *glp_ios_node_data(glp_tree *tree, int p);

393 *

394 * DESCRIPTION

395 *

396 * The routine glp_ios_node_data allows the application accessing a

397 * memory block allocated for the subproblem (which may be active or

398 * inactive), whose reference number is p.

399 *

400 * The size of the block is defined by the control parameter cb_size

401 * passed to the routine glp_intopt. The block is initialized by binary

402 * zeros on creating corresponding subproblem, and its contents is kept

403 * until the subproblem will be removed from the tree.

404 *

405 * The application may use these memory blocks to store specific data

406 * for each subproblem.

407 *

408 * RETURNS

409 *

410 * The routine glp_ios_node_data returns a pointer to the memory block

411 * for the specified subproblem. Note that if cb_size = 0, the routine

412 * returns a null pointer. */

413

414 void *glp_ios_node_data(glp_tree *tree, int p)

415 { IOSNPD *node;

416 /* obtain pointer to the specified subproblem */

417 if (!(1 <= p && p <= tree->nslots))

418 err: xerror("glp_ios_node_level: p = %d; invalid subproblem referen"

419 "ce number\n", p);

420 node = tree->slot[p].node;

421 if (node == NULL) goto err;

422 /* return pointer to the application-specific data */

423 return node->data;

424 }

425

426 /***********************************************************************

427 * NAME

428 *

429 * glp_ios_row_attr - retrieve additional row attributes

430 *

431 * SYNOPSIS

432 *

433 * void glp_ios_row_attr(glp_tree *tree, int i, glp_attr *attr);

434 *

435 * DESCRIPTION

436 *

437 * The routine glp_ios_row_attr retrieves additional attributes of row

438 * i and stores them in the structure glp_attr. */

439

440 void glp_ios_row_attr(glp_tree *tree, int i, glp_attr *attr)

441 { GLPROW *row;

442 if (!(1 <= i && i <= tree->mip->m))

443 xerror("glp_ios_row_attr: i = %d; row number out of range\n",

444 i);

445 row = tree->mip->row[i];

446 attr->level = row->level;

447 attr->origin = row->origin;

448 attr->klass = row->klass;

449 return;

450 }

451

452 /**********************************************************************/

453

454 int glp_ios_pool_size(glp_tree *tree)

455 { /* determine current size of the cut pool */

456 if (tree->reason != GLP_ICUTGEN)

457 xerror("glp_ios_pool_size: operation not allowed\n");

458 xassert(tree->local != NULL);

459 return tree->local->size;

460 }

461

462 /**********************************************************************/

463

464 int glp_ios_add_row(glp_tree *tree,

465 const char *name, int klass, int flags, int len, const int ind[],

466 const double val[], int type, double rhs)

467 { /* add row (constraint) to the cut pool */

468 int num;

469 if (tree->reason != GLP_ICUTGEN)

470 xerror("glp_ios_add_row: operation not allowed\n");

471 xassert(tree->local != NULL);

472 num = ios_add_row(tree, tree->local, name, klass, flags, len,

473 ind, val, type, rhs);

474 return num;

475 }

476

477 /**********************************************************************/

478

479 void glp_ios_del_row(glp_tree *tree, int i)

480 { /* remove row (constraint) from the cut pool */

481 if (tree->reason != GLP_ICUTGEN)

482 xerror("glp_ios_del_row: operation not allowed\n");

483 ios_del_row(tree, tree->local, i);

484 return;

485 }

486

487 /**********************************************************************/

488

489 void glp_ios_clear_pool(glp_tree *tree)

490 { /* remove all rows (constraints) from the cut pool */

491 if (tree->reason != GLP_ICUTGEN)

492 xerror("glp_ios_clear_pool: operation not allowed\n");

493 ios_clear_pool(tree, tree->local);

494 return;

495 }

496

497 /***********************************************************************

498 * NAME

499 *

500 * glp_ios_can_branch - check if can branch upon specified variable

501 *

502 * SYNOPSIS

503 *

504 * int glp_ios_can_branch(glp_tree *tree, int j);

505 *

506 * RETURNS

507 *

508 * If j-th variable (column) can be used to branch upon, the routine

509 * glp_ios_can_branch returns non-zero, otherwise zero. */

510

511 int glp_ios_can_branch(glp_tree *tree, int j)

512 { if (!(1 <= j && j <= tree->mip->n))

513 xerror("glp_ios_can_branch: j = %d; column number out of range"

514 "\n", j);

515 return tree->non_int[j];

516 }

517

518 /***********************************************************************

519 * NAME

520 *

521 * glp_ios_branch_upon - choose variable to branch upon

522 *

523 * SYNOPSIS

524 *

525 * void glp_ios_branch_upon(glp_tree *tree, int j, int sel);

526 *

527 * DESCRIPTION

528 *

529 * The routine glp_ios_branch_upon can be called from the user-defined

530 * callback routine in response to the reason GLP_IBRANCH to choose a

531 * branching variable, whose ordinal number is j. Should note that only

532 * variables, for which the routine glp_ios_can_branch returns non-zero,

533 * can be used to branch upon.

534 *

535 * The parameter sel is a flag that indicates which branch (subproblem)

536 * should be selected next to continue the search:

537 *

538 * GLP_DN_BRNCH - select down-branch;

539 * GLP_UP_BRNCH - select up-branch;

540 * GLP_NO_BRNCH - use general selection technique. */

541

542 void glp_ios_branch_upon(glp_tree *tree, int j, int sel)

543 { if (!(1 <= j && j <= tree->mip->n))

544 xerror("glp_ios_branch_upon: j = %d; column number out of rang"

545 "e\n", j);

546 if (!(sel == GLP_DN_BRNCH || sel == GLP_UP_BRNCH ||

547 sel == GLP_NO_BRNCH))

548 xerror("glp_ios_branch_upon: sel = %d: invalid branch selectio"

549 "n flag\n", sel);

550 if (!(tree->non_int[j]))

551 xerror("glp_ios_branch_upon: j = %d; variable cannot be used t"

552 "o branch upon\n", j);

553 if (tree->br_var != 0)

554 xerror("glp_ios_branch_upon: branching variable already chosen"

555 "\n");

556 tree->br_var = j;

557 tree->br_sel = sel;

558 return;

559 }

560

561 /***********************************************************************

562 * NAME

563 *

564 * glp_ios_select_node - select subproblem to continue the search

565 *

566 * SYNOPSIS

567 *

568 * void glp_ios_select_node(glp_tree *tree, int p);

569 *

570 * DESCRIPTION

571 *

572 * The routine glp_ios_select_node can be called from the user-defined

573 * callback routine in response to the reason GLP_ISELECT to select an

574 * active subproblem, whose reference number is p. The search will be

575 * continued from the subproblem selected. */

576

577 void glp_ios_select_node(glp_tree *tree, int p)

578 { IOSNPD *node;

579 /* obtain pointer to the specified subproblem */

580 if (!(1 <= p && p <= tree->nslots))

581 err: xerror("glp_ios_select_node: p = %d; invalid subproblem refere"

582 "nce number\n", p);

583 node = tree->slot[p].node;

584 if (node == NULL) goto err;

585 /* the specified subproblem must be active */

586 if (node->count != 0)

587 xerror("glp_ios_select_node: p = %d; subproblem not in the act"

588 "ive list\n", p);

589 /* no subproblem must be selected yet */

590 if (tree->next_p != 0)

591 xerror("glp_ios_select_node: subproblem already selected\n");

592 /* select the specified subproblem to continue the search */

593 tree->next_p = p;

594 return;

595 }

596

597 /***********************************************************************

598 * NAME

599 *

600 * glp_ios_heur_sol - provide solution found by heuristic

601 *

602 * SYNOPSIS

603 *

604 * int glp_ios_heur_sol(glp_tree *tree, const double x[]);

605 *

606 * DESCRIPTION

607 *

608 * The routine glp_ios_heur_sol can be called from the user-defined

609 * callback routine in response to the reason GLP_IHEUR to provide an

610 * integer feasible solution found by a primal heuristic.

611 *

612 * Primal values of *all* variables (columns) found by the heuristic

613 * should be placed in locations x[1], ..., x[n], where n is the number

614 * of columns in the original problem object. Note that the routine

615 * glp_ios_heur_sol *does not* check primal feasibility of the solution

616 * provided.

617 *

618 * Using the solution passed in the array x the routine computes value

619 * of the objective function. If the objective value is better than the

620 * best known integer feasible solution, the routine computes values of

621 * auxiliary variables (rows) and stores all solution components in the

622 * problem object.

623 *

624 * RETURNS

625 *

626 * If the provided solution is accepted, the routine glp_ios_heur_sol

627 * returns zero. Otherwise, if the provided solution is rejected, the

628 * routine returns non-zero. */

629

630 int glp_ios_heur_sol(glp_tree *tree, const double x[])

631 { glp_prob *mip = tree->mip;

632 int m = tree->orig_m;

633 int n = tree->n;

634 int i, j;

635 double obj;

636 xassert(mip->m >= m);

637 xassert(mip->n == n);

638 /* check values of integer variables and compute value of the

639 objective function */

640 obj = mip->c0;

641 for (j = 1; j <= n; j++)

642 { GLPCOL *col = mip->col[j];

643 if (col->kind == GLP_IV)

644 { /* provided value must be integral */

645 if (x[j] != floor(x[j])) return 1;

646 }

647 obj += col->coef * x[j];

648 }

649 /* check if the provided solution is better than the best known

650 integer feasible solution */

651 if (mip->mip_stat == GLP_FEAS)

652 { switch (mip->dir)

653 { case GLP_MIN:

654 if (obj >= tree->mip->mip_obj) return 1;

655 break;

656 case GLP_MAX:

657 if (obj <= tree->mip->mip_obj) return 1;

658 break;

659 default:

660 xassert(mip != mip);

661 }

662 }

663 /* it is better; store it in the problem object */

664 if (tree->parm->msg_lev >= GLP_MSG_ON)

665 xprintf("Solution found by heuristic: %.12g\n", obj);

666 mip->mip_stat = GLP_FEAS;

667 mip->mip_obj = obj;

668 for (j = 1; j <= n; j++)

669 mip->col[j]->mipx = x[j];

670 for (i = 1; i <= m; i++)

671 { GLPROW *row = mip->row[i];

672 GLPAIJ *aij;

673 row->mipx = 0.0;

674 for (aij = row->ptr; aij != NULL; aij = aij->r_next)

675 row->mipx += aij->val * aij->col->mipx;

676 }

677 return 0;

678 }

679

680 /***********************************************************************

681 * NAME

682 *

683 * glp_ios_terminate - terminate the solution process.

684 *

685 * SYNOPSIS

686 *

687 * void glp_ios_terminate(glp_tree *tree);

688 *

689 * DESCRIPTION

690 *

691 * The routine glp_ios_terminate sets a flag indicating that the MIP

692 * solver should prematurely terminate the search. */

693

694 void glp_ios_terminate(glp_tree *tree)

695 { if (tree->parm->msg_lev >= GLP_MSG_DBG)

696 xprintf("The search is prematurely terminated due to applicati"

697 "on request\n");

698 tree->stop = 1;

699 return;

700 }

701

702 /* eof */