lp.c
Go to the documentation of this file.
41/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
72 * using the LP solver activity is potentially faster, but may not be consistent with the SCIP_ROW calculations
518 /* we do not save the farkas coefficient, since it can be recomputed; thus, we invalidate it here */
521 /* if the column was created after performing the storage (possibly during probing), we treat it as implicitly zero;
606 /* if the row was created after performing the storage (possibly during probing), we treat it as basic;
656#ifdef SCIP_MORE_DEBUG /* enable this to check the sortings within rows (for debugging, very slow!) */
806 /* we are only interested in variables with a finite impact, because the infinity counters should be correct */
843 /* we are only interested in variables with a finite impact, because the infinity counters should be correct */
861/* recompute the global pseudo solution value from scratch, if it was marked to be unreliable before */
885 /* we are only interested in variables with a finite impact, because the infinity counters should be correct */
967/** sorts column entries of linked rows currently in the LP such that lower row indices precede higher ones */
998/** sorts column entries of unlinked rows or rows currently not in the LP such that lower row indices precede higher
1015 SCIPsortPtrRealInt((void**)(&(col->rows[col->nlprows])), &(col->vals[col->nlprows]), &(col->linkpos[col->nlprows]), SCIProwComp, col->len - col->nlprows);
1031/** sorts row entries of linked columns currently in the LP such that lower column indices precede higher ones */
1046 SCIPsortIntPtrIntReal(row->cols_index, (void**)row->cols, row->linkpos, row->vals, row->nlpcols);
1062/** sorts row entries of unlinked columns or columns currently not in the LP such that lower column indices precede
1081 SCIPsortIntPtrIntReal(&(row->cols_index[row->nlpcols]), (void**)(&(row->cols[row->nlpcols])), &(row->linkpos[row->nlpcols]), &(row->vals[row->nlpcols]), row->len - row->nlpcols);
1099/** searches coefficient in part of the column, returns position in col vector or -1 if not found */
1174/** searches coefficient in part of the row, returns position in col vector or -1 if not found */
1266/** moves a coefficient in a column to a different place, and updates all corresponding data structures */
1362/** moves a coefficient in a row to a different place, and updates all corresponding data structures */
1483 if( (row->eventfilter->len > 0 && (row->eventfilter->eventmask & SCIP_EVENTTYPE_ROWCOEFCHANGED) != 0) )
1488 SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, row->eventfilter, &event) );
1511 if( (row->eventfilter->len > 0 && (row->eventfilter->eventmask & SCIP_EVENTTYPE_ROWCONSTCHANGED)) )
1516 SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, row->eventfilter, &event) );
1540 if( (row->eventfilter->len > 0 && !(row->eventfilter->eventmask & SCIP_EVENTTYPE_ROWSIDECHANGED)) )
1545 SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, row->eventfilter, &event) );
1551#ifdef SCIP_MORE_DEBUG /* enable this to check links between columns and rows in LP data structure (for debugging, very slow!) */
1717 /*assert(colSearchCoef(col, row) == -1);*/ /* this assert would lead to slight differences in the solution process */
1727 /* if the row is in current LP and is linked to the column, we have to insert it at the end of the linked LP rows
1741 /* in case the coefficient is integral w.r.t. numerics we explicitly round the coefficient to an integral value */
1752 /* if the column is in current LP, we have to link it to the row, because otherwise, the primal information
1757 /* this call might swap the current row with the first non-LP/not linked row, s.t. insertion position
1779 /* if the column is in current LP, now both conditions, row->cols[linkpos]->lppos >= 0 and row->linkpos[linkpos] >= 0
1811 SCIPsetDebugMsg(set, "added coefficient %g * <%s> at position %d (%d/%d) to column <%s> (nunlinked=%d)\n",
1845 /* if row is a linked LP row, move last linked LP coefficient to position of empty slot (deleted coefficient) */
1881 /* in case the coefficient is integral w.r.t. numerics we explicitly round the coefficient to an integral value */
1927 /* Euclidean norm, sum norm, and objective function scalar product only take LP columns into account */
2012 /* Euclidean norm, sum norm, and objective function scalar product only take LP columns into account */
2063 /*assert(rowSearchCoef(row, col) == -1);*/ /* this assert would lead to slight differences in the solution process */
2078 /* if the column is in current LP and is linked to the row, we have to insert it at the end of the linked LP columns
2092 /* in case the coefficient is integral w.r.t. numerics we explicitly round the coefficient to an integral value */
2105 /* if the row is in current LP, we have to link it to the column, because otherwise, the dual information
2110 /* this call might swap the current column with the first non-LP/not linked column, s.t. insertion position
2132 /* if the row is in current LP, now both conditions, col->rows[linkpos]->lppos >= 0 and col->linkpos[linkpos] >= 0
2173 SCIPsetDebugMsg(set, "added coefficient %g * <%s> at position %d (%d/%d) to row <%s> (nunlinked=%d)\n",
2211 SCIPerrorMessage("cannot delete a coefficient from the locked unmodifiable row <%s>\n", row->name);
2218 /* if column is a linked LP column, move last linked LP coefficient to position of empty slot (deleted coefficient) */
2264 SCIPerrorMessage("cannot change a coefficient of the locked unmodifiable row <%s>\n", row->name);
2268 /* in case the coefficient is integral w.r.t. numerics we explicitly round the coefficient to an integral value */
2378 /* this call might swap the current row with the first non-LP/not linked row, but this is of no harm */
2383 assert(col->nlprows == 0 || col->rows[col->nlprows-1]->cols[col->linkpos[col->nlprows-1]] == col);
2384 assert(col->nlprows == 0 || col->rows[col->nlprows-1]->linkpos[col->linkpos[col->nlprows-1]] == col->nlprows-1);
2458 /* this call might swap the current column with the first non-LP/not linked column, but this is of no harm */
2463 assert(row->nlpcols == 0 || row->cols[row->nlpcols-1]->rows[row->linkpos[row->nlpcols-1]] == row);
2464 assert(row->nlpcols == 0 || row->cols[row->nlpcols-1]->linkpos[row->linkpos[row->nlpcols-1]] == row->nlpcols-1);
2579/** checks, that parameter of type int in LP solver has the given value, ignoring unknown parameters */
2604/** checks, that parameter of type SCIP_Bool in LP solver has the given value, ignoring unknown parameters */
2615/** checks, that parameter of type SCIP_Real in LP solver has the given value, ignoring unknown parameters */
2646#define lpCutoffDisabled(set,prob) (set->lp_disablecutoff == 1 || ((set->nactivepricers > 0 || !SCIPprobAllColsInLP(prob, set, lp)) && set->lp_disablecutoff == 2))
2667 /* We disabled the objective limit in the LP solver or we want so solve exactly and thus cannot rely on the LP
2668 * solver's objective limit handling, so we make sure that the objective limit is inactive (infinity). */
2685 /* check whether the parameter was actually changed or already was at the boundary of the LP solver's parameter range */
2724 /* check whether the parameter was actually changed or already was at the boundary of the LP solver's parameter range */
2767 /* check whether the parameter was actually changed or already was at the boundary of the LP solver's parameter range */
2810 /* check whether the parameter was actually changed or already was at the boundary of the LP solver's parameter range */
2879 /* We might only set lp->solved to false if fastmip is turned off, since the latter should be the more
3048/** sets the pricing strategy of the LP solver (given the character representation of the strategy) */
3176 assert((int) SCIP_CLOCKTYPE_CPU == 1 && (int) SCIP_CLOCKTYPE_WALL == 2); /*lint !e506*//*lint !e1564*/
3208 /* we don't check this parameter because SoPlex will always return its current random seed, not the initial one */
3419 SCIPmessageFPrintInfo(messagehdlr, file, "(obj: %.15g) [%.15g,%.15g], ", col->obj, col->lb, col->ub);
3433/** sorts column entries such that LP rows precede non-LP rows and inside both parts lower row indices precede higher ones
3489 SCIPerrorMessage("coefficient for row <%s> doesn't exist in column <%s>\n", row->name, SCIPvarGetName(col->var));
3605 SCIP_CALL( rowChgCoefPos(row, blkmem, set, eventqueue, lp, col->linkpos[pos], col->vals[pos] + incval) );
3640 * @note: Here we only consider cancellations which can occur during decreasing the oldvalue to newvalue; not the
3679 if( SCIPsetIsLT(set, lp->objsqrnorm, 0.0) || isNewValueUnreliable(set, lp->objsqrnorm, oldvalue) )
3685 /* due to numerical troubles it still can appear that lp->objsqrnorm is a little bit smaller than 0 */
3711 SCIPsetDebugMsg(set, "changing objective value of column <%s> from %f to %f\n", SCIPvarGetName(col->var), col->obj, newobj);
3727 /* in any case, when the sign of the objective (and thereby the best bound) changes, the variable has to enter the
3741 /* update original objective value, as long as we are not in diving or probing and changed objective values */
3770 SCIPsetDebugMsg(set, "changing lower bound of column <%s> from %f to %f\n", SCIPvarGetName(col->var), col->lb, newlb);
3786 /* in any case, when the best bound is zero and gets changed, the variable has to enter the LP and the LP has to be
3815 SCIPsetDebugMsg(set, "changing upper bound of column <%s> from %f to %f\n", SCIPvarGetName(col->var), col->ub, newub);
3831 /* in any case, when the best bound is zero and gets changed, the variable has to enter the LP and the LP has to be
4029/** calculates the Farkas coefficient y^T A_i of a column i using the given dual Farkas vector y */
4158/** gets the Farkas value of a column in last LP (which must be infeasible), i.e. the Farkas coefficient y^T A_i times
4311 SCIP_Bool* downvalid, /**< stores whether the returned down value is a valid dual bound, or NULL;
4369 /* if a loose variables has an infinite best bound, the LP bound is -infinity and no gain can be achieved */
4396 retcode = SCIPlpiStrongbranchInt(lp->lpi, col->lpipos, col->primsol, itlim, down == NULL ? NULL : &sbdown, up == NULL ? NULL : &sbup, &sbdownvalid, &sbupvalid, &iter);
4400 retcode = SCIPlpiStrongbranchFrac(lp->lpi, col->lpipos, col->primsol, itlim, down == NULL ? NULL : &sbdown, up == NULL ? NULL : &sbup, &sbdownvalid, &sbupvalid, &iter);
4433 iter = stat->ndualresolvelps > 0 ? (int)(2*stat->ndualresolvelpiterations / stat->ndualresolvelps)
4435 : stat->nprimalresolvelps > 0 ? (int)(2*stat->nprimalresolvelpiterations / stat->nprimalresolvelps)
4495 SCIP_Bool* downvalid, /**< stores whether the returned down values are valid dual bounds, or NULL;
4568 /* if a loose variables has an infinite best bound, the LP bound is -infinity and no gain can be achieved */
4596 SCIPsetDebugMsg(set, "performing strong branching on %d variables with %d iterations\n", ncols, itlim);
4600 retcode = SCIPlpiStrongbranchesInt(lp->lpi, lpipos, nsubcols, primsols, itlim, sbdown, sbup, sbdownvalid, sbupvalid, &iter);
4602 retcode = SCIPlpiStrongbranchesFrac(lp->lpi, lpipos, nsubcols, primsols, itlim, sbdown, sbup, sbdownvalid, sbupvalid, &iter);
4671 iter = stat->ndualresolvelps > 0 ? (int)(2*stat->ndualresolvelpiterations / stat->ndualresolvelps)
4673 : stat->nprimalresolvelps > 0 ? (int)(2*stat->nprimalresolvelpiterations / stat->nprimalresolvelps)
4705 * keep in mind, that the returned old values may have nothing to do with the current LP solution
4711 SCIP_Bool* downvalid, /**< stores whether the returned down value is a valid dual bound, or NULL;
4715 SCIP_Real* solval, /**< stores LP solution value of column at last strong branching call, or NULL */
4735/** if strong branching was already applied on the column at the current node, returns the number of LPs solved after
4750/** marks a column to be not removable from the LP in the current node because it became obsolete */
4760 /* lpRemoveObsoleteCols() does not remove a column if the node number stored in obsoletenode equals the current node number */
4898/** checks, whether the given scalar scales the given value to an integral number with error in the given bounds */
4903 SCIP_Real mindelta, /**< minimal relative allowed difference of scaled coefficient s*c and integral i */
4904 SCIP_Real maxdelta, /**< maximal relative allowed difference of scaled coefficient s*c and integral i */
4937 * if the row's activity is proven to be integral, the sides are automatically rounded to the next integer
4948 SCIP_Bool integralcontvars, /**< should the coefficients of the continuous variables also be made integral,
4950 SCIP_Real minrounddelta, /**< minimal relative difference of scaled coefficient s*c and integral i,
4952 SCIP_Real maxrounddelta /**< maximal relative difference of scaled coefficient s*c and integral i
4976 SCIPsetDebugMsg(set, "scale row <%s> with %g (tolerance=[%g,%g])\n", row->name, scaleval, minrounddelta, maxrounddelta);
4984 /* scale the row coefficients, thereby recalculating whether the row's activity is always integral;
4985 * if the row coefficients are rounded to the nearest integer value, calculate the maximal activity difference,
4997 /* get local or global bounds for column, depending on the local or global feasibility of the row */