Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
lp_types.h
Go to the documentation of this file.
1// Copyright 2010-2025 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 <cstddef>
20#include <cstdint>
21#include <initializer_list>
22#include <limits>
23#include <memory>
24#include <ostream>
25#include <string>
26#include <vector>
27
28#include "absl/log/check.h"
31#include "ortools/util/bitset.h"
33
34// We use typedefs as much as possible to later permit the usage of
35// types such as quad-doubles or rationals.
36
37namespace operations_research {
38namespace glop {
39
40// This type is defined to avoid cast issues during index conversions,
41// e.g. converting ColIndex into RowIndex.
42// All types should use 'Index' instead of int32_t.
43typedef int32_t Index;
44
45// ColIndex is the type for integers representing column/variable indices.
46// int32s are enough for handling even the largest problems.
48
49// RowIndex is the type for integers representing row/constraint indices.
50// int32s are enough for handling even the largest problems.
52
53// Get the ColIndex corresponding to the column # row.
54inline ColIndex RowToColIndex(RowIndex row) { return ColIndex(row.value()); }
55
56// Get the RowIndex corresponding to the row # col.
57inline RowIndex ColToRowIndex(ColIndex col) { return RowIndex(col.value()); }
58
59// Get the integer index corresponding to the col.
60inline Index ColToIntIndex(ColIndex col) { return col.value(); }
61
62// Get the integer index corresponding to the row.
63inline Index RowToIntIndex(RowIndex row) { return row.value(); }
64
65// EntryIndex is the type for integers representing entry indices.
66// An entry in a sparse matrix is a pair (row, value) for a given known column.
67// See classes SparseColumn and SparseMatrix.
68#if defined(__ANDROID__)
69DEFINE_STRONG_INDEX_TYPE(EntryIndex);
70#else
72#endif
73
74static inline double ToDouble(double f) { return f; }
75
76// The type Fractional denotes the type of numbers on which the computations are
77// performed. This is defined as double here, but it could as well be float,
78// DoubleDouble, QuadDouble, or infinite-precision rationals.
79// Floating-point representations are binary fractional numbers, thus the name.
80// (See http://en.wikipedia.org/wiki/Fraction_(mathematics) .)
81typedef double Fractional;
82
83// Range max for type Fractional. DBL_MAX for double for example.
84constexpr double kRangeMax = std::numeric_limits<double>::max();
85
86// Infinity for type Fractional.
87constexpr double kInfinity = std::numeric_limits<double>::infinity();
88
89// Epsilon for type Fractional, i.e. the smallest e such that 1.0 + e != 1.0 .
90constexpr double kEpsilon = std::numeric_limits<double>::epsilon();
91
92// Returns true if the given value is finite, that means for a double:
93// not a NaN and not +/- infinity.
94inline bool IsFinite(Fractional value) {
95 return value > -kInfinity && value < kInfinity;
96}
97
98// Constants to represent invalid row or column index.
99// It is important that their values be the same because during transposition,
100// one needs to be converted into the other.
101constexpr RowIndex kInvalidRow(-1);
102constexpr ColIndex kInvalidCol(-1);
103
104// Different statuses for a given problem.
105enum class ProblemStatus : int8_t {
106 // The problem has been solved to optimality. Both the primal and dual have
107 // a feasible solution.
109
110 // The problem has been proven primal-infeasible. Note that the problem is not
111 // necessarily DUAL_UNBOUNDED (See Chvatal p.60). The solver does not have a
112 // dual unbounded ray in this case.
114
115 // The problem has been proven dual-infeasible. Note that the problem is not
116 // necessarily PRIMAL_UNBOUNDED (See Chvatal p.60). The solver does
117 // note have a primal unbounded ray in this case,
119
120 // The problem is either INFEASIBLE or UNBOUNDED (this applies to both the
121 // primal and dual algorithms). This status is only returned by the presolve
122 // step and means that a primal or dual unbounded ray was found during
123 // presolve. Note that because some presolve techniques assume that a feasible
124 // solution exists to simplify the problem further, it is difficult to
125 // distinguish between infeasibility and unboundedness.
126 //
127 // If a client needs to distinguish, it is possible to run the primal
128 // algorithm on the same problem with a 0 objective function to know if the
129 // problem was PRIMAL_INFEASIBLE.
131
132 // The problem has been proven feasible and unbounded. That means that the
133 // problem is DUAL_INFEASIBLE and that the solver has a primal unbounded ray.
135
136 // The problem has been proven dual-feasible and dual-unbounded. That means
137 // the problem is PRIMAL_INFEASIBLE and that the solver has a dual unbounded
138 // ray to prove it.
140
141 // All the statuses below correspond to a case where the solver was
142 // interrupted. This can happen because of a timeout, an iteration limit or an
143 // error.
144
145 // The solver didn't had a chance to prove anything.
147
148 // The problem has been proven primal-feasible but may still be
149 // PRIMAL_UNBOUNDED.
151
152 // The problem has been proven dual-feasible, but may still be DUAL_UNBOUNDED.
153 // That means that if the primal is feasible, then it has a finite optimal
154 // solution.
156
157 // An error occurred during the solving process.
159
160 // The input problem was invalid (see LinearProgram.IsValid()).
162
163 // The problem was solved to a feasible status, but the solution checker found
164 // the primal and/or dual infeasibilities too important for the specified
165 // parameters.
167};
168
169// Returns the string representation of the ProblemStatus enum.
170std::string GetProblemStatusString(ProblemStatus problem_status);
171
172inline std::ostream& operator<<(std::ostream& os, ProblemStatus status) {
173 os << GetProblemStatusString(status);
174 return os;
175}
176
177// Different types of variables.
185
186// Returns the string representation of the VariableType enum.
187std::string GetVariableTypeString(VariableType variable_type);
188
189inline std::ostream& operator<<(std::ostream& os, VariableType type) {
190 os << GetVariableTypeString(type);
191 return os;
192}
193
194// Different variables statuses.
195// If a solution is OPTIMAL or FEASIBLE, then all the properties described here
196// should be satisfied. These properties should also be true during the
197// execution of the revised simplex algorithm, except that because of
198// bound-shifting, the variable may not be at their exact bounds until the
199// shifts are removed.
200enum class VariableStatus : int8_t {
201 // The basic status is special and takes precedence over all the other
202 // statuses. It means that the variable is part of the basis.
204 // Only possible status of a FIXED_VARIABLE not in the basis. The variable
205 // value should be exactly equal to its bounds (which are the same).
207 // Only possible statuses of a non-basic variable which is not UNCONSTRAINED
208 // or FIXED. The variable value should be at its exact specified bound (which
209 // must be finite).
212 // Only possible status of an UNCONSTRAINED non-basic variable.
213 // Its value should be zero.
214 //
215 // Note that during crossover, this status is relaxed, and any variable that
216 // can currently move in both directions can be marked as free.
218};
219
220// Returns the string representation of the VariableStatus enum.
221std::string GetVariableStatusString(VariableStatus status);
222
223inline std::ostream& operator<<(std::ostream& os, VariableStatus status) {
224 os << GetVariableStatusString(status);
225 return os;
226}
227
228// Different constraints statuses.
229// The meaning is the same for the constraint activity relative to its bounds as
230// it is for a variable value relative to its bounds. Actually, this is the
231// VariableStatus of the slack variable associated to a constraint modulo a
232// change of sign. The difference is that because of precision error, a
233// constraint activity cannot exactly be equal to one of its bounds or to zero.
241
242// Returns the string representation of the ConstraintStatus enum.
244
245inline std::ostream& operator<<(std::ostream& os, ConstraintStatus status) {
246 os << GetConstraintStatusString(status);
247 return os;
248}
249
250// Returns the ConstraintStatus corresponding to a given VariableStatus.
252
253// A span of `T`, indexed by a strict int type `IntType`. Intended to be passed
254// by value. See b/259677543.
255template <typename IntType, typename T>
257 public:
258 using IndexType = IntType;
259 using reference = T&;
260 using value_type = T;
261
262 StrictITISpan(T* data, IntType size) : data_(data), size_(size) {}
263
264 reference operator[](IntType i) const {
265 return data_[static_cast<size_t>(i.value())];
266 }
267
268 IntType size() const { return size_; }
269
270 // TODO(user): This should probably be a strictly typed iterator too, but
271 // `StrongVector::begin()` already suffers from this problem.
272 auto begin() const { return data_; }
273 auto end() const { return data_ + static_cast<size_t>(size_.value()); }
274
275 private:
276 T* const data_;
277 const IntType size_;
278};
279
280// Wrapper around a StrongVector to allow (and enforce) creation/resize/assign
281// to use the index type for the size.
282//
283// TODO(user): This should probably move to StrongVector, but note that this
284// version is stricter and does not allow any other size types.
285template <typename IntType, typename T, typename Alloc = std::allocator<T>>
286class StrictITIVector : public util_intops::StrongVector<IntType, T, Alloc> {
287 public:
288 using IndexType = IntType;
292
293 StrictITIVector() = default;
294 explicit StrictITIVector(IntType size) : ParentType(size) {}
295 explicit StrictITIVector(const Alloc& a) : ParentType(a) {}
296 StrictITIVector(IntType n, const T& v, const Alloc& a = Alloc())
297 : ParentType(n, v, a) {}
298
299 // This allows for brace initialization, which is really useful in tests.
300 // It is not 'explicit' by design, so one can do vector = {...};
301#if !defined(__ANDROID__) && (!defined(_MSC_VER) || (_MSC_VER >= 1800))
302 StrictITIVector(std::initializer_list<T> init_list,
303 const Alloc& a = Alloc()) // NOLINT
304 : ParentType(init_list.begin(), init_list.end(), a) {}
305#endif
306
307 template <typename InputIteratorType>
308 StrictITIVector(InputIteratorType first, InputIteratorType last,
309 const Alloc& a = Alloc())
310 : ParentType(first, last, a) {}
311
312 void resize(IntType size) { ParentType::resize(size.value()); }
313 void resize(IntType size, const T& v) { ParentType::resize(size.value(), v); }
314
315 void reserve(IntType size) { ParentType::reserve(size.value()); }
316
317 void assign(IntType size, const T& v) { ParentType::assign(size.value(), v); }
318
319 IntType size() const { return IntType(ParentType::size()); }
320
321 IntType capacity() const { return IntType(ParentType::capacity()); }
322
323 View view() { return View(ParentType::data(), size()); }
325 ConstView view() const { return const_view(); }
326
328 ParentType::assign(data.begin(), data.end());
329 return *this;
330 }
331
332 // Since calls to resize() must use a default value, we introduce a new
333 // function for convenience to reduce the size of a vector.
334 void resize_down(IntType size) {
335 DCHECK_GE(size, IntType(0));
336 DCHECK_LE(size, IntType(ParentType::size()));
337 ParentType::resize(size.value());
338 }
339
340 // This function can be up to 4 times faster than calling assign(size, 0).
341 // Note that it only works with StrictITIVector of basic types.
342 void AssignToZero(IntType size) {
343 resize(size, 0);
344 memset(ParentType::data(), 0, size.value() * sizeof(T));
345 }
346};
347
348// Row-vector types. Row-vector types are indexed by a column index.
349
350// Row of fractional values.
352
353// Row of booleans.
355
356// Row of column indices. Used to represent mappings between columns.
358
359// Vector of row or column indices. Useful to list the non-zero positions.
360typedef std::vector<ColIndex> ColIndexVector;
361typedef std::vector<RowIndex> RowIndexVector;
362
363// Row of row indices.
364// Useful for knowing which row corresponds to a particular column in the basis,
365// or for storing the number of rows for a given column.
367
368// Row of variable types.
370
371// Row of variable statuses.
373
374// Row of bits.
376
377// Column-vector types. Column-vector types are indexed by a row index.
378
379// Column of fractional values.
381
382// Column of booleans.
384
385// Column of bits.
387
388// Column of row indices. Used to represent mappings between rows.
390
391// Column of column indices.
392// Used to represent which column corresponds to a particular row in the basis,
393// or for storing the number of columns for a given row.
395
396// Column of constraints (slack variables) statuses.
398
399// --------------------------------------------------------
400// VectorIterator
401// --------------------------------------------------------
402
403// An iterator over the elements of a sparse data structure that stores the
404// elements in arrays for indices and coefficients. The iterator is
405// built as a wrapper over a sparse vector entry class; the concrete entry class
406// is provided through the template argument EntryType.
407template <typename EntryType>
408class VectorIterator : EntryType {
409 public:
410 using Index = typename EntryType::Index;
411 using Entry = EntryType;
413 VectorIterator(const Index* indices, const Fractional* coefficients,
414 EntryIndex i)
415 : EntryType(indices, coefficients, i) {}
416
417 void operator++() { ++this->i_; }
418 bool operator!=(const VectorIterator& other) const {
419 // This operator is intended for use in natural range iteration ONLY.
420 // Therefore, we prefer to use '<' so that a buggy range iteration which
421 // start point is *after* its end point stops immediately, instead of
422 // iterating 2^(number of bits of EntryIndex) times.
423 return this->i_ < other.i_;
424 }
425 const Entry& operator*() const { return *this; }
426};
428// This is used during the deterministic time computation to convert a given
429// number of floating-point operations to something in the same order of
430// magnitude as a second (on a 2014 desktop).
431static inline double DeterministicTimeForFpOperations(int64_t n) {
432 const double kConversionFactor = 2e-9;
433 return kConversionFactor * static_cast<double>(n);
434}
435
436} // namespace glop
437} // namespace operations_research
438
439#endif // OR_TOOLS_LP_DATA_LP_TYPES_H_
StrictITISpan(T *data, IntType size)
Definition lp_types.h:262
reference operator[](IntType i) const
Definition lp_types.h:264
StrictITIVector(std::initializer_list< T > init_list, const Alloc &a=Alloc())
Definition lp_types.h:302
void assign(IntType size, const T &v)
Definition lp_types.h:317
util_intops::StrongVector< IndexType, ValueType, std::allocator< ValueType > > ParentType
Definition lp_types.h:289
StrictITIVector & operator=(ConstView data)
Definition lp_types.h:327
void resize(IntType size, const T &v)
Definition lp_types.h:313
StrictITISpan< IndexType, const ValueType > ConstView
Definition lp_types.h:291
StrictITIVector(InputIteratorType first, InputIteratorType last, const Alloc &a=Alloc())
Definition lp_types.h:308
StrictITIVector(IntType n, const T &v, const Alloc &a=Alloc())
Definition lp_types.h:296
bool operator!=(const VectorIterator &other) const
Definition lp_types.h:420
VectorIterator(const Index *indices, const Fractional *coefficients, EntryIndex i)
Definition lp_types.h:415
typename EntryType::Index Index
Definition lp_types.h:412
void assign(size_type n, const value_type &val)
value_type * data()
– Pass-through methods to STL vector ----------------------------------—
constexpr ColIndex kInvalidCol(-1)
constexpr double kInfinity
Infinity for type Fractional.
Definition lp_types.h:87
std::string GetVariableTypeString(VariableType variable_type)
Returns the string representation of the VariableType enum.
Definition lp_types.cc:56
StrictITIVector< RowIndex, ColIndex > RowToColMapping
Definition lp_types.h:394
std::vector< RowIndex > RowIndexVector
Definition lp_types.h:361
StrictITIVector< ColIndex, RowIndex > ColToRowMapping
Definition lp_types.h:366
StrictITIVector< RowIndex, bool > DenseBooleanColumn
Column of booleans.
Definition lp_types.h:383
std::vector< ColIndex > ColIndexVector
Vector of row or column indices. Useful to list the non-zero positions.
Definition lp_types.h:360
StrictITIVector< ColIndex, ColIndex > ColMapping
Row of column indices. Used to represent mappings between columns.
Definition lp_types.h:357
StrictITIVector< RowIndex, ConstraintStatus > ConstraintStatusColumn
Column of constraints (slack variables) statuses.
Definition lp_types.h:397
Bitset64< ColIndex > DenseBitRow
Row of bits.
Definition lp_types.h:375
std::string GetVariableStatusString(VariableStatus status)
Returns the string representation of the VariableStatus enum.
Definition lp_types.cc:75
Index ColToIntIndex(ColIndex col)
Get the integer index corresponding to the col.
Definition lp_types.h:60
Bitset64< RowIndex > DenseBitColumn
Column of bits.
Definition lp_types.h:386
constexpr double kRangeMax
Range max for type Fractional. DBL_MAX for double for example.
Definition lp_types.h:84
ColIndex RowToColIndex(RowIndex row)
Get the ColIndex corresponding to the column # row.
Definition lp_types.h:54
bool IsFinite(Fractional value)
Definition lp_types.h:94
constexpr RowIndex kInvalidRow(-1)
StrictITIVector< RowIndex, RowIndex > RowMapping
Column of row indices. Used to represent mappings between rows.
Definition lp_types.h:389
VariableType
Different types of variables.
Definition lp_types.h:178
StrictITIVector< ColIndex, VariableType > VariableTypeRow
Row of variable types.
Definition lp_types.h:369
RowIndex ColToRowIndex(ColIndex col)
Get the RowIndex corresponding to the row # col.
Definition lp_types.h:57
std::string GetConstraintStatusString(ConstraintStatus status)
Returns the string representation of the ConstraintStatus enum.
Definition lp_types.cc:94
StrictITIVector< ColIndex, VariableStatus > VariableStatusRow
Row of variable statuses.
Definition lp_types.h:372
constexpr double kEpsilon
Epsilon for type Fractional, i.e. the smallest e such that 1.0 + e != 1.0 .
Definition lp_types.h:90
StrictITIVector< RowIndex, Fractional > DenseColumn
Column-vector types. Column-vector types are indexed by a row index.
Definition lp_types.h:380
StrictITIVector< ColIndex, Fractional > DenseRow
Row-vector types. Row-vector types are indexed by a column index.
Definition lp_types.h:351
StrictITIVector< ColIndex, bool > DenseBooleanRow
Row of booleans.
Definition lp_types.h:354
std::ostream & operator<<(std::ostream &os, ProblemStatus status)
Definition lp_types.h:172
ProblemStatus
Different statuses for a given problem.
Definition lp_types.h:105
@ ABNORMAL
An error occurred during the solving process.
Definition lp_types.h:158
@ INVALID_PROBLEM
The input problem was invalid (see LinearProgram.IsValid()).
Definition lp_types.h:161
@ INIT
The solver didn't had a chance to prove anything.
Definition lp_types.h:146
ConstraintStatus VariableToConstraintStatus(VariableStatus status)
Returns the ConstraintStatus corresponding to a given VariableStatus.
Definition lp_types.cc:113
static double DeterministicTimeForFpOperations(int64_t n)
Definition lp_types.h:433
std::string GetProblemStatusString(ProblemStatus problem_status)
Returns the string representation of the ProblemStatus enum.
Definition lp_types.cc:23
Index RowToIntIndex(RowIndex row)
Get the integer index corresponding to the row.
Definition lp_types.h:63
static double ToDouble(double f)
Definition lp_types.h:74
In SWIG mode, we don't want anything besides these top-level includes.
#define DEFINE_STRONG_INT64_TYPE(integer_type_name)
#define DEFINE_STRONG_INDEX_TYPE(index_type_name)