alpar@1: /* glpios07.c (mixed cover cut generator) */ alpar@1: alpar@1: /*********************************************************************** alpar@1: * This code is part of GLPK (GNU Linear Programming Kit). alpar@1: * alpar@1: * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, alpar@1: * 2009, 2010 Andrew Makhorin, Department for Applied Informatics, alpar@1: * Moscow Aviation Institute, Moscow, Russia. All rights reserved. alpar@1: * E-mail: . alpar@1: * alpar@1: * GLPK is free software: you can redistribute it and/or modify it alpar@1: * under the terms of the GNU General Public License as published by alpar@1: * the Free Software Foundation, either version 3 of the License, or alpar@1: * (at your option) any later version. alpar@1: * alpar@1: * GLPK is distributed in the hope that it will be useful, but WITHOUT alpar@1: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY alpar@1: * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public alpar@1: * License for more details. alpar@1: * alpar@1: * You should have received a copy of the GNU General Public License alpar@1: * along with GLPK. If not, see . alpar@1: ***********************************************************************/ alpar@1: alpar@1: #include "glpios.h" alpar@1: alpar@1: /*---------------------------------------------------------------------- alpar@1: -- COVER INEQUALITIES alpar@1: -- alpar@1: -- Consider the set of feasible solutions to 0-1 knapsack problem: alpar@1: -- alpar@1: -- sum a[j]*x[j] <= b, (1) alpar@1: -- j in J alpar@1: -- alpar@1: -- x[j] is binary, (2) alpar@1: -- alpar@1: -- where, wlog, we assume that a[j] > 0 (since 0-1 variables can be alpar@1: -- complemented) and a[j] <= b (since a[j] > b implies x[j] = 0). alpar@1: -- alpar@1: -- A set C within J is called a cover if alpar@1: -- alpar@1: -- sum a[j] > b. (3) alpar@1: -- j in C alpar@1: -- alpar@1: -- For any cover C the inequality alpar@1: -- alpar@1: -- sum x[j] <= |C| - 1 (4) alpar@1: -- j in C alpar@1: -- alpar@1: -- is called a cover inequality and is valid for (1)-(2). alpar@1: -- alpar@1: -- MIXED COVER INEQUALITIES alpar@1: -- alpar@1: -- Consider the set of feasible solutions to mixed knapsack problem: alpar@1: -- alpar@1: -- sum a[j]*x[j] + y <= b, (5) alpar@1: -- j in J alpar@1: -- alpar@1: -- x[j] is binary, (6) alpar@1: -- alpar@1: -- 0 <= y <= u is continuous, (7) alpar@1: -- alpar@1: -- where again we assume that a[j] > 0. alpar@1: -- alpar@1: -- Let C within J be some set. From (1)-(4) it follows that alpar@1: -- alpar@1: -- sum a[j] > b - y (8) alpar@1: -- j in C alpar@1: -- alpar@1: -- implies alpar@1: -- alpar@1: -- sum x[j] <= |C| - 1. (9) alpar@1: -- j in C alpar@1: -- alpar@1: -- Thus, we need to modify the inequality (9) in such a way that it be alpar@1: -- a constraint only if the condition (8) is satisfied. alpar@1: -- alpar@1: -- Consider the following inequality: alpar@1: -- alpar@1: -- sum x[j] <= |C| - t. (10) alpar@1: -- j in C alpar@1: -- alpar@1: -- If 0 < t <= 1, then (10) is equivalent to (9), because all x[j] are alpar@1: -- binary variables. On the other hand, if t <= 0, (10) being satisfied alpar@1: -- for any values of x[j] is not a constraint. alpar@1: -- alpar@1: -- Let alpar@1: -- alpar@1: -- t' = sum a[j] + y - b. (11) alpar@1: -- j in C alpar@1: -- alpar@1: -- It is understood that the condition t' > 0 is equivalent to (8). alpar@1: -- Besides, from (6)-(7) it follows that t' has an implied upper bound: alpar@1: -- alpar@1: -- t'max = sum a[j] + u - b. (12) alpar@1: -- j in C alpar@1: -- alpar@1: -- This allows to express the parameter t having desired properties: alpar@1: -- alpar@1: -- t = t' / t'max. (13) alpar@1: -- alpar@1: -- In fact, t <= 1 by definition, and t > 0 being equivalent to t' > 0 alpar@1: -- is equivalent to (8). alpar@1: -- alpar@1: -- Thus, the inequality (10), where t is given by formula (13) is valid alpar@1: -- for (5)-(7). alpar@1: -- alpar@1: -- Note that if u = 0, then y = 0, so t = 1, and the conditions (8) and alpar@1: -- (10) is transformed to the conditions (3) and (4). alpar@1: -- alpar@1: -- GENERATING MIXED COVER CUTS alpar@1: -- alpar@1: -- To generate a mixed cover cut in the form (10) we need to find such alpar@1: -- set C which satisfies to the inequality (8) and for which, in turn, alpar@1: -- the inequality (10) is violated in the current point. alpar@1: -- alpar@1: -- Substituting t from (13) to (10) gives: alpar@1: -- alpar@1: -- 1 alpar@1: -- sum x[j] <= |C| - ----- (sum a[j] + y - b), (14) alpar@1: -- j in C t'max j in C alpar@1: -- alpar@1: -- and finally we have the cut inequality in the standard form: alpar@1: -- alpar@1: -- sum x[j] + alfa * y <= beta, (15) alpar@1: -- j in C alpar@1: -- alpar@1: -- where: alpar@1: -- alpar@1: -- alfa = 1 / t'max, (16) alpar@1: -- alpar@1: -- beta = |C| - alfa * (sum a[j] - b). (17) alpar@1: -- j in C */ alpar@1: alpar@1: #if 1 alpar@1: #define MAXTRY 1000 alpar@1: #else alpar@1: #define MAXTRY 10000 alpar@1: #endif alpar@1: alpar@1: static int cover2(int n, double a[], double b, double u, double x[], alpar@1: double y, int cov[], double *_alfa, double *_beta) alpar@1: { /* try to generate mixed cover cut using two-element cover */ alpar@1: int i, j, try = 0, ret = 0; alpar@1: double eps, alfa, beta, temp, rmax = 0.001; alpar@1: eps = 0.001 * (1.0 + fabs(b)); alpar@1: for (i = 0+1; i <= n; i++) alpar@1: for (j = i+1; j <= n; j++) alpar@1: { /* C = {i, j} */ alpar@1: try++; alpar@1: if (try > MAXTRY) goto done; alpar@1: /* check if condition (8) is satisfied */ alpar@1: if (a[i] + a[j] + y > b + eps) alpar@1: { /* compute parameters for inequality (15) */ alpar@1: temp = a[i] + a[j] - b; alpar@1: alfa = 1.0 / (temp + u); alpar@1: beta = 2.0 - alfa * temp; alpar@1: /* compute violation of inequality (15) */ alpar@1: temp = x[i] + x[j] + alfa * y - beta; alpar@1: /* choose C providing maximum violation */ alpar@1: if (rmax < temp) alpar@1: { rmax = temp; alpar@1: cov[1] = i; alpar@1: cov[2] = j; alpar@1: *_alfa = alfa; alpar@1: *_beta = beta; alpar@1: ret = 1; alpar@1: } alpar@1: } alpar@1: } alpar@1: done: return ret; alpar@1: } alpar@1: alpar@1: static int cover3(int n, double a[], double b, double u, double x[], alpar@1: double y, int cov[], double *_alfa, double *_beta) alpar@1: { /* try to generate mixed cover cut using three-element cover */ alpar@1: int i, j, k, try = 0, ret = 0; alpar@1: double eps, alfa, beta, temp, rmax = 0.001; alpar@1: eps = 0.001 * (1.0 + fabs(b)); alpar@1: for (i = 0+1; i <= n; i++) alpar@1: for (j = i+1; j <= n; j++) alpar@1: for (k = j+1; k <= n; k++) alpar@1: { /* C = {i, j, k} */ alpar@1: try++; alpar@1: if (try > MAXTRY) goto done; alpar@1: /* check if condition (8) is satisfied */ alpar@1: if (a[i] + a[j] + a[k] + y > b + eps) alpar@1: { /* compute parameters for inequality (15) */ alpar@1: temp = a[i] + a[j] + a[k] - b; alpar@1: alfa = 1.0 / (temp + u); alpar@1: beta = 3.0 - alfa * temp; alpar@1: /* compute violation of inequality (15) */ alpar@1: temp = x[i] + x[j] + x[k] + alfa * y - beta; alpar@1: /* choose C providing maximum violation */ alpar@1: if (rmax < temp) alpar@1: { rmax = temp; alpar@1: cov[1] = i; alpar@1: cov[2] = j; alpar@1: cov[3] = k; alpar@1: *_alfa = alfa; alpar@1: *_beta = beta; alpar@1: ret = 1; alpar@1: } alpar@1: } alpar@1: } alpar@1: done: return ret; alpar@1: } alpar@1: alpar@1: static int cover4(int n, double a[], double b, double u, double x[], alpar@1: double y, int cov[], double *_alfa, double *_beta) alpar@1: { /* try to generate mixed cover cut using four-element cover */ alpar@1: int i, j, k, l, try = 0, ret = 0; alpar@1: double eps, alfa, beta, temp, rmax = 0.001; alpar@1: eps = 0.001 * (1.0 + fabs(b)); alpar@1: for (i = 0+1; i <= n; i++) alpar@1: for (j = i+1; j <= n; j++) alpar@1: for (k = j+1; k <= n; k++) alpar@1: for (l = k+1; l <= n; l++) alpar@1: { /* C = {i, j, k, l} */ alpar@1: try++; alpar@1: if (try > MAXTRY) goto done; alpar@1: /* check if condition (8) is satisfied */ alpar@1: if (a[i] + a[j] + a[k] + a[l] + y > b + eps) alpar@1: { /* compute parameters for inequality (15) */ alpar@1: temp = a[i] + a[j] + a[k] + a[l] - b; alpar@1: alfa = 1.0 / (temp + u); alpar@1: beta = 4.0 - alfa * temp; alpar@1: /* compute violation of inequality (15) */ alpar@1: temp = x[i] + x[j] + x[k] + x[l] + alfa * y - beta; alpar@1: /* choose C providing maximum violation */ alpar@1: if (rmax < temp) alpar@1: { rmax = temp; alpar@1: cov[1] = i; alpar@1: cov[2] = j; alpar@1: cov[3] = k; alpar@1: cov[4] = l; alpar@1: *_alfa = alfa; alpar@1: *_beta = beta; alpar@1: ret = 1; alpar@1: } alpar@1: } alpar@1: } alpar@1: done: return ret; alpar@1: } alpar@1: alpar@1: static int cover(int n, double a[], double b, double u, double x[], alpar@1: double y, int cov[], double *alfa, double *beta) alpar@1: { /* try to generate mixed cover cut; alpar@1: input (see (5)): alpar@1: n is the number of binary variables; alpar@1: a[1:n] are coefficients at binary variables; alpar@1: b is the right-hand side; alpar@1: u is upper bound of continuous variable; alpar@1: x[1:n] are values of binary variables at current point; alpar@1: y is value of continuous variable at current point; alpar@1: output (see (15), (16), (17)): alpar@1: cov[1:r] are indices of binary variables included in cover C, alpar@1: where r is the set cardinality returned on exit; alpar@1: alfa coefficient at continuous variable; alpar@1: beta is the right-hand side; */ alpar@1: int j; alpar@1: /* perform some sanity checks */ alpar@1: xassert(n >= 2); alpar@1: for (j = 1; j <= n; j++) xassert(a[j] > 0.0); alpar@1: #if 1 /* ??? */ alpar@1: xassert(b > -1e-5); alpar@1: #else alpar@1: xassert(b > 0.0); alpar@1: #endif alpar@1: xassert(u >= 0.0); alpar@1: for (j = 1; j <= n; j++) xassert(0.0 <= x[j] && x[j] <= 1.0); alpar@1: xassert(0.0 <= y && y <= u); alpar@1: /* try to generate mixed cover cut */ alpar@1: if (cover2(n, a, b, u, x, y, cov, alfa, beta)) return 2; alpar@1: if (cover3(n, a, b, u, x, y, cov, alfa, beta)) return 3; alpar@1: if (cover4(n, a, b, u, x, y, cov, alfa, beta)) return 4; alpar@1: return 0; alpar@1: } alpar@1: alpar@1: /*---------------------------------------------------------------------- alpar@1: -- lpx_cover_cut - generate mixed cover cut. alpar@1: -- alpar@1: -- SYNOPSIS alpar@1: -- alpar@1: -- #include "glplpx.h" alpar@1: -- int lpx_cover_cut(LPX *lp, int len, int ind[], double val[], alpar@1: -- double work[]); alpar@1: -- alpar@1: -- DESCRIPTION alpar@1: -- alpar@1: -- The routine lpx_cover_cut generates a mixed cover cut for a given alpar@1: -- row of the MIP problem. alpar@1: -- alpar@1: -- The given row of the MIP problem should be explicitly specified in alpar@1: -- the form: alpar@1: -- alpar@1: -- sum{j in J} a[j]*x[j] <= b. (1) alpar@1: -- alpar@1: -- On entry indices (ordinal numbers) of structural variables, which alpar@1: -- have non-zero constraint coefficients, should be placed in locations alpar@1: -- ind[1], ..., ind[len], and corresponding constraint coefficients alpar@1: -- should be placed in locations val[1], ..., val[len]. The right-hand alpar@1: -- side b should be stored in location val[0]. alpar@1: -- alpar@1: -- The working array work should have at least nb locations, where nb alpar@1: -- is the number of binary variables in (1). alpar@1: -- alpar@1: -- The routine generates a mixed cover cut in the same form as (1) and alpar@1: -- stores the cut coefficients and right-hand side in the same way as alpar@1: -- just described above. alpar@1: -- alpar@1: -- RETURNS alpar@1: -- alpar@1: -- If the cutting plane has been successfully generated, the routine alpar@1: -- returns 1 <= len' <= n, which is the number of non-zero coefficients alpar@1: -- in the inequality constraint. Otherwise, the routine returns zero. */ alpar@1: alpar@1: static int lpx_cover_cut(LPX *lp, int len, int ind[], double val[], alpar@1: double work[]) alpar@1: { int cov[1+4], j, k, nb, newlen, r; alpar@1: double f_min, f_max, alfa, beta, u, *x = work, y; alpar@1: /* substitute and remove fixed variables */ alpar@1: newlen = 0; alpar@1: for (k = 1; k <= len; k++) alpar@1: { j = ind[k]; alpar@1: if (lpx_get_col_type(lp, j) == LPX_FX) alpar@1: val[0] -= val[k] * lpx_get_col_lb(lp, j); alpar@1: else alpar@1: { newlen++; alpar@1: ind[newlen] = ind[k]; alpar@1: val[newlen] = val[k]; alpar@1: } alpar@1: } alpar@1: len = newlen; alpar@1: /* move binary variables to the beginning of the list so that alpar@1: elements 1, 2, ..., nb correspond to binary variables, and alpar@1: elements nb+1, nb+2, ..., len correspond to rest variables */ alpar@1: nb = 0; alpar@1: for (k = 1; k <= len; k++) alpar@1: { j = ind[k]; alpar@1: if (lpx_get_col_kind(lp, j) == LPX_IV && alpar@1: lpx_get_col_type(lp, j) == LPX_DB && alpar@1: lpx_get_col_lb(lp, j) == 0.0 && alpar@1: lpx_get_col_ub(lp, j) == 1.0) alpar@1: { /* binary variable */ alpar@1: int ind_k; alpar@1: double val_k; alpar@1: nb++; alpar@1: ind_k = ind[nb], val_k = val[nb]; alpar@1: ind[nb] = ind[k], val[nb] = val[k]; alpar@1: ind[k] = ind_k, val[k] = val_k; alpar@1: } alpar@1: } alpar@1: /* now the specified row has the form: alpar@1: sum a[j]*x[j] + sum a[j]*y[j] <= b, alpar@1: where x[j] are binary variables, y[j] are rest variables */ alpar@1: /* at least two binary variables are needed */ alpar@1: if (nb < 2) return 0; alpar@1: /* compute implied lower and upper bounds for sum a[j]*y[j] */ alpar@1: f_min = f_max = 0.0; alpar@1: for (k = nb+1; k <= len; k++) alpar@1: { j = ind[k]; alpar@1: /* both bounds must be finite */ alpar@1: if (lpx_get_col_type(lp, j) != LPX_DB) return 0; alpar@1: if (val[k] > 0.0) alpar@1: { f_min += val[k] * lpx_get_col_lb(lp, j); alpar@1: f_max += val[k] * lpx_get_col_ub(lp, j); alpar@1: } alpar@1: else alpar@1: { f_min += val[k] * lpx_get_col_ub(lp, j); alpar@1: f_max += val[k] * lpx_get_col_lb(lp, j); alpar@1: } alpar@1: } alpar@1: /* sum a[j]*x[j] + sum a[j]*y[j] <= b ===> alpar@1: sum a[j]*x[j] + (sum a[j]*y[j] - f_min) <= b - f_min ===> alpar@1: sum a[j]*x[j] + y <= b - f_min, alpar@1: where y = sum a[j]*y[j] - f_min; alpar@1: note that 0 <= y <= u, u = f_max - f_min */ alpar@1: /* determine upper bound of y */ alpar@1: u = f_max - f_min; alpar@1: /* determine value of y at the current point */ alpar@1: y = 0.0; alpar@1: for (k = nb+1; k <= len; k++) alpar@1: { j = ind[k]; alpar@1: y += val[k] * lpx_get_col_prim(lp, j); alpar@1: } alpar@1: y -= f_min; alpar@1: if (y < 0.0) y = 0.0; alpar@1: if (y > u) y = u; alpar@1: /* modify the right-hand side b */ alpar@1: val[0] -= f_min; alpar@1: /* now the transformed row has the form: alpar@1: sum a[j]*x[j] + y <= b, where 0 <= y <= u */ alpar@1: /* determine values of x[j] at the current point */ alpar@1: for (k = 1; k <= nb; k++) alpar@1: { j = ind[k]; alpar@1: x[k] = lpx_get_col_prim(lp, j); alpar@1: if (x[k] < 0.0) x[k] = 0.0; alpar@1: if (x[k] > 1.0) x[k] = 1.0; alpar@1: } alpar@1: /* if a[j] < 0, replace x[j] by its complement 1 - x'[j] */ alpar@1: for (k = 1; k <= nb; k++) alpar@1: { if (val[k] < 0.0) alpar@1: { ind[k] = - ind[k]; alpar@1: val[k] = - val[k]; alpar@1: val[0] += val[k]; alpar@1: x[k] = 1.0 - x[k]; alpar@1: } alpar@1: } alpar@1: /* try to generate a mixed cover cut for the transformed row */ alpar@1: r = cover(nb, val, val[0], u, x, y, cov, &alfa, &beta); alpar@1: if (r == 0) return 0; alpar@1: xassert(2 <= r && r <= 4); alpar@1: /* now the cut is in the form: alpar@1: sum{j in C} x[j] + alfa * y <= beta */ alpar@1: /* store the right-hand side beta */ alpar@1: ind[0] = 0, val[0] = beta; alpar@1: /* restore the original ordinal numbers of x[j] */ alpar@1: for (j = 1; j <= r; j++) cov[j] = ind[cov[j]]; alpar@1: /* store cut coefficients at binary variables complementing back alpar@1: the variables having negative row coefficients */ alpar@1: xassert(r <= nb); alpar@1: for (k = 1; k <= r; k++) alpar@1: { if (cov[k] > 0) alpar@1: { ind[k] = +cov[k]; alpar@1: val[k] = +1.0; alpar@1: } alpar@1: else alpar@1: { ind[k] = -cov[k]; alpar@1: val[k] = -1.0; alpar@1: val[0] -= 1.0; alpar@1: } alpar@1: } alpar@1: /* substitute y = sum a[j]*y[j] - f_min */ alpar@1: for (k = nb+1; k <= len; k++) alpar@1: { r++; alpar@1: ind[r] = ind[k]; alpar@1: val[r] = alfa * val[k]; alpar@1: } alpar@1: val[0] += alfa * f_min; alpar@1: xassert(r <= len); alpar@1: len = r; alpar@1: return len; alpar@1: } alpar@1: alpar@1: /*---------------------------------------------------------------------- alpar@1: -- lpx_eval_row - compute explictily specified row. alpar@1: -- alpar@1: -- SYNOPSIS alpar@1: -- alpar@1: -- #include "glplpx.h" alpar@1: -- double lpx_eval_row(LPX *lp, int len, int ind[], double val[]); alpar@1: -- alpar@1: -- DESCRIPTION alpar@1: -- alpar@1: -- The routine lpx_eval_row computes the primal value of an explicitly alpar@1: -- specified row using current values of structural variables. alpar@1: -- alpar@1: -- The explicitly specified row may be thought as a linear form: alpar@1: -- alpar@1: -- y = a[1]*x[m+1] + a[2]*x[m+2] + ... + a[n]*x[m+n], alpar@1: -- alpar@1: -- where y is an auxiliary variable for this row, a[j] are coefficients alpar@1: -- of the linear form, x[m+j] are structural variables. alpar@1: -- alpar@1: -- On entry column indices and numerical values of non-zero elements of alpar@1: -- the row should be stored in locations ind[1], ..., ind[len] and alpar@1: -- val[1], ..., val[len], where len is the number of non-zero elements. alpar@1: -- The array ind and val are not changed on exit. alpar@1: -- alpar@1: -- RETURNS alpar@1: -- alpar@1: -- The routine returns a computed value of y, the auxiliary variable of alpar@1: -- the specified row. */ alpar@1: alpar@1: static double lpx_eval_row(LPX *lp, int len, int ind[], double val[]) alpar@1: { int n = lpx_get_num_cols(lp); alpar@1: int j, k; alpar@1: double sum = 0.0; alpar@1: if (len < 0) alpar@1: xerror("lpx_eval_row: len = %d; invalid row length\n", len); alpar@1: for (k = 1; k <= len; k++) alpar@1: { j = ind[k]; alpar@1: if (!(1 <= j && j <= n)) alpar@1: xerror("lpx_eval_row: j = %d; column number out of range\n", alpar@1: j); alpar@1: sum += val[k] * lpx_get_col_prim(lp, j); alpar@1: } alpar@1: return sum; alpar@1: } alpar@1: alpar@1: /*********************************************************************** alpar@1: * NAME alpar@1: * alpar@1: * ios_cov_gen - generate mixed cover cuts alpar@1: * alpar@1: * SYNOPSIS alpar@1: * alpar@1: * #include "glpios.h" alpar@1: * void ios_cov_gen(glp_tree *tree); alpar@1: * alpar@1: * DESCRIPTION alpar@1: * alpar@1: * The routine ios_cov_gen generates mixed cover cuts for the current alpar@1: * point and adds them to the cut pool. */ alpar@1: alpar@1: void ios_cov_gen(glp_tree *tree) alpar@1: { glp_prob *prob = tree->mip; alpar@1: int m = lpx_get_num_rows(prob); alpar@1: int n = lpx_get_num_cols(prob); alpar@1: int i, k, type, kase, len, *ind; alpar@1: double r, *val, *work; alpar@1: xassert(lpx_get_status(prob) == LPX_OPT); alpar@1: /* allocate working arrays */ alpar@1: ind = xcalloc(1+n, sizeof(int)); alpar@1: val = xcalloc(1+n, sizeof(double)); alpar@1: work = xcalloc(1+n, sizeof(double)); alpar@1: /* look through all rows */ alpar@1: for (i = 1; i <= m; i++) alpar@1: for (kase = 1; kase <= 2; kase++) alpar@1: { type = lpx_get_row_type(prob, i); alpar@1: if (kase == 1) alpar@1: { /* consider rows of '<=' type */ alpar@1: if (!(type == LPX_UP || type == LPX_DB)) continue; alpar@1: len = lpx_get_mat_row(prob, i, ind, val); alpar@1: val[0] = lpx_get_row_ub(prob, i); alpar@1: } alpar@1: else alpar@1: { /* consider rows of '>=' type */ alpar@1: if (!(type == LPX_LO || type == LPX_DB)) continue; alpar@1: len = lpx_get_mat_row(prob, i, ind, val); alpar@1: for (k = 1; k <= len; k++) val[k] = - val[k]; alpar@1: val[0] = - lpx_get_row_lb(prob, i); alpar@1: } alpar@1: /* generate mixed cover cut: alpar@1: sum{j in J} a[j] * x[j] <= b */ alpar@1: len = lpx_cover_cut(prob, len, ind, val, work); alpar@1: if (len == 0) continue; alpar@1: /* at the current point the cut inequality is violated, i.e. alpar@1: sum{j in J} a[j] * x[j] - b > 0 */ alpar@1: r = lpx_eval_row(prob, len, ind, val) - val[0]; alpar@1: if (r < 1e-3) continue; alpar@1: /* add the cut to the cut pool */ alpar@1: glp_ios_add_row(tree, NULL, GLP_RF_COV, 0, len, ind, val, alpar@1: GLP_UP, val[0]); alpar@1: } alpar@1: /* free working arrays */ alpar@1: xfree(ind); alpar@1: xfree(val); alpar@1: xfree(work); alpar@1: return; alpar@1: } alpar@1: alpar@1: /* eof */