COIN-OR::LEMON - Graph Library

source: glpk-cmake/src/glpapi13.c @ 2:4c8956a7bdf4

Last change on this file since 2:4c8956a7bdf4 was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 14 years ago

Import glpk-4.45

  • Generated files and doc/notes are removed
File size: 22.3 KB
Line 
1/* glpapi13.c (branch-and-bound interface routines) */
2
3/***********************************************************************
4*  This code is part of GLPK (GNU Linear Programming Kit).
5*
6*  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
7*  2009, 2010 Andrew Makhorin, Department for Applied Informatics,
8*  Moscow Aviation Institute, Moscow, Russia. All rights reserved.
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***********************************************************************/
24
25#include "glpios.h"
26
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. */
40
41int glp_ios_reason(glp_tree *tree)
42{     return
43         tree->reason;
44}
45
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. */
69
70glp_prob *glp_ios_get_prob(glp_tree *tree)
71{     return
72         tree->mip;
73}
74
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
102void 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
125int 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
156int 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))
165err:        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
203int 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))
212err:        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
244int 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))
248err:     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
274int 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))
278err:     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
317double 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))
321err:     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
351int 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
380double 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
414void *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))
418err:     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
440void 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
454int 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
464int 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
479void 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
489void 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
511int 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
542void 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
577void 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))
581err:     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
630int 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
694void 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 */
Note: See TracBrowser for help on using the repository browser.