/* glpapi13.c (branch-and-bound interface routines) */ /*********************************************************************** * This code is part of GLPK (GNU Linear Programming Kit). * Copyright (C) 2000-2018 Free Software Foundation, Inc. * Written by Andrew Makhorin . * * 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 "env.h" #include "ios.h" /*********************************************************************** * NAME * * glp_ios_reason - determine reason for calling the callback routine * * SYNOPSIS * * glp_ios_reason(glp_tree *tree); * * RETURNS * * The routine glp_ios_reason returns a code, which indicates why the * user-defined callback routine is being called. */ int glp_ios_reason(glp_tree *tree) { return tree->reason; } /*********************************************************************** * NAME * * glp_ios_get_prob - access the problem object * * SYNOPSIS * * glp_prob *glp_ios_get_prob(glp_tree *tree); * * DESCRIPTION * * The routine glp_ios_get_prob can be called from the user-defined * callback routine to access the problem object, which is used by the * MIP solver. It is the original problem object passed to the routine * glp_intopt if the MIP presolver is not used; otherwise it is an * internal problem object built by the presolver. If the current * subproblem exists, LP segment of the problem object corresponds to * its LP relaxation. * * RETURNS * * The routine glp_ios_get_prob returns a pointer to the problem object * used by the MIP solver. */ glp_prob *glp_ios_get_prob(glp_tree *tree) { return tree->mip; } /*********************************************************************** * NAME * * glp_ios_tree_size - determine size of the branch-and-bound tree * * SYNOPSIS * * void glp_ios_tree_size(glp_tree *tree, int *a_cnt, int *n_cnt, * int *t_cnt); * * DESCRIPTION * * The routine glp_ios_tree_size stores the following three counts which * characterize the current size of the branch-and-bound tree: * * a_cnt is the current number of active nodes, i.e. the current size of * the active list; * * n_cnt is the current number of all (active and inactive) nodes; * * t_cnt is the total number of nodes including those which have been * already removed from the tree. This count is increased whenever * a new node appears in the tree and never decreased. * * If some of the parameters a_cnt, n_cnt, t_cnt is a null pointer, the * corresponding count is not stored. */ void glp_ios_tree_size(glp_tree *tree, int *a_cnt, int *n_cnt, int *t_cnt) { if (a_cnt != NULL) *a_cnt = tree->a_cnt; if (n_cnt != NULL) *n_cnt = tree->n_cnt; if (t_cnt != NULL) *t_cnt = tree->t_cnt; return; } /*********************************************************************** * NAME * * glp_ios_curr_node - determine current active subproblem * * SYNOPSIS * * int glp_ios_curr_node(glp_tree *tree); * * RETURNS * * The routine glp_ios_curr_node returns the reference number of the * current active subproblem. However, if the current subproblem does * not exist, the routine returns zero. */ int glp_ios_curr_node(glp_tree *tree) { IOSNPD *node; /* obtain pointer to the current subproblem */ node = tree->curr; /* return its reference number */ return node == NULL ? 0 : node->p; } /*********************************************************************** * NAME * * glp_ios_next_node - determine next active subproblem * * SYNOPSIS * * int glp_ios_next_node(glp_tree *tree, int p); * * RETURNS * * If the parameter p is zero, the routine glp_ios_next_node returns * the reference number of the first active subproblem. However, if the * tree is empty, zero is returned. * * If the parameter p is not zero, it must specify the reference number * of some active subproblem, in which case the routine returns the * reference number of the next active subproblem. However, if there is * no next active subproblem in the list, zero is returned. * * All subproblems in the active list are ordered chronologically, i.e. * subproblem A precedes subproblem B if A was created before B. */ int glp_ios_next_node(glp_tree *tree, int p) { IOSNPD *node; if (p == 0) { /* obtain pointer to the first active subproblem */ node = tree->head; } else { /* obtain pointer to the specified subproblem */ if (!(1 <= p && p <= tree->nslots)) err: xerror("glp_ios_next_node: p = %d; invalid subproblem refer" "ence number\n", p); node = tree->slot[p].node; if (node == NULL) goto err; /* the specified subproblem must be active */ if (node->count != 0) xerror("glp_ios_next_node: p = %d; subproblem not in the ac" "tive list\n", p); /* obtain pointer to the next active subproblem */ node = node->next; } /* return the reference number */ return node == NULL ? 0 : node->p; } /*********************************************************************** * NAME * * glp_ios_prev_node - determine previous active subproblem * * SYNOPSIS * * int glp_ios_prev_node(glp_tree *tree, int p); * * RETURNS * * If the parameter p is zero, the routine glp_ios_prev_node returns * the reference number of the last active subproblem. However, if the * tree is empty, zero is returned. * * If the parameter p is not zero, it must specify the reference number * of some active subproblem, in which case the routine returns the * reference number of the previous active subproblem. However, if there * is no previous active subproblem in the list, zero is returned. * * All subproblems in the active list are ordered chronologically, i.e. * subproblem A precedes subproblem B if A was created before B. */ int glp_ios_prev_node(glp_tree *tree, int p) { IOSNPD *node; if (p == 0) { /* obtain pointer to the last active subproblem */ node = tree->tail; } else { /* obtain pointer to the specified subproblem */ if (!(1 <= p && p <= tree->nslots)) err: xerror("glp_ios_prev_node: p = %d; invalid subproblem refer" "ence number\n", p); node = tree->slot[p].node; if (node == NULL) goto err; /* the specified subproblem must be active */ if (node->count != 0) xerror("glp_ios_prev_node: p = %d; subproblem not in the ac" "tive list\n", p); /* obtain pointer to the previous active subproblem */ node = node->prev; } /* return the reference number */ return node == NULL ? 0 : node->p; } /*********************************************************************** * NAME * * glp_ios_up_node - determine parent subproblem * * SYNOPSIS * * int glp_ios_up_node(glp_tree *tree, int p); * * RETURNS * * The parameter p must specify the reference number of some (active or * inactive) subproblem, in which case the routine iet_get_up_node * returns the reference number of its parent subproblem. However, if * the specified subproblem is the root of the tree and, therefore, has * no parent, the routine returns zero. */ int glp_ios_up_node(glp_tree *tree, int p) { IOSNPD *node; /* obtain pointer to the specified subproblem */ if (!(1 <= p && p <= tree->nslots)) err: xerror("glp_ios_up_node: p = %d; invalid subproblem reference " "number\n", p); node = tree->slot[p].node; if (node == NULL) goto err; /* obtain pointer to the parent subproblem */ node = node->up; /* return the reference number */ return node == NULL ? 0 : node->p; } /*********************************************************************** * NAME * * glp_ios_node_level - determine subproblem level * * SYNOPSIS * * int glp_ios_node_level(glp_tree *tree, int p); * * RETURNS * * The routine glp_ios_node_level returns the level of the subproblem, * whose reference number is p, in the branch-and-bound tree. (The root * subproblem has level 0, and the level of any other subproblem is the * level of its parent plus one.) */ int glp_ios_node_level(glp_tree *tree, int p) { IOSNPD *node; /* obtain pointer to the specified subproblem */ if (!(1 <= p && p <= tree->nslots)) err: xerror("glp_ios_node_level: p = %d; invalid subproblem referen" "ce number\n", p); node = tree->slot[p].node; if (node == NULL) goto err; /* return the node level */ return node->level; } /*********************************************************************** * NAME * * glp_ios_node_bound - determine subproblem local bound * * SYNOPSIS * * double glp_ios_node_bound(glp_tree *tree, int p); * * RETURNS * * The routine glp_ios_node_bound returns the local bound for (active or * inactive) subproblem, whose reference number is p. * * COMMENTS * * The local bound for subproblem p is an lower (minimization) or upper * (maximization) bound for integer optimal solution to this subproblem * (not to the original problem). This bound is local in the sense that * only subproblems in the subtree rooted at node p cannot have better * integer feasible solutions. * * On creating a subproblem (due to the branching step) its local bound * is inherited from its parent and then may get only stronger (never * weaker). For the root subproblem its local bound is initially set to * -DBL_MAX (minimization) or +DBL_MAX (maximization) and then improved * as the root LP relaxation has been solved. * * Note that the local bound is not necessarily the optimal objective * value to corresponding LP relaxation; it may be stronger. */ double glp_ios_node_bound(glp_tree *tree, int p) { IOSNPD *node; /* obtain pointer to the specified subproblem */ if (!(1 <= p && p <= tree->nslots)) err: xerror("glp_ios_node_bound: p = %d; invalid subproblem referen" "ce number\n", p); node = tree->slot[p].node; if (node == NULL) goto err; /* return the node local bound */ return node->bound; } /*********************************************************************** * NAME * * glp_ios_best_node - find active subproblem with best local bound * * SYNOPSIS * * int glp_ios_best_node(glp_tree *tree); * * RETURNS * * The routine glp_ios_best_node returns the reference number of the * active subproblem, whose local bound is best (i.e. smallest in case * of minimization or largest in case of maximization). However, if the * tree is empty, the routine returns zero. * * COMMENTS * * The best local bound is an lower (minimization) or upper * (maximization) bound for integer optimal solution to the original * MIP problem. */ int glp_ios_best_node(glp_tree *tree) { return ios_best_node(tree); } /*********************************************************************** * NAME * * glp_ios_mip_gap - compute relative MIP gap * * SYNOPSIS * * double glp_ios_mip_gap(glp_tree *tree); * * DESCRIPTION * * The routine glp_ios_mip_gap computes the relative MIP gap with the * following 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, gap is set to DBL_MAX. * * RETURNS * * The routine glp_ios_mip_gap returns the relative MIP gap. */ double glp_ios_mip_gap(glp_tree *tree) { return ios_relative_gap(tree); } /*********************************************************************** * NAME * * glp_ios_node_data - access subproblem application-specific data * * SYNOPSIS * * void *glp_ios_node_data(glp_tree *tree, int p); * * DESCRIPTION * * The routine glp_ios_node_data allows the application accessing a * memory block allocated for the subproblem (which may be active or * inactive), whose reference number is p. * * The size of the block is defined by the control parameter cb_size * passed to the routine glp_intopt. The block is initialized by binary * zeros on creating corresponding subproblem, and its contents is kept * until the subproblem will be removed from the tree. * * The application may use these memory blocks to store specific data * for each subproblem. * * RETURNS * * The routine glp_ios_node_data returns a pointer to the memory block * for the specified subproblem. Note that if cb_size = 0, the routine * returns a null pointer. */ void *glp_ios_node_data(glp_tree *tree, int p) { IOSNPD *node; /* obtain pointer to the specified subproblem */ if (!(1 <= p && p <= tree->nslots)) err: xerror("glp_ios_node_level: p = %d; invalid subproblem referen" "ce number\n", p); node = tree->slot[p].node; if (node == NULL) goto err; /* return pointer to the application-specific data */ return node->data; } /*********************************************************************** * NAME * * glp_ios_row_attr - retrieve additional row attributes * * SYNOPSIS * * void glp_ios_row_attr(glp_tree *tree, int i, glp_attr *attr); * * DESCRIPTION * * The routine glp_ios_row_attr retrieves additional attributes of row * i and stores them in the structure glp_attr. */ void glp_ios_row_attr(glp_tree *tree, int i, glp_attr *attr) { GLPROW *row; if (!(1 <= i && i <= tree->mip->m)) xerror("glp_ios_row_attr: i = %d; row number out of range\n", i); row = tree->mip->row[i]; attr->level = row->level; attr->origin = row->origin; attr->klass = row->klass; return; } /**********************************************************************/ int glp_ios_pool_size(glp_tree *tree) { /* determine current size of the cut pool */ if (tree->reason != GLP_ICUTGEN) xerror("glp_ios_pool_size: operation not allowed\n"); xassert(tree->local != NULL); #ifdef NEW_LOCAL /* 02/II-2018 */ return tree->local->m; #else return tree->local->size; #endif } /**********************************************************************/ int glp_ios_add_row(glp_tree *tree, 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 */ int num; if (tree->reason != GLP_ICUTGEN) xerror("glp_ios_add_row: operation not allowed\n"); xassert(tree->local != NULL); num = ios_add_row(tree, tree->local, name, klass, flags, len, ind, val, type, rhs); return num; } /**********************************************************************/ void glp_ios_del_row(glp_tree *tree, int i) { /* remove row (constraint) from the cut pool */ if (tree->reason != GLP_ICUTGEN) xerror("glp_ios_del_row: operation not allowed\n"); ios_del_row(tree, tree->local, i); return; } /**********************************************************************/ void glp_ios_clear_pool(glp_tree *tree) { /* remove all rows (constraints) from the cut pool */ if (tree->reason != GLP_ICUTGEN) xerror("glp_ios_clear_pool: operation not allowed\n"); ios_clear_pool(tree, tree->local); return; } /*********************************************************************** * NAME * * glp_ios_can_branch - check if can branch upon specified variable * * SYNOPSIS * * int glp_ios_can_branch(glp_tree *tree, int j); * * RETURNS * * If j-th variable (column) can be used to branch upon, the routine * glp_ios_can_branch returns non-zero, otherwise zero. */ int glp_ios_can_branch(glp_tree *tree, int j) { if (!(1 <= j && j <= tree->mip->n)) xerror("glp_ios_can_branch: j = %d; column number out of range" "\n", j); return tree->non_int[j]; } /*********************************************************************** * NAME * * glp_ios_branch_upon - choose variable to branch upon * * SYNOPSIS * * void glp_ios_branch_upon(glp_tree *tree, int j, int sel); * * DESCRIPTION * * The routine glp_ios_branch_upon can be called from the user-defined * callback routine in response to the reason GLP_IBRANCH to choose a * branching variable, whose ordinal number is j. Should note that only * variables, for which the routine glp_ios_can_branch returns non-zero, * can be used to branch upon. * * The parameter sel is a flag that indicates which branch (subproblem) * should be selected next to continue the search: * * GLP_DN_BRNCH - select down-branch; * GLP_UP_BRNCH - select up-branch; * GLP_NO_BRNCH - use general selection technique. */ void glp_ios_branch_upon(glp_tree *tree, int j, int sel) { if (!(1 <= j && j <= tree->mip->n)) xerror("glp_ios_branch_upon: j = %d; column number out of rang" "e\n", j); if (!(sel == GLP_DN_BRNCH || sel == GLP_UP_BRNCH || sel == GLP_NO_BRNCH)) xerror("glp_ios_branch_upon: sel = %d: invalid branch selectio" "n flag\n", sel); if (!(tree->non_int[j])) xerror("glp_ios_branch_upon: j = %d; variable cannot be used t" "o branch upon\n", j); if (tree->br_var != 0) xerror("glp_ios_branch_upon: branching variable already chosen" "\n"); tree->br_var = j; tree->br_sel = sel; return; } /*********************************************************************** * NAME * * glp_ios_select_node - select subproblem to continue the search * * SYNOPSIS * * void glp_ios_select_node(glp_tree *tree, int p); * * DESCRIPTION * * The routine glp_ios_select_node can be called from the user-defined * callback routine in response to the reason GLP_ISELECT to select an * active subproblem, whose reference number is p. The search will be * continued from the subproblem selected. */ void glp_ios_select_node(glp_tree *tree, int p) { IOSNPD *node; /* obtain pointer to the specified subproblem */ if (!(1 <= p && p <= tree->nslots)) err: xerror("glp_ios_select_node: p = %d; invalid subproblem refere" "nce number\n", p); node = tree->slot[p].node; if (node == NULL) goto err; /* the specified subproblem must be active */ if (node->count != 0) xerror("glp_ios_select_node: p = %d; subproblem not in the act" "ive list\n", p); /* no subproblem must be selected yet */ if (tree->next_p != 0) xerror("glp_ios_select_node: subproblem already selected\n"); /* select the specified subproblem to continue the search */ tree->next_p = p; return; } /*********************************************************************** * NAME * * glp_ios_heur_sol - provide solution found by heuristic * * SYNOPSIS * * int glp_ios_heur_sol(glp_tree *tree, const double x[]); * * DESCRIPTION * * The routine glp_ios_heur_sol can be called from the user-defined * callback routine in response to the reason GLP_IHEUR to provide an * integer feasible solution found by a primal heuristic. * * Primal values of *all* variables (columns) found by the heuristic * should be placed in locations x[1], ..., x[n], where n is the number * of columns in the original problem object. Note that the routine * glp_ios_heur_sol *does not* check primal feasibility of the solution * provided. * * Using the solution passed in the array x the routine computes value * of the objective function. If the objective value is better than the * best known integer feasible solution, the routine computes values of * auxiliary variables (rows) and stores all solution components in the * problem object. * * RETURNS * * If the provided solution is accepted, the routine glp_ios_heur_sol * returns zero. Otherwise, if the provided solution is rejected, the * routine returns non-zero. */ int glp_ios_heur_sol(glp_tree *tree, const double x[]) { glp_prob *mip = tree->mip; int m = tree->orig_m; int n = tree->n; int i, j; double obj; xassert(mip->m >= m); xassert(mip->n == n); /* check values of integer variables and compute value of the objective function */ obj = mip->c0; for (j = 1; j <= n; j++) { GLPCOL *col = mip->col[j]; if (col->kind == GLP_IV) { /* provided value must be integral */ if (x[j] != floor(x[j])) return 1; } obj += col->coef * x[j]; } /* check if the provided solution is better than the best known integer feasible solution */ if (mip->mip_stat == GLP_FEAS) { switch (mip->dir) { case GLP_MIN: if (obj >= tree->mip->mip_obj) return 1; break; case GLP_MAX: if (obj <= tree->mip->mip_obj) return 1; break; default: xassert(mip != mip); } } /* it is better; store it in the problem object */ if (tree->parm->msg_lev >= GLP_MSG_ON) xprintf("Solution found by heuristic: %.12g\n", obj); mip->mip_stat = GLP_FEAS; mip->mip_obj = obj; for (j = 1; j <= n; j++) mip->col[j]->mipx = x[j]; for (i = 1; i <= m; i++) { GLPROW *row = mip->row[i]; GLPAIJ *aij; row->mipx = 0.0; for (aij = row->ptr; aij != NULL; aij = aij->r_next) row->mipx += aij->val * aij->col->mipx; } #if 1 /* 11/VII-2013 */ ios_process_sol(tree); #endif return 0; } /*********************************************************************** * NAME * * glp_ios_terminate - terminate the solution process. * * SYNOPSIS * * void glp_ios_terminate(glp_tree *tree); * * DESCRIPTION * * The routine glp_ios_terminate sets a flag indicating that the MIP * solver should prematurely terminate the search. */ void glp_ios_terminate(glp_tree *tree) { if (tree->parm->msg_lev >= GLP_MSG_DBG) xprintf("The search is prematurely terminated due to applicati" "on request\n"); tree->stop = 1; return; } /* eof */