OR-Tools  8.2
lp_types.h
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14// Common types and constants used by the Linear Programming solver.
15
16#ifndef OR_TOOLS_LP_DATA_LP_TYPES_H_
17#define OR_TOOLS_LP_DATA_LP_TYPES_H_
18
19#include <cmath>
20#include <limits>
21
26#include "ortools/util/bitset.h"
27
28// We use typedefs as much as possible to later permit the usage of
29// types such as quad-doubles or rationals.
30
31namespace operations_research {
32namespace glop {
33
34// This type is defined to avoid cast issues during index conversions,
35// e.g. converting ColIndex into RowIndex.
36// All types should use 'Index' instead of int32.
37typedef int32 Index;
38
39// ColIndex is the type for integers representing column/variable indices.
40// int32s are enough for handling even the largest problems.
42
43// RowIndex is the type for integers representing row/constraint indices.
44// int32s are enough for handling even the largest problems.
46
47// Get the ColIndex corresponding to the column # row.
48inline ColIndex RowToColIndex(RowIndex row) { return ColIndex(row.value()); }
49
50// Get the RowIndex corresponding to the row # col.
51inline RowIndex ColToRowIndex(ColIndex col) { return RowIndex(col.value()); }
52
53// Get the integer index corresponding to the col.
54inline Index ColToIntIndex(ColIndex col) { return col.value(); }
55
56// Get the integer index corresponding to the row.
57inline Index RowToIntIndex(RowIndex row) { return row.value(); }
58
59// EntryIndex is the type for integers representing entry indices.
60// An entry in a sparse matrix is a pair (row, value) for a given known column.
61// See classes SparseColumn and SparseMatrix.
62#if defined(__ANDROID__)
63DEFINE_INT_TYPE(EntryIndex, int32);
64#else
66#endif
67
68static inline double ToDouble(double f) { return f; }
69
70static inline double ToDouble(long double f) { return static_cast<double>(f); }
71
72// The type Fractional denotes the type of numbers on which the computations are
73// performed. This is defined as double here, but it could as well be float,
74// DoubleDouble, QuadDouble, or infinite-precision rationals.
75// Floating-point representations are binary fractional numbers, thus the name.
76// (See http://en.wikipedia.org/wiki/Fraction_(mathematics) .)
77typedef double Fractional;
78
79// Range max for type Fractional. DBL_MAX for double for example.
81
82// Infinity for type Fractional.
83const double kInfinity = std::numeric_limits<double>::infinity();
84
85// Epsilon for type Fractional, i.e. the smallest e such that 1.0 + e != 1.0 .
86const double kEpsilon = std::numeric_limits<double>::epsilon();
87
88// Returns true if the given value is finite, that means for a double:
89// not a NaN and not +/- infinity.
91 return value > -kInfinity && value < kInfinity;
92}
93
94// Constants to represent invalid row or column index.
95// It is important that their values be the same because during transposition,
96// one needs to be converted into the other.
97const RowIndex kInvalidRow(-1);
98const ColIndex kInvalidCol(-1);
99
100// Different statuses for a given problem.
101enum class ProblemStatus : int8 {
102 // The problem has been solved to optimality. Both the primal and dual have
103 // a feasible solution.
104 OPTIMAL,
105
106 // The problem has been proven primal-infeasible. Note that the problem is not
107 // necessarily DUAL_UNBOUNDED (See Chvatal p.60). The solver does not have a
108 // dual unbounded ray in this case.
110
111 // The problem has been proven dual-infeasible. Note that the problem is not
112 // necessarily PRIMAL_UNBOUNDED (See Chvatal p.60). The solver does
113 // note have a primal unbounded ray in this case,
115
116 // The problem is either INFEASIBLE or UNBOUNDED (this applies to both the
117 // primal and dual algorithms). This status is only returned by the presolve
118 // step and means that a primal or dual unbounded ray was found during
119 // presolve. Note that because some presolve techniques assume that a feasible
120 // solution exists to simplify the problem further, it is difficult to
121 // distinguish between infeasibility and unboundedness.
122 //
123 // If a client needs to distinguish, it is possible to run the primal
124 // algorithm on the same problem with a 0 objective function to know if the
125 // problem was PRIMAL_INFEASIBLE.
127
128 // The problem has been proven feasible and unbounded. That means that the
129 // problem is DUAL_INFEASIBLE and that the solver has a primal unbounded ray.
131
132 // The problem has been proven dual-feasible and dual-unbounded. That means
133 // the problem is PRIMAL_INFEASIBLE and that the solver has a dual unbounded
134 // ray to prove it.
136
137 // All the statuses below correspond to a case where the solver was
138 // interrupted. This can happen because of a timeout, an iteration limit or an
139 // error.
140
141 // The solver didn't had a chance to prove anything.
142 INIT,
143
144 // The problem has been proven primal-feasible but may still be
145 // PRIMAL_UNBOUNDED.
147
148 // The problem has been proven dual-feasible, but may still be DUAL_UNBOUNDED.
149 // That means that if the primal is feasible, then it has a finite optimal
150 // solution.
152
153 // An error occurred during the solving process.
154 ABNORMAL,
155
156 // The input problem was invalid (see LinearProgram.IsValid()).
157 INVALID_PROBLEM,
158
159 // The problem was solved to a feasible status, but the solution checker found
160 // the primal and/or dual infeasibilities too important for the specified
161 // parameters.
162 IMPRECISE,
163};
164
165// Returns the string representation of the ProblemStatus enum.
166std::string GetProblemStatusString(ProblemStatus problem_status);
167
168inline std::ostream& operator<<(std::ostream& os, ProblemStatus status) {
169 os << GetProblemStatusString(status);
170 return os;
171}
172
173// Different types of variables.
174enum class VariableType : int8 {
180};
181
182// Returns the string representation of the VariableType enum.
183std::string GetVariableTypeString(VariableType variable_type);
184
185inline std::ostream& operator<<(std::ostream& os, VariableType type) {
186 os << GetVariableTypeString(type);
187 return os;
188}
189
190// Different variables statuses.
191// If a solution is OPTIMAL or FEASIBLE, then all the properties described here
192// should be satisfied. These properties should also be true during the
193// execution of the revised simplex algorithm, except that because of
194// bound-shifting, the variable may not be at their exact bounds until the
195// shifts are removed.
196enum class VariableStatus : int8 {
197 // The basic status is special and takes precedence over all the other
198 // statuses. It means that the variable is part of the basis.
199 BASIC,
200 // Only possible status of a FIXED_VARIABLE not in the basis. The variable
201 // value should be exactly equal to its bounds (which are the same).
203 // Only possible statuses of a non-basic variable which is not UNCONSTRAINED
204 // or FIXED. The variable value should be at its exact specified bound (which
205 // must be finite).
208 // Only possible status of an UNCONSTRAINED non-basic variable.
209 // Its value should be zero.
210 FREE,
211};
212
213// Returns the string representation of the VariableStatus enum.
214std::string GetVariableStatusString(VariableStatus status);
215
216inline std::ostream& operator<<(std::ostream& os, VariableStatus status) {
217 os << GetVariableStatusString(status);
218 return os;
219}
220
221// Different constraints statuses.
222// The meaning is the same for the constraint activity relative to its bounds as
223// it is for a variable value relative to its bounds. Actually, this is the
224// VariableStatus of the slack variable associated to a constraint modulo a
225// change of sign. The difference is that because of precision error, a
226// constraint activity cannot exactly be equal to one of its bounds or to zero.
227enum class ConstraintStatus : int8 {
228 BASIC,
232 FREE,
233};
234
235// Returns the string representation of the ConstraintStatus enum.
237
238inline std::ostream& operator<<(std::ostream& os, ConstraintStatus status) {
239 os << GetConstraintStatusString(status);
240 return os;
241}
242
243// Returns the ConstraintStatus corresponding to a given VariableStatus.
245
246// Wrapper around an ITIVector to allow (and enforce) creation/resize/assign
247// to use the index type for the size.
248//
249// TODO(user): This should probably move into ITIVector, but note that this
250// version is more strict and does not allow any other size types.
251template <typename IntType, typename T>
252class StrictITIVector : public absl::StrongVector<IntType, T> {
253 public:
254 typedef IntType IndexType;
256// This allows for brace initialization, which is really useful in tests.
257// It is not 'explicit' by design, so one can do vector = {...};
258#if !defined(__ANDROID__) && (!defined(_MSC_VER) || (_MSC_VER >= 1800))
259 StrictITIVector(std::initializer_list<T> init_list) // NOLINT
260 : ParentType(init_list.begin(), init_list.end()) {}
261#endif
263 explicit StrictITIVector(IntType size) : ParentType(size.value()) {}
264 StrictITIVector(IntType size, const T& v) : ParentType(size.value(), v) {}
265 template <typename InputIteratorType>
266 StrictITIVector(InputIteratorType first, InputIteratorType last)
267 : ParentType(first, last) {}
268
269 void resize(IntType size) { ParentType::resize(size.value()); }
270 void resize(IntType size, const T& v) { ParentType::resize(size.value(), v); }
271
272 void reserve(IntType size) { ParentType::reserve(size.value()); }
273
274 void assign(IntType size, const T& v) { ParentType::assign(size.value(), v); }
275
276 IntType size() const { return IntType(ParentType::size()); }
277
278 IntType capacity() const { return IntType(ParentType::capacity()); }
279
280 // Since calls to resize() must use a default value, we introduce a new
281 // function for convenience to reduce the size of a vector.
282 void resize_down(IntType size) {
283 DCHECK_GE(size, IntType(0));
284 DCHECK_LE(size, IntType(ParentType::size()));
285 ParentType::resize(size.value());
286 }
287
288 // This function can be up to 4 times faster than calling assign(size, 0).
289 // Note that it only works with StrictITIVector of basic types.
290 void AssignToZero(IntType size) {
291 resize(size, 0);
292 memset(ParentType::data(), 0, size.value() * sizeof(T));
293 }
294};
295
296// Row-vector types. Row-vector types are indexed by a column index.
297
298// Row of fractional values.
300
301// Row of booleans.
303
304// Row of column indices. Used to represent mappings between columns.
306
307// Vector of row or column indices. Useful to list the non-zero positions.
308typedef std::vector<ColIndex> ColIndexVector;
309typedef std::vector<RowIndex> RowIndexVector;
310
311// Row of row indices.
312// Useful for knowing which row corresponds to a particular column in the basis,
313// or for storing the number of rows for a given column.
315
316// Row of variable types.
318
319// Row of variable statuses.
321
322// Row of bits.
324
325// Column-vector types. Column-vector types are indexed by a row index.
326
327// Column of fractional values.
329
330// Column of booleans.
332
333// Column of bits.
335
336// Column of row indices. Used to represent mappings between rows.
338
339// Column of column indices.
340// Used to represent which column corresponds to a particular row in the basis,
341// or for storing the number of columns for a given row.
343
344// Column of constraints (slack variables) statuses.
346
347// --------------------------------------------------------
348// VectorIterator
349// --------------------------------------------------------
350
351// An iterator over the elements of a sparse data structure that stores the
352// elements in arrays for indices and coefficients. The iterator is
353// built as a wrapper over a sparse vector entry class; the concrete entry class
354// is provided through the template argument EntryType.
355template <typename EntryType>
356class VectorIterator : EntryType {
357 public:
358 using Index = typename EntryType::Index;
359 using Entry = EntryType;
360
362 EntryIndex i)
363 : EntryType(indices, coefficients, i) {}
364
365 void operator++() { ++this->i_; }
366 bool operator!=(const VectorIterator& other) const {
367 // This operator is intended for use in natural range iteration ONLY.
368 // Therefore, we prefer to use '<' so that a buggy range iteration which
369 // start point is *after* its end point stops immediately, instead of
370 // iterating 2^(number of bits of EntryIndex) times.
371 return this->i_ < other.i_;
372 }
373 const Entry& operator*() const { return *this; }
374};
375
376// This is used during the deterministic time computation to convert a given
377// number of floating-point operations to something in the same order of
378// magnitude as a second (on a 2014 desktop).
380 const double kConversionFactor = 2e-9;
381 return kConversionFactor * static_cast<double>(n);
382}
383
384} // namespace glop
385} // namespace operations_research
386
387#endif // OR_TOOLS_LP_DATA_LP_TYPES_H_
int64 max
Definition: alldiff_cst.cc:139
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
void assign(size_type n, const value_type &val)
void resize(size_type new_size)
void reserve(size_type n)
size_type size() const
size_type capacity() const
std::vector< T, Alloc > ParentType
Definition: strong_vector.h:79
StrictITIVector(InputIteratorType first, InputIteratorType last)
Definition: lp_types.h:266
StrictITIVector(std::initializer_list< T > init_list)
Definition: lp_types.h:259
void resize(IntType size, const T &v)
Definition: lp_types.h:270
StrictITIVector(IntType size, const T &v)
Definition: lp_types.h:264
void assign(IntType size, const T &v)
Definition: lp_types.h:274
absl::StrongVector< IntType, T > ParentType
Definition: lp_types.h:255
typename EntryType::Index Index
Definition: lp_types.h:358
bool operator!=(const VectorIterator &other) const
Definition: lp_types.h:366
VectorIterator(const Index *indices, const Fractional *coefficients, EntryIndex i)
Definition: lp_types.h:361
int64 value
signed char int8
int int32
int64_t int64
ColIndex col
Definition: markowitz.cc:176
RowIndex row
Definition: markowitz.cc:175
RowIndex ColToRowIndex(ColIndex col)
Definition: lp_types.h:51
Bitset64< RowIndex > DenseBitColumn
Definition: lp_types.h:334
bool IsFinite(Fractional value)
Definition: lp_types.h:90
std::vector< ColIndex > ColIndexVector
Definition: lp_types.h:308
static double DeterministicTimeForFpOperations(int64 n)
Definition: lp_types.h:379
StrictITIVector< ColIndex, VariableType > VariableTypeRow
Definition: lp_types.h:317
const ColIndex kInvalidCol(-1)
StrictITIVector< ColIndex, Fractional > DenseRow
Definition: lp_types.h:299
std::string GetProblemStatusString(ProblemStatus problem_status)
Definition: lp_types.cc:19
std::string GetConstraintStatusString(ConstraintStatus status)
Definition: lp_types.cc:90
const double kRangeMax
Definition: lp_types.h:80
StrictITIVector< ColIndex, VariableStatus > VariableStatusRow
Definition: lp_types.h:320
Index RowToIntIndex(RowIndex row)
Definition: lp_types.h:57
static double ToDouble(double f)
Definition: lp_types.h:68
std::ostream & operator<<(std::ostream &os, ProblemStatus status)
Definition: lp_types.h:168
StrictITIVector< RowIndex, RowIndex > RowMapping
Definition: lp_types.h:337
StrictITIVector< RowIndex, ConstraintStatus > ConstraintStatusColumn
Definition: lp_types.h:345
Index ColToIntIndex(ColIndex col)
Definition: lp_types.h:54
ColIndex RowToColIndex(RowIndex row)
Definition: lp_types.h:48
Bitset64< ColIndex > DenseBitRow
Definition: lp_types.h:323
ConstraintStatus VariableToConstraintStatus(VariableStatus status)
Definition: lp_types.cc:109
const RowIndex kInvalidRow(-1)
std::vector< RowIndex > RowIndexVector
Definition: lp_types.h:309
StrictITIVector< ColIndex, bool > DenseBooleanRow
Definition: lp_types.h:302
const double kEpsilon
Definition: lp_types.h:86
StrictITIVector< ColIndex, RowIndex > ColToRowMapping
Definition: lp_types.h:314
StrictITIVector< RowIndex, ColIndex > RowToColMapping
Definition: lp_types.h:342
std::string GetVariableTypeString(VariableType variable_type)
Definition: lp_types.cc:52
StrictITIVector< RowIndex, Fractional > DenseColumn
Definition: lp_types.h:328
DEFINE_INT_TYPE(ColIndex, Index)
StrictITIVector< RowIndex, bool > DenseBooleanColumn
Definition: lp_types.h:331
std::string GetVariableStatusString(VariableStatus status)
Definition: lp_types.cc:71
const double kInfinity
Definition: lp_types.h:83
StrictITIVector< ColIndex, ColIndex > ColMapping
Definition: lp_types.h:305
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::vector< double > coefficients