/* glpios01.c */ /*********************************************************************** * This code is part of GLPK (GNU Linear Programming Kit). * * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, * 2009, 2010 Andrew Makhorin, Department for Applied Informatics, * Moscow Aviation Institute, Moscow, Russia. All rights reserved. * E-mail: . * * GLPK is free software: you can redistribute it and/or modify it * under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * GLPK is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public * License for more details. * * You should have received a copy of the GNU General Public License * along with GLPK. If not, see . ***********************************************************************/ #include "glpios.h" /*********************************************************************** * NAME * * ios_create_tree - create branch-and-bound tree * * SYNOPSIS * * #include "glpios.h" * glp_tree *ios_create_tree(glp_prob *mip, const glp_iocp *parm); * * DESCRIPTION * * The routine ios_create_tree creates the branch-and-bound tree. * * Being created the tree consists of the only root subproblem whose * reference number is 1. Note that initially the root subproblem is in * frozen state and therefore needs to be revived. * * RETURNS * * The routine returns a pointer to the tree created. */ static IOSNPD *new_node(glp_tree *tree, IOSNPD *parent); glp_tree *ios_create_tree(glp_prob *mip, const glp_iocp *parm) { int m = mip->m; int n = mip->n; glp_tree *tree; int i, j; xassert(mip->tree == NULL); mip->tree = tree = xmalloc(sizeof(glp_tree)); tree->pool = dmp_create_pool(); tree->n = n; /* save original problem components */ tree->orig_m = m; tree->orig_type = xcalloc(1+m+n, sizeof(char)); tree->orig_lb = xcalloc(1+m+n, sizeof(double)); tree->orig_ub = xcalloc(1+m+n, sizeof(double)); tree->orig_stat = xcalloc(1+m+n, sizeof(char)); tree->orig_prim = xcalloc(1+m+n, sizeof(double)); tree->orig_dual = xcalloc(1+m+n, sizeof(double)); for (i = 1; i <= m; i++) { GLPROW *row = mip->row[i]; tree->orig_type[i] = (char)row->type; tree->orig_lb[i] = row->lb; tree->orig_ub[i] = row->ub; tree->orig_stat[i] = (char)row->stat; tree->orig_prim[i] = row->prim; tree->orig_dual[i] = row->dual; } for (j = 1; j <= n; j++) { GLPCOL *col = mip->col[j]; tree->orig_type[m+j] = (char)col->type; tree->orig_lb[m+j] = col->lb; tree->orig_ub[m+j] = col->ub; tree->orig_stat[m+j] = (char)col->stat; tree->orig_prim[m+j] = col->prim; tree->orig_dual[m+j] = col->dual; } tree->orig_obj = mip->obj_val; /* initialize the branch-and-bound tree */ tree->nslots = 0; tree->avail = 0; tree->slot = NULL; tree->head = tree->tail = NULL; tree->a_cnt = tree->n_cnt = tree->t_cnt = 0; /* the root subproblem is not solved yet, so its final components are unknown so far */ tree->root_m = 0; tree->root_type = NULL; tree->root_lb = tree->root_ub = NULL; tree->root_stat = NULL; /* the current subproblem does not exist yet */ tree->curr = NULL; tree->mip = mip; /*tree->solved = 0;*/ tree->non_int = xcalloc(1+n, sizeof(char)); memset(&tree->non_int[1], 0, n); /* arrays to save parent subproblem components will be allocated later */ tree->pred_m = tree->pred_max = 0; tree->pred_type = NULL; tree->pred_lb = tree->pred_ub = NULL; tree->pred_stat = NULL; /* cut generator */ tree->local = ios_create_pool(tree); /*tree->first_attempt = 1;*/ /*tree->max_added_cuts = 0;*/ /*tree->min_eff = 0.0;*/ /*tree->miss = 0;*/ /*tree->just_selected = 0;*/ tree->mir_gen = NULL; tree->clq_gen = NULL; /*tree->round = 0;*/ #if 0 /* create the conflict graph */ tree->n_ref = xcalloc(1+n, sizeof(int)); memset(&tree->n_ref[1], 0, n * sizeof(int)); tree->c_ref = xcalloc(1+n, sizeof(int)); memset(&tree->c_ref[1], 0, n * sizeof(int)); tree->g = scg_create_graph(0); tree->j_ref = xcalloc(1+tree->g->n_max, sizeof(int)); #endif /* pseudocost branching */ tree->pcost = NULL; tree->iwrk = xcalloc(1+n, sizeof(int)); tree->dwrk = xcalloc(1+n, sizeof(double)); /* initialize control parameters */ tree->parm = parm; tree->tm_beg = xtime(); tree->tm_lag = xlset(0); tree->sol_cnt = 0; /* initialize advanced solver interface */ tree->reason = 0; tree->reopt = 0; tree->reinv = 0; tree->br_var = 0; tree->br_sel = 0; tree->child = 0; tree->next_p = 0; /*tree->btrack = NULL;*/ tree->stop = 0; /* create the root subproblem, which initially is identical to the original MIP */ new_node(tree, NULL); return tree; } /*********************************************************************** * NAME * * ios_revive_node - revive specified subproblem * * SYNOPSIS * * #include "glpios.h" * void ios_revive_node(glp_tree *tree, int p); * * DESCRIPTION * * The routine ios_revive_node revives the specified subproblem, whose * reference number is p, and thereby makes it the current subproblem. * Note that the specified subproblem must be active. Besides, if the * current subproblem already exists, it must be frozen before reviving * another subproblem. */ void ios_revive_node(glp_tree *tree, int p) { glp_prob *mip = tree->mip; IOSNPD *node, *root; /* obtain pointer to the specified subproblem */ xassert(1 <= p && p <= tree->nslots); node = tree->slot[p].node; xassert(node != NULL); /* the specified subproblem must be active */ xassert(node->count == 0); /* the current subproblem must not exist */ xassert(tree->curr == NULL); /* the specified subproblem becomes current */ tree->curr = node; /*tree->solved = 0;*/ /* obtain pointer to the root subproblem */ root = tree->slot[1].node; xassert(root != NULL); /* at this point problem object components correspond to the root subproblem, so if the root subproblem should be revived, there is nothing more to do */ if (node == root) goto done; xassert(mip->m == tree->root_m); /* build path from the root to the current node */ node->temp = NULL; for (node = node; node != NULL; node = node->up) { if (node->up == NULL) xassert(node == root); else node->up->temp = node; } /* go down from the root to the current node and make necessary changes to restore components of the current subproblem */ for (node = root; node != NULL; node = node->temp) { int m = mip->m; int n = mip->n; /* if the current node is reached, the problem object at this point corresponds to its parent, so save attributes of rows and columns for the parent subproblem */ if (node->temp == NULL) { int i, j; tree->pred_m = m; /* allocate/reallocate arrays, if necessary */ if (tree->pred_max < m + n) { int new_size = m + n + 100; if (tree->pred_type != NULL) xfree(tree->pred_type); if (tree->pred_lb != NULL) xfree(tree->pred_lb); if (tree->pred_ub != NULL) xfree(tree->pred_ub); if (tree->pred_stat != NULL) xfree(tree->pred_stat); tree->pred_max = new_size; tree->pred_type = xcalloc(1+new_size, sizeof(char)); tree->pred_lb = xcalloc(1+new_size, sizeof(double)); tree->pred_ub = xcalloc(1+new_size, sizeof(double)); tree->pred_stat = xcalloc(1+new_size, sizeof(char)); } /* save row attributes */ for (i = 1; i <= m; i++) { GLPROW *row = mip->row[i]; tree->pred_type[i] = (char)row->type; tree->pred_lb[i] = row->lb; tree->pred_ub[i] = row->ub; tree->pred_stat[i] = (char)row->stat; } /* save column attributes */ for (j = 1; j <= n; j++) { GLPCOL *col = mip->col[j]; tree->pred_type[mip->m+j] = (char)col->type; tree->pred_lb[mip->m+j] = col->lb; tree->pred_ub[mip->m+j] = col->ub; tree->pred_stat[mip->m+j] = (char)col->stat; } } /* change bounds of rows and columns */ { IOSBND *b; for (b = node->b_ptr; b != NULL; b = b->next) { if (b->k <= m) glp_set_row_bnds(mip, b->k, b->type, b->lb, b->ub); else glp_set_col_bnds(mip, b->k-m, b->type, b->lb, b->ub); } } /* change statuses of rows and columns */ { IOSTAT *s; for (s = node->s_ptr; s != NULL; s = s->next) { if (s->k <= m) glp_set_row_stat(mip, s->k, s->stat); else glp_set_col_stat(mip, s->k-m, s->stat); } } /* add new rows */ if (node->r_ptr != NULL) { IOSROW *r; IOSAIJ *a; int i, len, *ind; double *val; ind = xcalloc(1+n, sizeof(int)); val = xcalloc(1+n, sizeof(double)); for (r = node->r_ptr; r != NULL; r = r->next) { i = glp_add_rows(mip, 1); glp_set_row_name(mip, i, r->name); #if 1 /* 20/IX-2008 */ xassert(mip->row[i]->level == 0); mip->row[i]->level = node->level; mip->row[i]->origin = r->origin; mip->row[i]->klass = r->klass; #endif glp_set_row_bnds(mip, i, r->type, r->lb, r->ub); len = 0; for (a = r->ptr; a != NULL; a = a->next) len++, ind[len] = a->j, val[len] = a->val; glp_set_mat_row(mip, i, len, ind, val); glp_set_rii(mip, i, r->rii); glp_set_row_stat(mip, i, r->stat); } xfree(ind); xfree(val); } #if 0 /* add new edges to the conflict graph */ /* add new cliques to the conflict graph */ /* (not implemented yet) */ xassert(node->own_nn == 0); xassert(node->own_nc == 0); xassert(node->e_ptr == NULL); #endif } /* the specified subproblem has been revived */ node = tree->curr; /* delete its bound change list */ while (node->b_ptr != NULL) { IOSBND *b; b = node->b_ptr; node->b_ptr = b->next; dmp_free_atom(tree->pool, b, sizeof(IOSBND)); } /* delete its status change list */ while (node->s_ptr != NULL) { IOSTAT *s; s = node->s_ptr; node->s_ptr = s->next; dmp_free_atom(tree->pool, s, sizeof(IOSTAT)); } #if 1 /* 20/XI-2009 */ /* delete its row addition list (additional rows may appear, for example, due to branching on GUB constraints */ while (node->r_ptr != NULL) { IOSROW *r; r = node->r_ptr; node->r_ptr = r->next; xassert(r->name == NULL); while (r->ptr != NULL) { IOSAIJ *a; a = r->ptr; r->ptr = a->next; dmp_free_atom(tree->pool, a, sizeof(IOSAIJ)); } dmp_free_atom(tree->pool, r, sizeof(IOSROW)); } #endif done: return; } /*********************************************************************** * NAME * * ios_freeze_node - freeze current subproblem * * SYNOPSIS * * #include "glpios.h" * void ios_freeze_node(glp_tree *tree); * * DESCRIPTION * * The routine ios_freeze_node freezes the current subproblem. */ void ios_freeze_node(glp_tree *tree) { glp_prob *mip = tree->mip; int m = mip->m; int n = mip->n; IOSNPD *node; /* obtain pointer to the current subproblem */ node = tree->curr; xassert(node != NULL); if (node->up == NULL) { /* freeze the root subproblem */ int k; xassert(node->p == 1); xassert(tree->root_m == 0); xassert(tree->root_type == NULL); xassert(tree->root_lb == NULL); xassert(tree->root_ub == NULL); xassert(tree->root_stat == NULL); tree->root_m = m; tree->root_type = xcalloc(1+m+n, sizeof(char)); tree->root_lb = xcalloc(1+m+n, sizeof(double)); tree->root_ub = xcalloc(1+m+n, sizeof(double)); tree->root_stat = xcalloc(1+m+n, sizeof(char)); for (k = 1; k <= m+n; k++) { if (k <= m) { GLPROW *row = mip->row[k]; tree->root_type[k] = (char)row->type; tree->root_lb[k] = row->lb; tree->root_ub[k] = row->ub; tree->root_stat[k] = (char)row->stat; } else { GLPCOL *col = mip->col[k-m]; tree->root_type[k] = (char)col->type; tree->root_lb[k] = col->lb; tree->root_ub[k] = col->ub; tree->root_stat[k] = (char)col->stat; } } } else { /* freeze non-root subproblem */ int root_m = tree->root_m; int pred_m = tree->pred_m; int i, j, k; xassert(pred_m <= m); /* build change lists for rows and columns which exist in the parent subproblem */ xassert(node->b_ptr == NULL); xassert(node->s_ptr == NULL); for (k = 1; k <= pred_m + n; k++) { int pred_type, pred_stat, type, stat; double pred_lb, pred_ub, lb, ub; /* determine attributes in the parent subproblem */ pred_type = tree->pred_type[k]; pred_lb = tree->pred_lb[k]; pred_ub = tree->pred_ub[k]; pred_stat = tree->pred_stat[k]; /* determine attributes in the current subproblem */ if (k <= pred_m) { GLPROW *row = mip->row[k]; type = row->type; lb = row->lb; ub = row->ub; stat = row->stat; } else { GLPCOL *col = mip->col[k - pred_m]; type = col->type; lb = col->lb; ub = col->ub; stat = col->stat; } /* save type and bounds of a row/column, if changed */ if (!(pred_type == type && pred_lb == lb && pred_ub == ub)) { IOSBND *b; b = dmp_get_atom(tree->pool, sizeof(IOSBND)); b->k = k; b->type = (unsigned char)type; b->lb = lb; b->ub = ub; b->next = node->b_ptr; node->b_ptr = b; } /* save status of a row/column, if changed */ if (pred_stat != stat) { IOSTAT *s; s = dmp_get_atom(tree->pool, sizeof(IOSTAT)); s->k = k; s->stat = (unsigned char)stat; s->next = node->s_ptr; node->s_ptr = s; } } /* save new rows added to the current subproblem */ xassert(node->r_ptr == NULL); if (pred_m < m) { int i, len, *ind; double *val; ind = xcalloc(1+n, sizeof(int)); val = xcalloc(1+n, sizeof(double)); for (i = m; i > pred_m; i--) { GLPROW *row = mip->row[i]; IOSROW *r; const char *name; r = dmp_get_atom(tree->pool, sizeof(IOSROW)); name = glp_get_row_name(mip, i); if (name == NULL) r->name = NULL; else { r->name = dmp_get_atom(tree->pool, strlen(name)+1); strcpy(r->name, name); } #if 1 /* 20/IX-2008 */ r->origin = row->origin; r->klass = row->klass; #endif r->type = (unsigned char)row->type; r->lb = row->lb; r->ub = row->ub; r->ptr = NULL; len = glp_get_mat_row(mip, i, ind, val); for (k = 1; k <= len; k++) { IOSAIJ *a; a = dmp_get_atom(tree->pool, sizeof(IOSAIJ)); a->j = ind[k]; a->val = val[k]; a->next = r->ptr; r->ptr = a; } r->rii = row->rii; r->stat = (unsigned char)row->stat; r->next = node->r_ptr; node->r_ptr = r; } xfree(ind); xfree(val); } /* remove all rows missing in the root subproblem */ if (m != root_m) { int nrs, *num; nrs = m - root_m; xassert(nrs > 0); num = xcalloc(1+nrs, sizeof(int)); for (i = 1; i <= nrs; i++) num[i] = root_m + i; glp_del_rows(mip, nrs, num); xfree(num); } m = mip->m; /* and restore attributes of all rows and columns for the root subproblem */ xassert(m == root_m); for (i = 1; i <= m; i++) { glp_set_row_bnds(mip, i, tree->root_type[i], tree->root_lb[i], tree->root_ub[i]); glp_set_row_stat(mip, i, tree->root_stat[i]); } for (j = 1; j <= n; j++) { glp_set_col_bnds(mip, j, tree->root_type[m+j], tree->root_lb[m+j], tree->root_ub[m+j]); glp_set_col_stat(mip, j, tree->root_stat[m+j]); } #if 1 /* remove all edges and cliques missing in the conflict graph for the root subproblem */ /* (not implemented yet) */ #endif } /* the current subproblem has been frozen */ tree->curr = NULL; return; } /*********************************************************************** * NAME * * ios_clone_node - clone specified subproblem * * SYNOPSIS * * #include "glpios.h" * void ios_clone_node(glp_tree *tree, int p, int nnn, int ref[]); * * DESCRIPTION * * The routine ios_clone_node clones the specified subproblem, whose * reference number is p, creating its nnn exact copies. Note that the * specified subproblem must be active and must be in the frozen state * (i.e. it must not be the current subproblem). * * Each clone, an exact copy of the specified subproblem, becomes a new * active subproblem added to the end of the active list. After cloning * the specified subproblem becomes inactive. * * The reference numbers of clone subproblems are stored to locations * ref[1], ..., ref[nnn]. */ static int get_slot(glp_tree *tree) { int p; /* if no free slots are available, increase the room */ if (tree->avail == 0) { int nslots = tree->nslots; IOSLOT *save = tree->slot; if (nslots == 0) tree->nslots = 20; else { tree->nslots = nslots + nslots; xassert(tree->nslots > nslots); } tree->slot = xcalloc(1+tree->nslots, sizeof(IOSLOT)); if (save != NULL) { memcpy(&tree->slot[1], &save[1], nslots * sizeof(IOSLOT)); xfree(save); } /* push more free slots into the stack */ for (p = tree->nslots; p > nslots; p--) { tree->slot[p].node = NULL; tree->slot[p].next = tree->avail; tree->avail = p; } } /* pull a free slot from the stack */ p = tree->avail; tree->avail = tree->slot[p].next; xassert(tree->slot[p].node == NULL); tree->slot[p].next = 0; return p; } static IOSNPD *new_node(glp_tree *tree, IOSNPD *parent) { IOSNPD *node; int p; /* pull a free slot for the new node */ p = get_slot(tree); /* create descriptor of the new subproblem */ node = dmp_get_atom(tree->pool, sizeof(IOSNPD)); tree->slot[p].node = node; node->p = p; node->up = parent; node->level = (parent == NULL ? 0 : parent->level + 1); node->count = 0; node->b_ptr = NULL; node->s_ptr = NULL; node->r_ptr = NULL; node->solved = 0; #if 0 node->own_nn = node->own_nc = 0; node->e_ptr = NULL; #endif #if 1 /* 04/X-2008 */ node->lp_obj = (parent == NULL ? (tree->mip->dir == GLP_MIN ? -DBL_MAX : +DBL_MAX) : parent->lp_obj); #endif node->bound = (parent == NULL ? (tree->mip->dir == GLP_MIN ? -DBL_MAX : +DBL_MAX) : parent->bound); node->br_var = 0; node->br_val = 0.0; node->ii_cnt = 0; node->ii_sum = 0.0; #if 1 /* 30/XI-2009 */ node->changed = 0; #endif if (tree->parm->cb_size == 0) node->data = NULL; else { node->data = dmp_get_atom(tree->pool, tree->parm->cb_size); memset(node->data, 0, tree->parm->cb_size); } node->temp = NULL; node->prev = tree->tail; node->next = NULL; /* add the new subproblem to the end of the active list */ if (tree->head == NULL) tree->head = node; else tree->tail->next = node; tree->tail = node; tree->a_cnt++; tree->n_cnt++; tree->t_cnt++; /* increase the number of child subproblems */ if (parent == NULL) xassert(p == 1); else parent->count++; return node; } void ios_clone_node(glp_tree *tree, int p, int nnn, int ref[]) { IOSNPD *node; int k; /* obtain pointer to the subproblem to be cloned */ xassert(1 <= p && p <= tree->nslots); node = tree->slot[p].node; xassert(node != NULL); /* the specified subproblem must be active */ xassert(node->count == 0); /* and must be in the frozen state */ xassert(tree->curr != node); /* remove the specified subproblem from the active list, because it becomes inactive */ if (node->prev == NULL) tree->head = node->next; else node->prev->next = node->next; if (node->next == NULL) tree->tail = node->prev; else node->next->prev = node->prev; node->prev = node->next = NULL; tree->a_cnt--; /* create clone subproblems */ xassert(nnn > 0); for (k = 1; k <= nnn; k++) ref[k] = new_node(tree, node)->p; return; } /*********************************************************************** * NAME * * ios_delete_node - delete specified subproblem * * SYNOPSIS * * #include "glpios.h" * void ios_delete_node(glp_tree *tree, int p); * * DESCRIPTION * * The routine ios_delete_node deletes the specified subproblem, whose * reference number is p. The subproblem must be active and must be in * the frozen state (i.e. it must not be the current subproblem). * * Note that deletion is performed recursively, i.e. if a subproblem to * be deleted is the only child of its parent, the parent subproblem is * also deleted, etc. */ void ios_delete_node(glp_tree *tree, int p) { IOSNPD *node, *temp; /* obtain pointer to the subproblem to be deleted */ xassert(1 <= p && p <= tree->nslots); node = tree->slot[p].node; xassert(node != NULL); /* the specified subproblem must be active */ xassert(node->count == 0); /* and must be in the frozen state */ xassert(tree->curr != node); /* remove the specified subproblem from the active list, because it is gone from the tree */ if (node->prev == NULL) tree->head = node->next; else node->prev->next = node->next; if (node->next == NULL) tree->tail = node->prev; else node->next->prev = node->prev; node->prev = node->next = NULL; tree->a_cnt--; loop: /* recursive deletion starts here */ /* delete the bound change list */ { IOSBND *b; while (node->b_ptr != NULL) { b = node->b_ptr; node->b_ptr = b->next; dmp_free_atom(tree->pool, b, sizeof(IOSBND)); } } /* delete the status change list */ { IOSTAT *s; while (node->s_ptr != NULL) { s = node->s_ptr; node->s_ptr = s->next; dmp_free_atom(tree->pool, s, sizeof(IOSTAT)); } } /* delete the row addition list */ while (node->r_ptr != NULL) { IOSROW *r; r = node->r_ptr; if (r->name != NULL) dmp_free_atom(tree->pool, r->name, strlen(r->name)+1); while (r->ptr != NULL) { IOSAIJ *a; a = r->ptr; r->ptr = a->next; dmp_free_atom(tree->pool, a, sizeof(IOSAIJ)); } node->r_ptr = r->next; dmp_free_atom(tree->pool, r, sizeof(IOSROW)); } #if 0 /* delete the edge addition list */ /* delete the clique addition list */ /* (not implemented yet) */ xassert(node->own_nn == 0); xassert(node->own_nc == 0); xassert(node->e_ptr == NULL); #endif /* free application-specific data */ if (tree->parm->cb_size == 0) xassert(node->data == NULL); else dmp_free_atom(tree->pool, node->data, tree->parm->cb_size); /* free the corresponding node slot */ p = node->p; xassert(tree->slot[p].node == node); tree->slot[p].node = NULL; tree->slot[p].next = tree->avail; tree->avail = p; /* save pointer to the parent subproblem */ temp = node->up; /* delete the subproblem descriptor */ dmp_free_atom(tree->pool, node, sizeof(IOSNPD)); tree->n_cnt--; /* take pointer to the parent subproblem */ node = temp; if (node != NULL) { /* the parent subproblem exists; decrease the number of its child subproblems */ xassert(node->count > 0); node->count--; /* if now the parent subproblem has no childs, it also must be deleted */ if (node->count == 0) goto loop; } return; } /*********************************************************************** * NAME * * ios_delete_tree - delete branch-and-bound tree * * SYNOPSIS * * #include "glpios.h" * void ios_delete_tree(glp_tree *tree); * * DESCRIPTION * * The routine ios_delete_tree deletes the branch-and-bound tree, which * the parameter tree points to, and frees all the memory allocated to * this program object. * * On exit components of the problem object are restored to correspond * to the original MIP passed to the routine ios_create_tree. */ void ios_delete_tree(glp_tree *tree) { glp_prob *mip = tree->mip; int i, j; int m = mip->m; int n = mip->n; xassert(mip->tree == tree); /* remove all additional rows */ if (m != tree->orig_m) { int nrs, *num; nrs = m - tree->orig_m; xassert(nrs > 0); num = xcalloc(1+nrs, sizeof(int)); for (i = 1; i <= nrs; i++) num[i] = tree->orig_m + i; glp_del_rows(mip, nrs, num); xfree(num); } m = tree->orig_m; /* restore original attributes of rows and columns */ xassert(m == tree->orig_m); xassert(n == tree->n); for (i = 1; i <= m; i++) { glp_set_row_bnds(mip, i, tree->orig_type[i], tree->orig_lb[i], tree->orig_ub[i]); glp_set_row_stat(mip, i, tree->orig_stat[i]); mip->row[i]->prim = tree->orig_prim[i]; mip->row[i]->dual = tree->orig_dual[i]; } for (j = 1; j <= n; j++) { glp_set_col_bnds(mip, j, tree->orig_type[m+j], tree->orig_lb[m+j], tree->orig_ub[m+j]); glp_set_col_stat(mip, j, tree->orig_stat[m+j]); mip->col[j]->prim = tree->orig_prim[m+j]; mip->col[j]->dual = tree->orig_dual[m+j]; } mip->pbs_stat = mip->dbs_stat = GLP_FEAS; mip->obj_val = tree->orig_obj; /* delete the branch-and-bound tree */ xassert(tree->local != NULL); ios_delete_pool(tree, tree->local); dmp_delete_pool(tree->pool); xfree(tree->orig_type); xfree(tree->orig_lb); xfree(tree->orig_ub); xfree(tree->orig_stat); xfree(tree->orig_prim); xfree(tree->orig_dual); xfree(tree->slot); if (tree->root_type != NULL) xfree(tree->root_type); if (tree->root_lb != NULL) xfree(tree->root_lb); if (tree->root_ub != NULL) xfree(tree->root_ub); if (tree->root_stat != NULL) xfree(tree->root_stat); xfree(tree->non_int); #if 0 xfree(tree->n_ref); xfree(tree->c_ref); xfree(tree->j_ref); #endif if (tree->pcost != NULL) ios_pcost_free(tree); xfree(tree->iwrk); xfree(tree->dwrk); #if 0 scg_delete_graph(tree->g); #endif if (tree->pred_type != NULL) xfree(tree->pred_type); if (tree->pred_lb != NULL) xfree(tree->pred_lb); if (tree->pred_ub != NULL) xfree(tree->pred_ub); if (tree->pred_stat != NULL) xfree(tree->pred_stat); #if 0 xassert(tree->cut_gen == NULL); #endif xassert(tree->mir_gen == NULL); xassert(tree->clq_gen == NULL); xfree(tree); mip->tree = NULL; return; } /*********************************************************************** * NAME * * ios_eval_degrad - estimate obj. degrad. for down- and up-branches * * SYNOPSIS * * #include "glpios.h" * void ios_eval_degrad(glp_tree *tree, int j, double *dn, double *up); * * DESCRIPTION * * Given optimal basis to LP relaxation of the current subproblem the * routine ios_eval_degrad performs the dual ratio test to compute the * objective values in the adjacent basis for down- and up-branches, * which are stored in locations *dn and *up, assuming that x[j] is a * variable chosen to branch upon. */ void ios_eval_degrad(glp_tree *tree, int j, double *dn, double *up) { glp_prob *mip = tree->mip; int m = mip->m, n = mip->n; int len, kase, k, t, stat; double alfa, beta, gamma, delta, dz; int *ind = tree->iwrk; double *val = tree->dwrk; /* current basis must be optimal */ xassert(glp_get_status(mip) == GLP_OPT); /* basis factorization must exist */ xassert(glp_bf_exists(mip)); /* obtain (fractional) value of x[j] in optimal basic solution to LP relaxation of the current subproblem */ xassert(1 <= j && j <= n); beta = mip->col[j]->prim; /* since the value of x[j] is fractional, it is basic; compute corresponding row of the simplex table */ len = lpx_eval_tab_row(mip, m+j, ind, val); /* kase < 0 means down-branch; kase > 0 means up-branch */ for (kase = -1; kase <= +1; kase += 2) { /* for down-branch we introduce new upper bound floor(beta) for x[j]; similarly, for up-branch we introduce new lower bound ceil(beta) for x[j]; in the current basis this new upper/lower bound is violated, so in the adjacent basis x[j] will leave the basis and go to its new upper/lower bound; we need to know which non-basic variable x[k] should enter the basis to keep dual feasibility */ #if 0 /* 23/XI-2009 */ k = lpx_dual_ratio_test(mip, len, ind, val, kase, 1e-7); #else k = lpx_dual_ratio_test(mip, len, ind, val, kase, 1e-9); #endif /* if no variable has been chosen, current basis being primal infeasible due to the new upper/lower bound of x[j] is dual unbounded, therefore, LP relaxation to corresponding branch has no primal feasible solution */ if (k == 0) { if (mip->dir == GLP_MIN) { if (kase < 0) *dn = +DBL_MAX; else *up = +DBL_MAX; } else if (mip->dir == GLP_MAX) { if (kase < 0) *dn = -DBL_MAX; else *up = -DBL_MAX; } else xassert(mip != mip); continue; } xassert(1 <= k && k <= m+n); /* row of the simplex table corresponding to specified basic variable x[j] is the following: x[j] = ... + alfa * x[k] + ... ; we need to know influence coefficient, alfa, at non-basic variable x[k] chosen with the dual ratio test */ for (t = 1; t <= len; t++) if (ind[t] == k) break; xassert(1 <= t && t <= len); alfa = val[t]; /* determine status and reduced cost of variable x[k] */ if (k <= m) { stat = mip->row[k]->stat; gamma = mip->row[k]->dual; } else { stat = mip->col[k-m]->stat; gamma = mip->col[k-m]->dual; } /* x[k] cannot be basic or fixed non-basic */ xassert(stat == GLP_NL || stat == GLP_NU || stat == GLP_NF); /* if the current basis is dual degenerative, some reduced costs, which are close to zero, may have wrong sign due to round-off errors, so correct the sign of gamma */ if (mip->dir == GLP_MIN) { if (stat == GLP_NL && gamma < 0.0 || stat == GLP_NU && gamma > 0.0 || stat == GLP_NF) gamma = 0.0; } else if (mip->dir == GLP_MAX) { if (stat == GLP_NL && gamma > 0.0 || stat == GLP_NU && gamma < 0.0 || stat == GLP_NF) gamma = 0.0; } else xassert(mip != mip); /* determine the change of x[j] in the adjacent basis: delta x[j] = new x[j] - old x[j] */ delta = (kase < 0 ? floor(beta) : ceil(beta)) - beta; /* compute the change of x[k] in the adjacent basis: delta x[k] = new x[k] - old x[k] = delta x[j] / alfa */ delta /= alfa; /* compute the change of the objective in the adjacent basis: delta z = new z - old z = gamma * delta x[k] */ dz = gamma * delta; if (mip->dir == GLP_MIN) xassert(dz >= 0.0); else if (mip->dir == GLP_MAX) xassert(dz <= 0.0); else xassert(mip != mip); /* compute the new objective value in the adjacent basis: new z = old z + delta z */ if (kase < 0) *dn = mip->obj_val + dz; else *up = mip->obj_val + dz; } /*xprintf("obj = %g; dn = %g; up = %g\n", mip->obj_val, *dn, *up);*/ return; } /*********************************************************************** * NAME * * ios_round_bound - improve local bound by rounding * * SYNOPSIS * * #include "glpios.h" * double ios_round_bound(glp_tree *tree, double bound); * * RETURNS * * For the given local bound for any integer feasible solution to the * current subproblem the routine ios_round_bound returns an improved * local bound for the same integer feasible solution. * * BACKGROUND * * Let the current subproblem has the following objective function: * * z = sum c[j] * x[j] + s >= b, (1) * j in J * * where J = {j: c[j] is non-zero and integer, x[j] is integer}, s is * the sum of terms corresponding to fixed variables, b is an initial * local bound (minimization). * * From (1) it follows that: * * d * sum (c[j] / d) * x[j] + s >= b, (2) * j in J * * or, equivalently, * * sum (c[j] / d) * x[j] >= (b - s) / d = h, (3) * j in J * * where d = gcd(c[j]). Since the left-hand side of (3) is integer, * h = (b - s) / d can be rounded up to the nearest integer: * * h' = ceil(h) = (b' - s) / d, (4) * * that gives an rounded, improved local bound: * * b' = d * h' + s. (5) * * In case of maximization '>=' in (1) should be replaced by '<=' that * leads to the following formula: * * h' = floor(h) = (b' - s) / d, (6) * * which should used in the same way as (4). * * NOTE: If b is a valid local bound for a child of the current * subproblem, b' is also valid for that child subproblem. */ double ios_round_bound(glp_tree *tree, double bound) { glp_prob *mip = tree->mip; int n = mip->n; int d, j, nn, *c = tree->iwrk; double s, h; /* determine c[j] and compute s */ nn = 0, s = mip->c0, d = 0; for (j = 1; j <= n; j++) { GLPCOL *col = mip->col[j]; if (col->coef == 0.0) continue; if (col->type == GLP_FX) { /* fixed variable */ s += col->coef * col->prim; } else { /* non-fixed variable */ if (col->kind != GLP_IV) goto skip; if (col->coef != floor(col->coef)) goto skip; if (fabs(col->coef) <= (double)INT_MAX) c[++nn] = (int)fabs(col->coef); else d = 1; } } /* compute d = gcd(c[1],...c[nn]) */ if (d == 0) { if (nn == 0) goto skip; d = gcdn(nn, c); } xassert(d > 0); /* compute new local bound */ if (mip->dir == GLP_MIN) { if (bound != +DBL_MAX) { h = (bound - s) / (double)d; if (h >= floor(h) + 0.001) { /* round up */ h = ceil(h); /*xprintf("d = %d; old = %g; ", d, bound);*/ bound = (double)d * h + s; /*xprintf("new = %g\n", bound);*/ } } } else if (mip->dir == GLP_MAX) { if (bound != -DBL_MAX) { h = (bound - s) / (double)d; if (h <= ceil(h) - 0.001) { /* round down */ h = floor(h); bound = (double)d * h + s; } } } else xassert(mip != mip); skip: return bound; } /*********************************************************************** * NAME * * ios_is_hopeful - check if subproblem is hopeful * * SYNOPSIS * * #include "glpios.h" * int ios_is_hopeful(glp_tree *tree, double bound); * * DESCRIPTION * * Given the local bound of a subproblem the routine ios_is_hopeful * checks if the subproblem can have an integer optimal solution which * is better than the best one currently known. * * RETURNS * * If the subproblem can have a better integer optimal solution, the * routine returns non-zero; otherwise, if the corresponding branch can * be pruned, the routine returns zero. */ int ios_is_hopeful(glp_tree *tree, double bound) { glp_prob *mip = tree->mip; int ret = 1; double eps; if (mip->mip_stat == GLP_FEAS) { eps = tree->parm->tol_obj * (1.0 + fabs(mip->mip_obj)); switch (mip->dir) { case GLP_MIN: if (bound >= mip->mip_obj - eps) ret = 0; break; case GLP_MAX: if (bound <= mip->mip_obj + eps) ret = 0; break; default: xassert(mip != mip); } } else { switch (mip->dir) { case GLP_MIN: if (bound == +DBL_MAX) ret = 0; break; case GLP_MAX: if (bound == -DBL_MAX) ret = 0; break; default: xassert(mip != mip); } } return ret; } /*********************************************************************** * NAME * * ios_best_node - find active node with best local bound * * SYNOPSIS * * #include "glpios.h" * int ios_best_node(glp_tree *tree); * * DESCRIPTION * * The routine ios_best_node finds an active node whose local bound is * best among other active nodes. * * It is understood that the integer optimal solution of the original * mip problem cannot be better than the best bound, so the best bound * is an lower (minimization) or upper (maximization) global bound for * the original problem. * * RETURNS * * The routine ios_best_node returns the subproblem reference number * for the best node. However, if the tree is empty, it returns zero. */ int ios_best_node(glp_tree *tree) { IOSNPD *node, *best = NULL; switch (tree->mip->dir) { case GLP_MIN: /* minimization */ for (node = tree->head; node != NULL; node = node->next) if (best == NULL || best->bound > node->bound) best = node; break; case GLP_MAX: /* maximization */ for (node = tree->head; node != NULL; node = node->next) if (best == NULL || best->bound < node->bound) best = node; break; default: xassert(tree != tree); } return best == NULL ? 0 : best->p; } /*********************************************************************** * NAME * * ios_relative_gap - compute relative mip gap * * SYNOPSIS * * #include "glpios.h" * double ios_relative_gap(glp_tree *tree); * * DESCRIPTION * * The routine ios_relative_gap computes the relative mip gap using the * formula: * * gap = |best_mip - best_bnd| / (|best_mip| + DBL_EPSILON), * * where best_mip is the best integer feasible solution found so far, * best_bnd is the best (global) bound. If no integer feasible solution * has been found yet, rel_gap is set to DBL_MAX. * * RETURNS * * The routine ios_relative_gap returns the relative mip gap. */ double ios_relative_gap(glp_tree *tree) { glp_prob *mip = tree->mip; int p; double best_mip, best_bnd, gap; if (mip->mip_stat == GLP_FEAS) { best_mip = mip->mip_obj; p = ios_best_node(tree); if (p == 0) { /* the tree is empty */ gap = 0.0; } else { best_bnd = tree->slot[p].node->bound; gap = fabs(best_mip - best_bnd) / (fabs(best_mip) + DBL_EPSILON); } } else { /* no integer feasible solution has been found yet */ gap = DBL_MAX; } return gap; } /*********************************************************************** * NAME * * ios_solve_node - solve LP relaxation of current subproblem * * SYNOPSIS * * #include "glpios.h" * int ios_solve_node(glp_tree *tree); * * DESCRIPTION * * The routine ios_solve_node re-optimizes LP relaxation of the current * subproblem using the dual simplex method. * * RETURNS * * The routine returns the code which is reported by glp_simplex. */ int ios_solve_node(glp_tree *tree) { glp_prob *mip = tree->mip; glp_smcp parm; int ret; /* the current subproblem must exist */ xassert(tree->curr != NULL); /* set some control parameters */ glp_init_smcp(&parm); switch (tree->parm->msg_lev) { case GLP_MSG_OFF: parm.msg_lev = GLP_MSG_OFF; break; case GLP_MSG_ERR: parm.msg_lev = GLP_MSG_ERR; break; case GLP_MSG_ON: case GLP_MSG_ALL: parm.msg_lev = GLP_MSG_ON; break; case GLP_MSG_DBG: parm.msg_lev = GLP_MSG_ALL; break; default: xassert(tree != tree); } parm.meth = GLP_DUALP; if (tree->parm->msg_lev < GLP_MSG_DBG) parm.out_dly = tree->parm->out_dly; else parm.out_dly = 0; /* if the incumbent objective value is already known, use it to prematurely terminate the dual simplex search */ if (mip->mip_stat == GLP_FEAS) { switch (tree->mip->dir) { case GLP_MIN: parm.obj_ul = mip->mip_obj; break; case GLP_MAX: parm.obj_ll = mip->mip_obj; break; default: xassert(mip != mip); } } /* try to solve/re-optimize the LP relaxation */ ret = glp_simplex(mip, &parm); tree->curr->solved++; #if 0 xprintf("ret = %d; status = %d; pbs = %d; dbs = %d; some = %d\n", ret, glp_get_status(mip), mip->pbs_stat, mip->dbs_stat, mip->some); lpx_print_sol(mip, "sol"); #endif return ret; } /**********************************************************************/ IOSPOOL *ios_create_pool(glp_tree *tree) { /* create cut pool */ IOSPOOL *pool; #if 0 pool = dmp_get_atom(tree->pool, sizeof(IOSPOOL)); #else xassert(tree == tree); pool = xmalloc(sizeof(IOSPOOL)); #endif pool->size = 0; pool->head = pool->tail = NULL; pool->ord = 0, pool->curr = NULL; return pool; } int ios_add_row(glp_tree *tree, IOSPOOL *pool, const char *name, int klass, int flags, int len, const int ind[], const double val[], int type, double rhs) { /* add row (constraint) to the cut pool */ IOSCUT *cut; IOSAIJ *aij; int k; xassert(pool != NULL); cut = dmp_get_atom(tree->pool, sizeof(IOSCUT)); if (name == NULL || name[0] == '\0') cut->name = NULL; else { for (k = 0; name[k] != '\0'; k++) { if (k == 256) xerror("glp_ios_add_row: cut name too long\n"); if (iscntrl((unsigned char)name[k])) xerror("glp_ios_add_row: cut name contains invalid chara" "cter(s)\n"); } cut->name = dmp_get_atom(tree->pool, strlen(name)+1); strcpy(cut->name, name); } if (!(0 <= klass && klass <= 255)) xerror("glp_ios_add_row: klass = %d; invalid cut class\n", klass); cut->klass = (unsigned char)klass; if (flags != 0) xerror("glp_ios_add_row: flags = %d; invalid cut flags\n", flags); cut->ptr = NULL; if (!(0 <= len && len <= tree->n)) xerror("glp_ios_add_row: len = %d; invalid cut length\n", len); for (k = 1; k <= len; k++) { aij = dmp_get_atom(tree->pool, sizeof(IOSAIJ)); if (!(1 <= ind[k] && ind[k] <= tree->n)) xerror("glp_ios_add_row: ind[%d] = %d; column index out of " "range\n", k, ind[k]); aij->j = ind[k]; aij->val = val[k]; aij->next = cut->ptr; cut->ptr = aij; } if (!(type == GLP_LO || type == GLP_UP || type == GLP_FX)) xerror("glp_ios_add_row: type = %d; invalid cut type\n", type); cut->type = (unsigned char)type; cut->rhs = rhs; cut->prev = pool->tail; cut->next = NULL; if (cut->prev == NULL) pool->head = cut; else cut->prev->next = cut; pool->tail = cut; pool->size++; return pool->size; } IOSCUT *ios_find_row(IOSPOOL *pool, int i) { /* find row (constraint) in the cut pool */ /* (smart linear search) */ xassert(pool != NULL); xassert(1 <= i && i <= pool->size); if (pool->ord == 0) { xassert(pool->curr == NULL); pool->ord = 1; pool->curr = pool->head; } xassert(pool->curr != NULL); if (i < pool->ord) { if (i < pool->ord - i) { pool->ord = 1; pool->curr = pool->head; while (pool->ord != i) { pool->ord++; xassert(pool->curr != NULL); pool->curr = pool->curr->next; } } else { while (pool->ord != i) { pool->ord--; xassert(pool->curr != NULL); pool->curr = pool->curr->prev; } } } else if (i > pool->ord) { if (i - pool->ord < pool->size - i) { while (pool->ord != i) { pool->ord++; xassert(pool->curr != NULL); pool->curr = pool->curr->next; } } else { pool->ord = pool->size; pool->curr = pool->tail; while (pool->ord != i) { pool->ord--; xassert(pool->curr != NULL); pool->curr = pool->curr->prev; } } } xassert(pool->ord == i); xassert(pool->curr != NULL); return pool->curr; } void ios_del_row(glp_tree *tree, IOSPOOL *pool, int i) { /* remove row (constraint) from the cut pool */ IOSCUT *cut; IOSAIJ *aij; xassert(pool != NULL); if (!(1 <= i && i <= pool->size)) xerror("glp_ios_del_row: i = %d; cut number out of range\n", i); cut = ios_find_row(pool, i); xassert(pool->curr == cut); if (cut->next != NULL) pool->curr = cut->next; else if (cut->prev != NULL) pool->ord--, pool->curr = cut->prev; else pool->ord = 0, pool->curr = NULL; if (cut->name != NULL) dmp_free_atom(tree->pool, cut->name, strlen(cut->name)+1); if (cut->prev == NULL) { xassert(pool->head == cut); pool->head = cut->next; } else { xassert(cut->prev->next == cut); cut->prev->next = cut->next; } if (cut->next == NULL) { xassert(pool->tail == cut); pool->tail = cut->prev; } else { xassert(cut->next->prev == cut); cut->next->prev = cut->prev; } while (cut->ptr != NULL) { aij = cut->ptr; cut->ptr = aij->next; dmp_free_atom(tree->pool, aij, sizeof(IOSAIJ)); } dmp_free_atom(tree->pool, cut, sizeof(IOSCUT)); pool->size--; return; } void ios_clear_pool(glp_tree *tree, IOSPOOL *pool) { /* remove all rows (constraints) from the cut pool */ xassert(pool != NULL); while (pool->head != NULL) { IOSCUT *cut = pool->head; pool->head = cut->next; if (cut->name != NULL) dmp_free_atom(tree->pool, cut->name, strlen(cut->name)+1); while (cut->ptr != NULL) { IOSAIJ *aij = cut->ptr; cut->ptr = aij->next; dmp_free_atom(tree->pool, aij, sizeof(IOSAIJ)); } dmp_free_atom(tree->pool, cut, sizeof(IOSCUT)); } pool->size = 0; pool->head = pool->tail = NULL; pool->ord = 0, pool->curr = NULL; return; } void ios_delete_pool(glp_tree *tree, IOSPOOL *pool) { /* delete cut pool */ xassert(pool != NULL); ios_clear_pool(tree, pool); xfree(pool); return; } /**********************************************************************/ #if 0 static int refer_to_node(glp_tree *tree, int j) { /* determine node number corresponding to binary variable x[j] or its complement */ glp_prob *mip = tree->mip; int n = mip->n; int *ref; if (j > 0) ref = tree->n_ref; else ref = tree->c_ref, j = - j; xassert(1 <= j && j <= n); if (ref[j] == 0) { /* new node is needed */ SCG *g = tree->g; int n_max = g->n_max; ref[j] = scg_add_nodes(g, 1); if (g->n_max > n_max) { int *save = tree->j_ref; tree->j_ref = xcalloc(1+g->n_max, sizeof(int)); memcpy(&tree->j_ref[1], &save[1], g->n * sizeof(int)); xfree(save); } xassert(ref[j] == g->n); tree->j_ref[ref[j]] = j; xassert(tree->curr != NULL); if (tree->curr->level > 0) tree->curr->own_nn++; } return ref[j]; } #endif #if 0 void ios_add_edge(glp_tree *tree, int j1, int j2) { /* add new edge to the conflict graph */ glp_prob *mip = tree->mip; int n = mip->n; SCGRIB *e; int first, i1, i2; xassert(-n <= j1 && j1 <= +n && j1 != 0); xassert(-n <= j2 && j2 <= +n && j2 != 0); xassert(j1 != j2); /* determine number of the first node, which was added for the current subproblem */ xassert(tree->curr != NULL); first = tree->g->n - tree->curr->own_nn + 1; /* determine node numbers for both endpoints */ i1 = refer_to_node(tree, j1); i2 = refer_to_node(tree, j2); /* add edge (i1,i2) to the conflict graph */ e = scg_add_edge(tree->g, i1, i2); /* if the current subproblem is not the root and both endpoints were created on some previous levels, save the edge */ if (tree->curr->level > 0 && i1 < first && i2 < first) { IOSRIB *rib; rib = dmp_get_atom(tree->pool, sizeof(IOSRIB)); rib->j1 = j1; rib->j2 = j2; rib->e = e; rib->next = tree->curr->e_ptr; tree->curr->e_ptr = rib; } return; } #endif /* eof */