16 #ifndef OR_TOOLS_LP_DATA_LP_UTILS_H_
17 #define OR_TOOLS_LP_DATA_LP_UTILS_H_
41 return std::abs(f - std::round(f));
46 template <
class DenseRowOrColumn1,
class DenseRowOrColumn2>
48 const DenseRowOrColumn2& v) {
49 DCHECK_EQ(u.size().value(), v.size().value());
51 typename DenseRowOrColumn1::IndexType i(0);
52 typename DenseRowOrColumn2::IndexType j(0);
53 const size_t num_blocks = u.size().value() / 4;
54 for (
size_t block = 0; block < num_blocks; ++block) {
68 sum += (u[i++] * v[j++]) + (u[i++] * v[j++]) + (u[i++] * v[j++]) +
71 while (i < u.size()) {
72 sum += u[i++] * v[j++];
81 template <
class DenseRowOrColumn>
85 sum += u[
typename DenseRowOrColumn::IndexType(e.row().value())] *
91 template <
class DenseRowOrColumn,
class DenseRowOrColumn2>
93 const DenseRowOrColumn2& v) {
94 DCHECK_EQ(u.size().value(), v.size().value());
96 for (
typename DenseRowOrColumn::IndexType i(0); i < u.size(); ++i) {
97 sum.
Add(u[i] * v[
typename DenseRowOrColumn2::IndexType(i.value())]);
102 template <
class DenseRowOrColumn>
107 sum.
Add(u[
typename DenseRowOrColumn::IndexType(e.row().value())] *
113 template <
class DenseRowOrColumn>
121 for (
const auto e : v) {
122 sum.
Add(u[
typename DenseRowOrColumn::IndexType(e.row().value())] *
129 template <
class DenseRowOrColumn>
134 if (e.row().value() >= max_index) {
137 sum += u[
typename DenseRowOrColumn::IndexType(e.row().value())] *
178 RowIndex* row_index);
208 template <
typename IndexType>
210 std::vector<IndexType>* non_zeros) {
212 const IndexType end =
input.size();
215 non_zeros->push_back(
index);
221 template <
typename Container>
224 if (
value != 0.0)
return false;
230 template <
typename BoolVector>
232 return std::all_of(v.begin(), v.end(), [](
bool value) { return !value; });
236 template <
typename IndexType,
typename PermutationIndexType>
242 const IndexType size = input_output->
size();
243 zero_scratchpad->
swap(*input_output);
244 input_output->
resize(size, 0.0);
248 const IndexType permuted_index(
249 permutation[PermutationIndexType(
index.value())].value());
250 (*input_output)[permuted_index] =
value;
253 zero_scratchpad->
assign(size, 0.0);
258 template <
typename IndexType>
263 std::vector<IndexType>* non_zeros) {
265 zero_scratchpad->
swap(*output);
267 for (IndexType& index_ref : *non_zeros) {
269 (*zero_scratchpad)[index_ref] = 0.0;
270 const IndexType permuted_index(permutation[index_ref]);
271 (*output)[permuted_index] =
value;
272 index_ref = permuted_index;
277 template <
typename IndexType,
typename ScatteredRowOrCol>
279 ScatteredRowOrCol* v) {
283 const double kSparseThreshold = 0.05;
284 if (!v->non_zeros.empty() &&
285 v->non_zeros.size() < kSparseThreshold * size.value()) {
286 for (
const IndexType
index : v->non_zeros) {
290 v->values.resize(size, 0.0);
293 v->values.AssignToZero(size);
295 v->non_zeros.clear();
299 template <
typename IndexType>
301 const IndexType end = data->
size();
302 for (IndexType i(0); i < end; ++i) {
303 (*data)[i] = -(*data)[i];
320 template <
bool supported_infinity_is_positive>
326 if (num_infinities_ > 1)
return;
336 if (num_infinities_ > 0)
return Infinity();
342 if (num_infinities_ > 0)
return Infinity();
343 return sum_.
Value() - x;
346 if (num_infinities_ > 1)
return Infinity();
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
void swap(StrongVector &x)
void Add(const FpNumber &value)
typename Iterator::Entry Entry
void resize(IntType size)
void assign(IntType size, const T &v)
Fractional SumWithout(Fractional x) const
void PermuteWithScratchpad(const Permutation< PermutationIndexType > &permutation, StrictITIVector< IndexType, Fractional > *zero_scratchpad, StrictITIVector< IndexType, Fractional > *input_output)
Fractional Square(Fractional f)
Fractional PreciseSquaredNorm(const SparseColumn &v)
Fractional InfinityNorm(const DenseColumn &v)
Fractional SquaredNorm(const SparseColumn &v)
bool IsAllZero(const Container &input)
AccurateSum< Fractional > KahanSum
Fractional ScalarProduct(const DenseRowOrColumn1 &u, const DenseRowOrColumn2 &v)
void ComputeNonZeros(const StrictITIVector< IndexType, Fractional > &input, std::vector< IndexType > *non_zeros)
Fractional PreciseScalarProduct(const DenseRowOrColumn &u, const DenseRowOrColumn2 &v)
StrictITIVector< ColIndex, Fractional > DenseRow
void RemoveNearZeroEntries(Fractional threshold, DenseRow *row)
SumWithOneMissing< false > SumWithNegativeInfiniteAndOneMissing
bool IsAllFalse(const BoolVector &v)
void PermuteWithKnownNonZeros(const Permutation< IndexType > &permutation, StrictITIVector< IndexType, Fractional > *zero_scratchpad, StrictITIVector< IndexType, Fractional > *output, std::vector< IndexType > *non_zeros)
double Density(const DenseRow &row)
void SetSupportToFalse(const ColumnView &column, DenseBooleanColumn *b)
bool IsFinite(Fractional value)
bool IsDominated(const ColumnView &column, const DenseColumn &radius)
void ClearAndResizeVectorWithNonZeros(IndexType size, ScatteredRowOrCol *v)
const DenseRow & Transpose(const DenseColumn &col)
RowIndex ColToRowIndex(ColIndex col)
void ChangeSign(StrictITIVector< IndexType, Fractional > *data)
static Fractional Fractionality(Fractional f)
Fractional PartialScalarProduct(const DenseRowOrColumn &u, const SparseColumn &v, int max_index)
Fractional RestrictedInfinityNorm(const ColumnView &column, const DenseBooleanColumn &rows_to_consider, RowIndex *row_index)
StrictITIVector< RowIndex, Fractional > DenseColumn
SumWithOneMissing< true > SumWithPositiveInfiniteAndOneMissing
StrictITIVector< RowIndex, bool > DenseBooleanColumn
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
static int input(yyscan_t yyscanner)
bool ShouldUseDenseIteration(double ratio_for_using_dense_representation) const
StrictITIVector< Index, Fractional > values