lp.c
Go to the documentation of this file.
32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
63 * using the LP solver activity is potentially faster, but may not be consistent with the SCIP_ROW calculations
509 /* we do not save the farkas coefficient, since it can be recomputed; thus, we invalidate it here */
512 /* if the column was created after performing the storage (possibly during probing), we treat it as implicitly zero;
597 /* if the row was created after performing the storage (possibly during probing), we treat it as basic;
647 #ifdef SCIP_MORE_DEBUG /* enable this to check the sortings within rows (for debugging, very slow!) */
768 /* recompute the loose objective value from scratch, if it was marked to be unreliable before */
797 /* we are only interested in variables with a finite impact, because the infinity counters should be correct */
810 /* recompute the pseudo solution value from scratch, if it was marked to be unreliable before */
834 /* we are only interested in variables with a finite impact, because the infinity counters should be correct */
852 /* recompute the global pseudo solution value from scratch, if it was marked to be unreliable before */
876 /* we are only interested in variables with a finite impact, because the infinity counters should be correct */
958 /** sorts column entries of linked rows currently in the LP such that lower row indices precede higher ones */
989 /** sorts column entries of unlinked rows or rows currently not in the LP such that lower row indices precede higher
1006 SCIPsortPtrRealInt((void**)(&(col->rows[col->nlprows])), &(col->vals[col->nlprows]), &(col->linkpos[col->nlprows]), SCIProwComp, col->len - col->nlprows);
1022 /** sorts row entries of linked columns currently in the LP such that lower column indices precede higher ones */
1037 SCIPsortIntPtrIntReal(row->cols_index, (void**)row->cols, row->linkpos, row->vals, row->nlpcols);
1053 /** sorts row entries of unlinked columns or columns currently not in the LP such that lower column indices precede
1072 SCIPsortIntPtrIntReal(&(row->cols_index[row->nlpcols]), (void**)(&(row->cols[row->nlpcols])), &(row->linkpos[row->nlpcols]), &(row->vals[row->nlpcols]), row->len - row->nlpcols);
1090 /** searches coefficient in part of the column, returns position in col vector or -1 if not found */
1165 /** searches coefficient in part of the row, returns position in col vector or -1 if not found */
1257 /** moves a coefficient in a column to a different place, and updates all corresponding data structures */
1353 /** moves a coefficient in a row to a different place, and updates all corresponding data structures */
1474 if( (row->eventfilter->len > 0 && (row->eventfilter->eventmask & SCIP_EVENTTYPE_ROWCOEFCHANGED) != 0) )
1479 SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, row->eventfilter, &event) );
1502 if( (row->eventfilter->len > 0 && (row->eventfilter->eventmask & SCIP_EVENTTYPE_ROWCONSTCHANGED)) )
1507 SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, row->eventfilter, &event) );
1531 if( (row->eventfilter->len > 0 && !(row->eventfilter->eventmask & SCIP_EVENTTYPE_ROWSIDECHANGED)) )
1536 SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, row->eventfilter, &event) );
1542 #ifdef SCIP_MORE_DEBUG /* enable this to check links between columns and rows in LP data structure (for debugging, very slow!) */
1708 /*assert(colSearchCoef(col, row) == -1);*/ /* this assert would lead to slight differences in the solution process */
1718 /* 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
1732 /* in case the coefficient is integral w.r.t. numerics we explicitly round the coefficient to an integral value */
1743 /* if the column is in current LP, we have to link it to the row, because otherwise, the primal information
1748 /* this call might swap the current row with the first non-LP/not linked row, s.t. insertion position
1770 /* if the column is in current LP, now both conditions, row->cols[linkpos]->lppos >= 0 and row->linkpos[linkpos] >= 0
1802 SCIPsetDebugMsg(set, "added coefficient %g * <%s> at position %d (%d/%d) to column <%s> (nunlinked=%d)\n",
1836 /* if row is a linked LP row, move last linked LP coefficient to position of empty slot (deleted coefficient) */
1872 /* in case the coefficient is integral w.r.t. numerics we explicitly round the coefficient to an integral value */
1918 /* Euclidean norm, sum norm, and objective function scalar product only take LP columns into account */
2003 /* Euclidean norm, sum norm, and objective function scalar product only take LP columns into account */
2054 /*assert(rowSearchCoef(row, col) == -1);*/ /* this assert would lead to slight differences in the solution process */
2069 /* 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
2083 /* in case the coefficient is integral w.r.t. numerics we explicitly round the coefficient to an integral value */
2096 /* if the row is in current LP, we have to link it to the column, because otherwise, the dual information
2101 /* this call might swap the current column with the first non-LP/not linked column, s.t. insertion position
2123 /* if the row is in current LP, now both conditions, col->rows[linkpos]->lppos >= 0 and col->linkpos[linkpos] >= 0
2164 SCIPsetDebugMsg(set, "added coefficient %g * <%s> at position %d (%d/%d) to row <%s> (nunlinked=%d)\n",
2202 SCIPerrorMessage("cannot delete a coefficient from the locked unmodifiable row <%s>\n", row->name);
2209 /* if column is a linked LP column, move last linked LP coefficient to position of empty slot (deleted coefficient) */
2255 SCIPerrorMessage("cannot change a coefficient of the locked unmodifiable row <%s>\n", row->name);
2259 /* in case the coefficient is integral w.r.t. numerics we explicitly round the coefficient to an integral value */
2370 /* this call might swap the current row with the first non-LP/not linked row, but this is of no harm */
2375 assert(col->nlprows == 0 || col->rows[col->nlprows-1]->cols[col->linkpos[col->nlprows-1]] == col);
2376 assert(col->nlprows == 0 || col->rows[col->nlprows-1]->linkpos[col->linkpos[col->nlprows-1]] == col->nlprows-1);
2452 /* this call might swap the current column with the first non-LP/not linked column, but this is of no harm */
2457 assert(row->nlpcols == 0 || row->cols[row->nlpcols-1]->rows[row->linkpos[row->nlpcols-1]] == row);
2458 assert(row->nlpcols == 0 || row->cols[row->nlpcols-1]->linkpos[row->linkpos[row->nlpcols-1]] == row->nlpcols-1);
2574 /** checks, that parameter of type int in LP solver has the given value, ignoring unknown parameters */
2599 /** checks, that parameter of type SCIP_Bool in LP solver has the given value, ignoring unknown parameters */
2610 /** checks, that parameter of type SCIP_Real in LP solver has the given value, ignoring unknown parameters */
2641 #define lpCutoffDisabled(set) (set->lp_disablecutoff == 1 || (set->nactivepricers > 0 && set->lp_disablecutoff == 2))
2661 /* We disabled the objective limit in the LP solver or we want so solve exactly and thus cannot rely on the LP
2662 * solver's objective limit handling, so we return here and do not apply the objective limit. */
2679 /* check whether the parameter was actually changed or already was at the boundary of the LP solver's parameter range */
2718 /* check whether the parameter was actually changed or already was at the boundary of the LP solver's parameter range */
2761 /* check whether the parameter was actually changed or already was at the boundary of the LP solver's parameter range */
2804 /* check whether the parameter was actually changed or already was at the boundary of the LP solver's parameter range */
2873 /* We might only set lp->solved to false if fastmip is turned off, since the latter should be the more
3042 /** sets the pricing strategy of the LP solver (given the character representation of the strategy) */
3202 /* we don't check this parameter because SoPlex will always return its current random seed, not the initial one */
3413 SCIPmessageFPrintInfo(messagehdlr, file, "(obj: %.15g) [%.15g,%.15g], ", col->obj, col->lb, col->ub);
3427 /** sorts column entries such that LP rows precede non-LP rows and inside both parts lower row indices precede higher ones
3483 SCIPerrorMessage("coefficient for row <%s> doesn't exist in column <%s>\n", row->name, SCIPvarGetName(col->var));
3599 SCIP_CALL( rowChgCoefPos(row, blkmem, set, eventqueue, lp, col->linkpos[pos], col->vals[pos] + incval) );
3634 * @note: Here we only consider cancellations which can occur during decreasing the oldvalue to newvalue; not the
3673 if( SCIPsetIsLT(set, lp->objsqrnorm, 0.0) || isNewValueUnreliable(set, lp->objsqrnorm, oldvalue) )
3679 /* due to numerical troubles it still can appear that lp->objsqrnorm is a little bit smaller than 0 */
3705 SCIPsetDebugMsg(set, "changing objective value of column <%s> from %f to %f\n", SCIPvarGetName(col->var), col->obj, newobj);
3721 /* in any case, when the sign of the objective (and thereby the best bound) changes, the variable has to enter the
3735 /* update original objective value, as long as we are not in diving or probing and changed objective values */
3764 SCIPsetDebugMsg(set, "changing lower bound of column <%s> from %f to %f\n", SCIPvarGetName(col->var), col->lb, newlb);
3780 /* 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
3809 SCIPsetDebugMsg(set, "changing upper bound of column <%s> from %f to %f\n", SCIPvarGetName(col->var), col->ub, newub);
3825 /* 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
4023 /** calculates the Farkas coefficient y^T A_i of a column i using the given dual Farkas vector y */
4152 /** gets the Farkas value of a column in last LP (which must be infeasible), i.e. the Farkas coefficient y^T A_i times
4305 SCIP_Bool* downvalid, /**< stores whether the returned down value is a valid dual bound, or NULL;
4363 /* if a loose variables has an infinite best bound, the LP bound is -infinity and no gain can be achieved */
4390 retcode = SCIPlpiStrongbranchInt(lp->lpi, col->lpipos, col->primsol, itlim, down == NULL ? NULL : &sbdown, up == NULL ? NULL : &sbup, &sbdownvalid, &sbupvalid, &iter);
4394 retcode = SCIPlpiStrongbranchFrac(lp->lpi, col->lpipos, col->primsol, itlim, down == NULL ? NULL : &sbdown, up == NULL ? NULL : &sbup, &sbdownvalid, &sbupvalid, &iter);
4427 iter = stat->ndualresolvelps > 0 ? (int)(2*stat->ndualresolvelpiterations / stat->ndualresolvelps)
4429 : stat->nprimalresolvelps > 0 ? (int)(2*stat->nprimalresolvelpiterations / stat->nprimalresolvelps)
4489 SCIP_Bool* downvalid, /**< stores whether the returned down values are valid dual bounds, or NULL;
4562 /* if a loose variables has an infinite best bound, the LP bound is -infinity and no gain can be achieved */
4590 SCIPsetDebugMsg(set, "performing strong branching on %d variables with %d iterations\n", ncols, itlim);
4594 retcode = SCIPlpiStrongbranchesInt(lp->lpi, lpipos, nsubcols, primsols, itlim, sbdown, sbup, sbdownvalid, sbupvalid, &iter);
4596 retcode = SCIPlpiStrongbranchesFrac(lp->lpi, lpipos, nsubcols, primsols, itlim, sbdown, sbup, sbdownvalid, sbupvalid, &iter);
4665 iter = stat->ndualresolvelps > 0 ? (int)(2*stat->ndualresolvelpiterations / stat->ndualresolvelps)
4667 : stat->nprimalresolvelps > 0 ? (int)(2*stat->nprimalresolvelpiterations / stat->nprimalresolvelps)
4699 * keep in mind, that the returned old values may have nothing to do with the current LP solution
4705 SCIP_Bool* downvalid, /**< stores whether the returned down value is a valid dual bound, or NULL;
4709 SCIP_Real* solval, /**< stores LP solution value of column at last strong branching call, or NULL */
4729 /** if strong branching was already applied on the column at the current node, returns the number of LPs solved after
4744 /** marks a column to be not removable from the LP in the current node because it became obsolete */
4754 /* lpRemoveObsoleteCols() does not remove a column if the node number stored in obsoletenode equals the current node number */
4892 /** checks, whether the given scalar scales the given value to an integral number with error in the given bounds */
4897 SCIP_Real mindelta, /**< minimal relative allowed difference of scaled coefficient s*c and integral i */
4898 SCIP_Real maxdelta, /**< maximal relative allowed difference of scaled coefficient s*c and integral i */
4931 * if the row's activity is proven to be integral, the sides are automatically rounded to the next integer
4942 SCIP_Bool integralcontvars, /**< should the coefficients of the continuous variables also be made integral,
4944 SCIP_Real minrounddelta, /**< minimal relative difference of scaled coefficient s*c and integral i,
4946 SCIP_Real maxrounddelta /**< maximal relative difference of scaled coefficient s*c and integral i
4970 SCIPsetDebugMsg(set, "scale row <%s> with %g (tolerance=[%g,%g])\n", row->name, scaleval, minrounddelta, maxrounddelta);
4978 /* scale the row coefficients, thereby recalculating whether the row's activity is always integral;
4979 * if the row coefficients are rounded to the nearest integer value, calculate the maximal activity difference,
4991 /* get local or global bounds for column, depending on the local or global feasibility of the row */
5055 /* scale the row sides, and move the constant to the sides; relax the sides with accumulated delta in order
5092 for( c = 0; c < row->len && SCIPcolIsIntegral(row->cols[c]) && SCIPsetIsIntegral(set, row->vals[c]); ++c )
5116 void* origin, /**< pointer to constraint handler or separator who created the row (NULL if unkown) */
5118 SCIP_Bool modifiable, /**< is row modifiable during node processing (subject to column generation)? */
5128 * in case, for example, lhs > rhs but they are equal with tolerances, one could pass lhs=rhs=lhs+rhs/2 to
5320 SCIPmessageFPrintInfo(messagehdlr, file, "%+.15g<%s> ", row->vals[i], SCIPvarGetName(row->cols[i]->var));
5340 SCIPdebugMessage("capture row <%s> with nuses=%d and nlocks=%u\n", row->name, row->nuses, row->nlocks);
5358 SCIPsetDebugMsg(set, "release row <%s> with nuses=%d and nlocks=%u\n", (*row)->name, (*row)->nuses, (*row)->nlocks);
5370 /** locks an unmodifiable row, which forbids further changes; has no effect on modifiable rows */
5380 SCIPdebugMessage("lock row <%s> with nuses=%d and nlocks=%u\n", row->name, row->nuses, row->nlocks);
5385 /** unlocks a lock of an unmodifiable row; a row with no sealed lock may be modified; has no effect on modifiable rows */
5395 SCIPdebugMessage("unlock row <%s> with nuses=%d and nlocks=%u\n", row->name, row->nuses, row->nlocks);
5445 SCIPerrorMessage("coefficient for column <%s> doesn't exist in row <%s>\n", SCIPvarGetName(col->var), row->name);