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 
23 #include "ortools/base/int_type.h"
24 #include "ortools/base/logging.h"
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 
31 namespace operations_research {
32 namespace 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.
37 typedef 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.
48 inline ColIndex RowToColIndex(RowIndex row) { return ColIndex(row.value()); }
49 
50 // Get the RowIndex corresponding to the row # col.
51 inline RowIndex ColToRowIndex(ColIndex col) { return RowIndex(col.value()); }
52 
53 // Get the integer index corresponding to the col.
54 inline Index ColToIntIndex(ColIndex col) { return col.value(); }
55 
56 // Get the integer index corresponding to the row.
57 inline 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__)
63 DEFINE_INT_TYPE(EntryIndex, int32);
64 #else
65 DEFINE_INT_TYPE(EntryIndex, int64);
66 #endif
67 
68 static inline double ToDouble(double f) { return f; }
69 
70 static 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) .)
77 typedef double Fractional;
78 
79 // Range max for type Fractional. DBL_MAX for double for example.
81 
82 // Infinity for type Fractional.
83 const 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 .
86 const 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.
90 inline bool IsFinite(Fractional value) {
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.
97 const RowIndex kInvalidRow(-1);
98 const ColIndex kInvalidCol(-1);
99 
100 // Different statuses for a given problem.
101 enum 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()).
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.
166 std::string GetProblemStatusString(ProblemStatus problem_status);
167 
168 inline std::ostream& operator<<(std::ostream& os, ProblemStatus status) {
169  os << GetProblemStatusString(status);
170  return os;
171 }
172 
173 // Different types of variables.
174 enum class VariableType : int8 {
180 };
181 
182 // Returns the string representation of the VariableType enum.
183 std::string GetVariableTypeString(VariableType variable_type);
184 
185 inline 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.
196 enum 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).
202  FIXED_VALUE,
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.
214 std::string GetVariableStatusString(VariableStatus status);
215 
216 inline 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.
227 enum class ConstraintStatus : int8 {
228  BASIC,
229  FIXED_VALUE,
232  FREE,
233 };
234 
235 // Returns the string representation of the ConstraintStatus enum.
236 std::string GetConstraintStatusString(ConstraintStatus status);
237 
238 inline 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.
251 template <typename IntType, typename T>
252 class 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.
308 typedef std::vector<ColIndex> ColIndexVector;
309 typedef 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.
355 template <typename EntryType>
356 class VectorIterator : EntryType {
357  public:
358  using Index = typename EntryType::Index;
359  using Entry = EntryType;
360 
361  VectorIterator(const Index* indices, const Fractional* coefficients,
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).
379 static inline double DeterministicTimeForFpOperations(int64 n) {
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
Bitset64< RowIndex > DenseBitColumn
Definition: lp_types.h:334
static double DeterministicTimeForFpOperations(int64 n)
Definition: lp_types.h:379
std::vector< ColIndex > ColIndexVector
Definition: lp_types.h:308
const RowIndex kInvalidRow(-1)
StrictITIVector< ColIndex, VariableType > VariableTypeRow
Definition: lp_types.h:317
StrictITIVector< ColIndex, Fractional > DenseRow
Definition: lp_types.h:299
std::string GetProblemStatusString(ProblemStatus problem_status)
Definition: lp_types.cc:19
DEFINE_INT_TYPE(ColIndex, Index)
Index ColToIntIndex(ColIndex col)
Definition: lp_types.h:54
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
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
ColIndex RowToColIndex(RowIndex row)
Definition: lp_types.h:48
bool IsFinite(Fractional value)
Definition: lp_types.h:90
Bitset64< ColIndex > DenseBitRow
Definition: lp_types.h:323
RowIndex ColToRowIndex(ColIndex col)
Definition: lp_types.h:51
ConstraintStatus VariableToConstraintStatus(VariableStatus status)
Definition: lp_types.cc:109
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
StrictITIVector< RowIndex, bool > DenseBooleanColumn
Definition: lp_types.h:331
std::string GetVariableStatusString(VariableStatus status)
Definition: lp_types.cc:71
Index RowToIntIndex(RowIndex row)
Definition: lp_types.h:57
const double kInfinity
Definition: lp_types.h:83
StrictITIVector< ColIndex, ColIndex > ColMapping
Definition: lp_types.h:305
const ColIndex kInvalidCol(-1)
static double ToDouble(double f)
Definition: lp_types.h:68
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::vector< double > coefficients