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