1 // Copyright 2010-2021 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 // An index based C++ API for building optimization problems.
15 //
16 // TODO(b/188550843): move/rename to core/model_storage.h
17 //
18 // Models problems of the form:
19 // min sum_{j in J} c_j * x_j + d
20 // s.t. lb^c_i <= sum_{j in J} A_ij * x_j <= ub^c_i for all i in I,
21 // lb^v_j <= x_j <= ub^v_j for all j in J,
22 // x_j integer for all j in Z,
23 // where above:
24 // * I: the set of linear constraints,
25 // * J: the set of variables,
26 // * Z: a subset of J, the integer variables,
27 // * x: the decision variables (indexed by J),
28 // * c: the linear objective, one double per variable,
29 // * d: the objective offset, a double scalar,
30 // * lb^c: the constraint lower bounds, one double per linear constraint,
31 // * ub^c: the constraint upper bounds, one double per linear constraint,
32 // * lb^v: the variable lower bounds, one double per variable,
33 // * ub^v: the variable upper bounds, one double per variable,
34 // * A: the linear constraint matrix, a double per variable/constraint pair.
35 //
36 // The min in the objective can also be changed to a max.
37 //
38 // A simple example:
39 //
40 // Model the problem:
41 // max 2.0 * x + y
42 // s.t. x + y <= 1.5
43 // x in {0.0, 1.0}
44 // 0 <= y <= 2.5
45 //
46 // using ::operations_research::math_opt::IndexedModel;
47 // using ::operations_research::math_opt::VariableId;
48 // using ::operations_research::math_opt::LinearConstraintId;
49 // using ::operations_research::math_opt::ModelProto;
50 // using ::operations_research::math_opt::ModelProtoUpdate;
51 //
52 // IndexedModel model("my_model");
53 // const VariableId x = model.AddVariable(0.0, 1.0, true, "x");
54 // const VariableId y = model.AddVariable(0.0, 2.5, false, "y");
55 // const LinearConstraintId c = model.AddLinearConstraint(
56 // -std::numeric_limits<double>::infinity, 1.5, "c");
57 // model.set_linear_constraint_coefficient(x, c, 1.0);
58 // model.set_linear_constraint_coefficient(y, c, 1.0);
59 // model.set_linear_objective_coefficient(x, 2.0);
60 // model.set_linear_objective_coefficient(y, 1.0);
61 // model.set_maximize();
62 //
63 // Now, export to a proto describing the model:
64 //
65 // const ModelProto model_proto = model.ExportModel();
66 //
67 // Modify the problem and get a model update proto:
68 //
69 // const std::unique_ptr<IndexedModel::UpdateTracker> update_tracker =
70 // model.NewUpdateTracker();
71 // c.set_upper_bound(2.0);
72 // const absl::optional<ModelUpdateProto> update_proto =
73 // update_tracker->ExportModelUpdate();
74 // update_tracker->Checkpoint();
75 //
76 // Reading and writing model properties:
77 //
78 // Properties of the model (e.g. variable/constraint bounds) can be written
79 // and read in amortized O(1) time. Deleting a variable will take time
80 // O(#constraints containing the variable), and likewise deleting a constraint
81 // will take time O(#variables in the constraint). The constraint matrix is
82 // stored as hash map where the key is a {LinearConstraintId, VariableId}
83 // pair and the value is the coefficient. The nonzeros of the matrix are
84 // additionally stored by row and by column, but these indices generated lazily
85 // upon first use. Asking for the set of variables in a constraint, the
86 // constraints in a variable, deleting a variable or constraint, or requesting a
87 // ModelUpdate proto will all trigger these additional indices to be generated.
88 //
89 // Exporting the Model proto:
90 //
91 // The Model proto is an equivalent representation to IndexedModel. It has a
92 // smaller memory footprint and optimized for storage/transport, rather than
93 // efficient modification. It is also the format consumed by solvers in this
94 // library. The Model proto can be generated by calling
95 // IndexedModel::ExportModel().
96 //
97 // Incrementalism, the ModelUpdate proto, and Checkpoints:
98 //
99 // To update an existing model as specified by a Model proto, solvers consume a
100 // ModelUpdate proto, which describes the changes to a model (e.g. new variables
101 // or a change in a variable bound). IndexedModel::UpdateTracker tracks the
102 // changes made and produces a ModelUpdate proto describing these changes with
103 // the method UpdateTracker::ExportModelUpdate(). The changes returned will be
104 // the modifications since the previous call to
105 // UpdateTracker::Checkpoint(). Note that, for newly initialized models, before
106 // the first checkpoint, there is no additional memory overhead from tracking
107 // changes. See
108 // g3doc/ortools/math_opt/g3doc/model_building_complexity.md
109 // for details.
110 //
111 // On bad input:
112 //
113 // Using a bad variable id or constraint id (an id not in the current model,
114 // which includes ids that have been deleted) on any method will result in an
115 // immediate failure (either a CHECK failure or an exception, which is an
116 // implementation detail you should not rely on). We make no attempt to say if a
117 // model is invalid (e.g. a variable lower bound is infinite, exceeds an upper
118 // bound, or is NaN). The exported models are validated instead, see
119 // model_validator.h.
120
121 #ifndef OR_TOOLS_MATH_OPT_CORE_INDEXED_MODEL_H_
122 #define OR_TOOLS_MATH_OPT_CORE_INDEXED_MODEL_H_
123
124 #include <cstdint>
125 #include <limits>
126 #include <memory>
127 #include <optional>
128 #include <string>
129 #include <utility>
130 #include <vector>
131
132 #include "ortools/base/integral_types.h"
133 #include "absl/base/thread_annotations.h"
134 #include "absl/container/flat_hash_map.h"
135 #include "absl/container/flat_hash_set.h"
136 #include "absl/meta/type_traits.h"
137 #include "absl/strings/string_view.h"
138 #include "absl/synchronization/mutex.h"
139 #include "absl/types/span.h"
140 #include "ortools/base/map_util.h"
141 #include "ortools/base/int_type.h"
142 #include "ortools/math_opt/model.pb.h"
143 #include "ortools/math_opt/model_update.pb.h"
144 #include "ortools/math_opt/result.pb.h"
145 #include "ortools/math_opt/solution.pb.h"
146 #include "ortools/math_opt/sparse_containers.pb.h"
147
148 namespace operations_research {
149 namespace math_opt {
150
151 DEFINE_INT_TYPE(VariableId, int64_t);
152 DEFINE_INT_TYPE(LinearConstraintId, int64_t);
153
154 // A mathematical optimization model.
155 //
156 // Supports the efficient creation and modification of an optimization model,
157 // and the export of Model and ModelUpdate protos.
158 //
159 // All methods run in amortized O(1) (as amortized over calls to that exact
160 // function) unless otherwise specified.
161 class IndexedModel {
162 public:
163 // Tracks the changes of the model.
164 //
165 // For each update tracker we define a checkpoint that is the starting point
166 // used to compute the ModelUpdateProto.
167 //
168 // Lifecycle: the IndexedModel must outlive all the UpdateTracker instances
169 // since they keep a reference to it. They use this reference in their
170 // destructor so it is not safe to destroy an UpdateTracker after the
171 // destruction of the IndexedModel.
172 //
173 // Thread-safety: UpdateTracker methods must not be used while modifying the
174 // IndexedModel. The user is expected to use proper synchronization primitives
175 // to serialize changes to the model and the use of the update trackers. The
176 // methods of different instances of UpdateTracker are safe to be called
177 // concurrently (i.e. multiple trackers can be called concurrently on
178 // ExportModelUpdate() or Checkpoint()).
179 //
180 // Example:
181 // IndexedModel model;
182 // ...
183 // ASSIGN_OR_RETURN(const auto solver,
184 // Solver::New(solver_type, model.ExportModel(),
185 // /*initializer=*/{}));
186 // const std::unique_ptr<IndexedModel::UpdateTracker> update_tracker =
187 // model.NewUpdatesTracker();
188 //
189 // ASSIGN_OR_RETURN(const auto result_1,
190 // solver->Solve(/*parameters=*/{});
191 //
192 // model.AddVariable(0.0, 1.0, true, "y");
193 // model.set_maximize(true);
194 //
195 // const absl::optional<ModelUpdateProto> update_proto =
196 // update_tracker.ExportModelUpdate();
197 // update_tracker.Checkpoint();
198 //
199 // if (update_proto) {
200 // ASSIGN_OR_RETURN(const bool updated, solver->Update(*update_proto));
201 // if (!updated) {
202 // // The update is not supported by the solver, we create a new one.
203 // ASSIGN_OR_RETURN(const auto new_model_proto, model.ExportModel());
204 // ASSIGN_OR_RETURN(solver,
205 // Solver::New(solver_type, new_model_proto,
206 // /*initializer=*/{}));
207 // }
208 // }
209 // ASSIGN_OR_RETURN(const auto result_2,
210 // solver->Solve(/*parameters=*/{});
211 //
212 class UpdateTracker {
213 public:
214 ~UpdateTracker() ABSL_LOCKS_EXCLUDED(indexed_model_.update_trackers_lock_);
215
216 // Returns a proto representation of the changes to the model since the most
217 // recent checkpoint (i.e. last time Checkpoint() was called); nullopt if
218 // the update would have been empty.
219 absl::optional<ModelUpdateProto> ExportModelUpdate()
220 ABSL_LOCKS_EXCLUDED(indexed_model_.update_trackers_lock_);
221
222 // Uses the current model state as the starting point to calculate the
223 // ModelUpdateProto next time ExportModelUpdate() is called.
224 void Checkpoint() ABSL_LOCKS_EXCLUDED(indexed_model_.update_trackers_lock_);
225
226 private:
227 friend class IndexedModel;
228
229 // Registers in update_trackers_ and calls Checkpoint() to synchronize the
230 // checkpoint to the current state of the model.
231 explicit UpdateTracker(IndexedModel& indexed_model)
232 ABSL_LOCKS_EXCLUDED(indexed_model.update_trackers_lock_);
233
234 // Same as Checkpoint() but the caller must have acquired the
235 // update_trackers_lock_ mutex.
236 void CheckpointLocked()
237 ABSL_EXCLUSIVE_LOCKS_REQUIRED(indexed_model_.update_trackers_lock_);
238
239 IndexedModel& indexed_model_;
240
241 // All incremental updates that occurred since last checkpoint. It is
242 // filled-in each time Checkpoint() is called on any update tracker. When an
243 // ExportModelUpdate() is requested on a tracker, all these are merged along
244 // with the remaining updates.
245 std::vector<std::shared_ptr<const ModelUpdateProto>> updates_
246 ABSL_GUARDED_BY(indexed_model_.update_trackers_lock_);
247 };
248
249 // Creates an empty minimization problem.
name_(name)250 explicit IndexedModel(absl::string_view name = "") : name_(name) {}
251
252 // TODO(b/185892243): add `std::unique_ptr<IndexedModel> Clone()` method.
253 IndexedModel(const IndexedModel&) = delete;
254 IndexedModel& operator=(const IndexedModel&) = delete;
255
name()256 inline const std::string& name() const { return name_; }
257
258 //////////////////////////////////////////////////////////////////////////////
259 // Variables
260 //////////////////////////////////////////////////////////////////////////////
261
262 // Adds a continuous unbounded variable to the model and returns its id.
263 //
264 // See AddVariable(double, double, bool, absl::string_view) for details.
265 inline VariableId AddVariable(absl::string_view name = "");
266
267 // Adds a variable to the model and returns its id.
268 //
269 // The returned ids begin at zero and increase by one with each call to
270 // AddVariable. Deleted ids are NOT reused. If no variables are deleted,
271 // the ids in the model will be consecutive.
272 VariableId AddVariable(double lower_bound, double upper_bound,
273 bool is_integer, absl::string_view name = "");
274
275 inline double variable_lower_bound(VariableId id) const;
276 inline double variable_upper_bound(VariableId id) const;
277 inline bool is_variable_integer(VariableId id) const;
278 inline const std::string& variable_name(VariableId id) const;
279
280 inline void set_variable_lower_bound(VariableId id, double lower_bound);
281 inline void set_variable_upper_bound(VariableId id, double upper_bound);
282 inline void set_variable_is_integer(VariableId id, bool is_integer);
283 inline void set_variable_as_integer(VariableId id);
284 inline void set_variable_as_continuous(VariableId id);
285
286 // Removes a variable from the model.
287 //
288 // It is an error to use a deleted variable id as input to any subsequent
289 // function calls on the model. Runs in O(#constraints containing the
290 // variable).
291 void DeleteVariable(VariableId id);
292
293 // The number of variables in the model.
294 //
295 // Equal to the number of variables created minus the number of variables
296 // deleted.
297 inline int num_variables() const;
298
299 // The returned id of the next call to AddVariable.
300 //
301 // Equal to the number of variables created.
302 inline VariableId next_variable_id() const;
303
304 // Returns true if this id has been created and not yet deleted.
305 inline bool has_variable(VariableId id) const;
306
307 // The VariableIds in use (not deleted), order not defined.
308 std::vector<VariableId> variables() const;
309
310 // Returns a sorted vector of all existing (not deleted) variables in the
311 // model.
312 //
313 // Runs in O(n log(n)), where n is the number of variables returned.
314 std::vector<VariableId> SortedVariables() const;
315
316 //////////////////////////////////////////////////////////////////////////////
317 // Linear Constraints
318 //////////////////////////////////////////////////////////////////////////////
319
320 // Adds a linear constraint to the model with a lower bound of -inf and an
321 // upper bound of +inf and returns its id.
322 //
323 // See AddLinearConstraint(double, double, absl::string_view) for details.
324 inline LinearConstraintId AddLinearConstraint(absl::string_view name = "");
325
326 // Adds a linear constraint to the model returns its id.
327 //
328 // The returned ids begin at zero and increase by one with each call to
329 // AddLinearConstraint. Deleted ids are NOT reused. If no linear
330 // constraints are deleted, the ids in the model will be consecutive.
331 LinearConstraintId AddLinearConstraint(double lower_bound, double upper_bound,
332 absl::string_view name = "");
333
334 inline double linear_constraint_lower_bound(LinearConstraintId id) const;
335 inline double linear_constraint_upper_bound(LinearConstraintId id) const;
336 inline const std::string& linear_constraint_name(LinearConstraintId id) const;
337
338 inline void set_linear_constraint_lower_bound(LinearConstraintId id,
339 double lower_bound);
340 inline void set_linear_constraint_upper_bound(LinearConstraintId id,
341 double upper_bound);
342
343 // Removes a linear constraint from the model.
344 //
345 // It is an error to use a deleted linear constraint id as input to any
346 // subsequent function calls on the model. Runs in O(#variables in the linear
347 // constraint).
348 void DeleteLinearConstraint(LinearConstraintId id);
349
350 // The number of linear constraints in the model.
351 //
352 // Equal to the number of linear constraints created minus the number of
353 // linear constraints deleted.
354 inline int num_linear_constraints() const;
355
356 // The returned id of the next call to AddLinearConstraint.
357 //
358 // Equal to the number of linear constraints created.
359 inline LinearConstraintId next_linear_constraint_id() const;
360
361 // Returns true if this id has been created and not yet deleted.
362 inline bool has_linear_constraint(LinearConstraintId id) const;
363
364 // The LinearConstraintsIds in use (not deleted), order not defined.
365 std::vector<LinearConstraintId> linear_constraints() const;
366
367 // Returns a sorted vector of all existing (not deleted) linear constraints in
368 // the model.
369 //
370 // Runs in O(n log(n)), where n is the number of linear constraints returned.
371 std::vector<LinearConstraintId> SortedLinearConstraints() const;
372
373 //////////////////////////////////////////////////////////////////////////////
374 // Linear constraint matrix
375 //////////////////////////////////////////////////////////////////////////////
376
377 // Returns 0.0 if the entry is not in matrix.
378 inline double linear_constraint_coefficient(LinearConstraintId constraint,
379 VariableId variable) const;
380 inline bool is_linear_constraint_coefficient_nonzero(
381 LinearConstraintId constraint, VariableId variable) const;
382
383 // Setting a value to 0.0 will delete the {constraint, variable} pair from the
384 // underlying sparse matrix representation (and has no effect if the pair is
385 // not present).
386 inline void set_linear_constraint_coefficient(LinearConstraintId constraint,
387 VariableId variable,
388 double value);
389
390 // The {linear constraint, variable} pairs with nonzero linear constraint
391 // matrix coefficients.
392 inline const absl::flat_hash_map<std::pair<LinearConstraintId, VariableId>,
393 double>&
394 linear_constraint_matrix() const;
395
396 // Returns the variables with nonzero coefficients in a linear constraint.
397 //
398 // Runs in O(1), but triggers allocations that are O(nnz) on first use through
399 // a lazy initialization.
400 inline const absl::flat_hash_set<VariableId>& variables_in_linear_constraint(
401 LinearConstraintId constraint);
402
403 // Returns the linear constraints with nonzero coefficients on a variable.
404 //
405 // Runs in O(1), but triggers allocations that are O(nnz) on first use through
406 // a lazy initialization.
407 inline const absl::flat_hash_set<LinearConstraintId>&
408 linear_constraints_with_variable(VariableId variable);
409
410 //////////////////////////////////////////////////////////////////////////////
411 // Objective
412 //////////////////////////////////////////////////////////////////////////////
413
414 inline bool is_maximize() const;
415 inline double objective_offset() const;
416 // Returns 0.0 if this variable has no linear objective coefficient.
417 inline double linear_objective_coefficient(VariableId variable) const;
418 inline bool is_linear_objective_coefficient_nonzero(
419 VariableId variable) const;
420
421 inline void set_is_maximize(bool is_maximize);
422 inline void set_maximize();
423 inline void set_minimize();
424 inline void set_objective_offset(double value);
425
426 // Setting a value to 0.0 will delete the variable from the underlying sparse
427 // representation (and has no effect if the variable is not present).
428 inline void set_linear_objective_coefficient(VariableId variable,
429 double value);
430
431 // Equivalent to calling set_linear_objective_coefficient(v, 0.0) for every
432 // variable with nonzero objective coefficient.
433 //
434 // Runs in O(#variables with nonzero objective coefficient).
435 inline void clear_objective();
436
437 // The variables with nonzero linear objective coefficients.
438 inline const absl::flat_hash_map<VariableId, double>& linear_objective()
439 const;
440
441 // Returns a sorted vector of all variables in the model with nonzero linear
442 // objective coefficients.
443 //
444 // Runs in O(n log(n)), where n is the number of variables returned.
445 std::vector<VariableId> SortedLinearObjectiveNonzeroVariables() const;
446
447 //////////////////////////////////////////////////////////////////////////////
448 // Export
449 //////////////////////////////////////////////////////////////////////////////
450
451 // Returns a proto representation of the optimization model.
452 ModelProto ExportModel() const;
453
454 // Returns a tracker that can be used to generate a ModelUpdateProto with the
455 // updates that happened since the last checkpoint. The tracker initial
456 // checkpoint corresponds to the current state of the model.
457 //
458 // The returned UpdateTracker keeps a reference to this IndexedModel. Thus the
459 // IndexedModel must not be destroyed before the destruction of all its
460 // UpdateTracker instances.
461 //
462 // Thread-safety: this method must not be used while modifying the
463 // IndexedModel. The user is expected to use proper synchronization primitive
464 // to serialize changes to the model and the use of this method.
465 std::unique_ptr<UpdateTracker> NewUpdateTracker();
466
467 private:
468 struct VariableData {
469 double lower_bound = -std::numeric_limits<double>::infinity();
470 double upper_bound = std::numeric_limits<double>::infinity();
471 bool is_integer = false;
472 std::string name = "";
473 };
474 struct LinearConstraintData {
475 double lower_bound = -std::numeric_limits<double>::infinity();
476 double upper_bound = std::numeric_limits<double>::infinity();
477 std::string name = "";
478 };
479
480 template <typename T>
481 void set_variable_property(VariableId id, T value, T VariableData::*field,
482 absl::flat_hash_set<VariableId>& dirty_set);
483
484 inline void set_linear_constraint_property(
485 const LinearConstraintId id, double value,
486 double LinearConstraintData::*field,
487 absl::flat_hash_set<LinearConstraintId>& dirty_set);
488
489 // Initializes lazy_matrix_columns_ (column major storage of the linear
490 // constraint matrix) if it is still empty and there is at least one variable
491 // in the model.
492 void EnsureLazyMatrixColumns();
493
494 // Initializes lazy_matrix_rows_ (row major storage of the linear constraint
495 // matrix) if it is still empty and there is at least one linear constraint in
496 // the model.
497 void EnsureLazyMatrixRows();
498
499 // Export a single variable to proto.
500 void AppendVariable(VariableId id, VariablesProto& variables_proto) const;
501
502 // Export a single linear constraint to proto.
503 void AppendLinearConstraint(
504 LinearConstraintId id,
505 LinearConstraintsProto& linear_constraints_proto) const;
506
507 // If an element in entries is not found in linear_constraint_matrix_, it is
508 // set to 0.0 in matrix. Entries should be sorted by constraint then by
509 // variable.
510 void ExportLinearConstraintMatrix(
511 absl::Span<const std::pair<LinearConstraintId, VariableId>> entries,
512 SparseDoubleMatrixProto& matrix) const;
513
514 // Returns a proto representation of the changes to the model since the most
515 // recent call to SharedCheckpoint() or nullopt if no changes happened.
516 //
517 // Thread-safety: this method must not be called concurrently (due to
518 // EnsureLazyMatrixXxx() functions).
519 absl::optional<ModelUpdateProto> ExportSharedModelUpdate()
520 ABSL_EXCLUSIVE_LOCKS_REQUIRED(update_trackers_lock_);
521
522 // Use the current model state as the starting point to calculate the
523 // ModelUpdateProto next time ExportSharedModelUpdate() is called.
524 void SharedCheckpoint() ABSL_EXCLUSIVE_LOCKS_REQUIRED(update_trackers_lock_);
525
526 std::string name_;
527 VariableId next_variable_id_ = VariableId(0);
528 LinearConstraintId next_linear_constraint_id_ = LinearConstraintId(0);
529
530 bool is_maximize_ = false;
531 double objective_offset_ = 0.0;
532
533 absl::flat_hash_map<VariableId, VariableData> variables_;
534 absl::flat_hash_map<LinearConstraintId, LinearConstraintData>
535 linear_constraints_;
536 // The values of the map must never include zero.
537 absl::flat_hash_map<VariableId, double> linear_objective_;
538 // The values of the map must never include zero.
539 absl::flat_hash_map<std::pair<LinearConstraintId, VariableId>, double>
540 linear_constraint_matrix_;
541 absl::flat_hash_map<VariableId, absl::flat_hash_set<LinearConstraintId>>
542 lazy_matrix_columns_;
543 absl::flat_hash_map<LinearConstraintId, absl::flat_hash_set<VariableId>>
544 lazy_matrix_rows_;
545
546 // Update information
547 //
548 // Implicitly, all data for variables and constraints added after the last
549 // checkpoint are considered "new" and will NOT be stored in the "dirty" data
550 // structures below.
551 VariableId variables_checkpoint_ = VariableId(0);
552 LinearConstraintId linear_constraints_checkpoint_ = LinearConstraintId(0);
553 bool dirty_objective_direction_ = false;
554 bool dirty_objective_offset_ = false;
555
556 absl::flat_hash_set<VariableId> dirty_variable_deletes_;
557 absl::flat_hash_set<VariableId> dirty_variable_lower_bounds_;
558 absl::flat_hash_set<VariableId> dirty_variable_upper_bounds_;
559 absl::flat_hash_set<VariableId> dirty_variable_is_integer_;
560
561 absl::flat_hash_set<VariableId> dirty_linear_objective_coefficients_;
562
563 absl::flat_hash_set<LinearConstraintId> dirty_linear_constraint_deletes_;
564 absl::flat_hash_set<LinearConstraintId> dirty_linear_constraint_lower_bounds_;
565 absl::flat_hash_set<LinearConstraintId> dirty_linear_constraint_upper_bounds_;
566
567 // Only for pairs where both the variable and constraint are before the
568 // checkpoint, i.e.
569 // var_id < variables_checkpoint_ &&
570 // lin_con_id < linear_constraints_checkpoint_
571 absl::flat_hash_set<std::pair<LinearConstraintId, VariableId>>
572 dirty_linear_constraint_matrix_keys_;
573
574 // Lock used to serialize access to update_trackers_ and to the all fields of
575 // UpdateTracker. We use only one lock since trackers are modified in group
576 // (they share a chain of ModelUpdateProto and the update of one tracker
577 // usually requires the update of some of the others).
578 absl::Mutex update_trackers_lock_;
579
580 // The UpdateTracker instances tracking the changes of to this model. This
581 // collection is updated by UpdateTracker constructor and destructor. It is
582 // used internally by UpdateTracker instances to know about other instances.
583 absl::flat_hash_set<UpdateTracker*> update_trackers_
584 ABSL_GUARDED_BY(update_trackers_lock_);
585 };
586
587 // A solution to the problem modeled in IndexedModel.
588 //
589 // IndexedPrimalSolution will satisfy (see top of file notation):
590 // objective_value = c * variable_values + d
591 // In addition, if feasible (as is typical), it should additionally satisfy:
592 // vlb <= variable_values <= vub
593 // clb <= A * variable_values <= cub
594 // variable_values_i integer for i in I.
595 //
596 // For details, see go/mathopt-solutions#primal-solution.
597 struct IndexedPrimalSolution {
598 absl::flat_hash_map<VariableId, double> variable_values;
599 double objective_value;
600 };
601
602 // A direction of improving objective value that maintains feasibility.
603 //
604 // Indexed primal ray will satisfy (see top of file notation):
605 // * c * x < 0 for minimization problems, c * x > 0 for maximization problems.
606 // * A_j * x <= 0 for finite cub_j
607 // * A_j * x >= 0 for finite clb_j
608 // * x_i <= 0 for finite vub_i
609 // * x_i >= 0 for finite vlb_i
610 // where A_j are the row of matrix coefficients for the jth linear constraint.
611 //
612 //
613 // Note that this alone does not prove unboundedness, you also need a feasible
614 // point. This is a certificate of dual infeasibility for LPs, see
615 // go/mathopt-dual#dual-inf-cert.
616 //
617 // For details, see go/mathopt-solutions#primal-ray.
618 struct IndexedPrimalRay {
619 absl::flat_hash_map<VariableId, double> variable_values;
620 };
621
622 // A solution to the dual of the problem modeled in IndexedModel. Applies only
623 // when the problem has a dual (e.g. LP).
624 //
625 // For details, see go/mathopt-dual#dual-solution.
626 // For an primal interpretation as objective-value/optimality certificates see:
627 // go/mathopt-solutions#opt-certificate
628 struct IndexedDualSolution {
629 absl::flat_hash_map<LinearConstraintId, double> dual_values;
630 absl::flat_hash_map<VariableId, double> reduced_costs;
631 double objective_value;
632 };
633
634 // A direction of improving objective value that maintains feasibility for the
635 // dual problem. Applies only when the problem has a dual (e.g. LP).
636 //
637 // Note that this alone does not prove dual unboundedness, you also need a dual
638 // feasible point.
639 //
640 // Also, a certificate of primal infeasibility.
641 //
642 // For details, see
643 // go/mathopt-dual#dual-ray
644 // go/mathopt-solutions#primal-inf-cert
645 struct IndexedDualRay {
646 absl::flat_hash_map<LinearConstraintId, double> dual_values;
647 absl::flat_hash_map<VariableId, double> reduced_costs;
648 };
649
650 // A basis for a solution of the problem modeled in IndexedModel. Applies only
651 // when the problem is an LP.
652 //
653 // For details, see go/mathopt-basis#basis.
654 // TODO(b/171883688): consider improving consistency for matchers in
655 // solver_matchers.h/cc (e.g. removing PrimalDualPair from that file)
656 struct IndexedBasis {
657 absl::flat_hash_map<LinearConstraintId, BasisStatus> constraint_status;
658 absl::flat_hash_map<VariableId, BasisStatus> variable_status;
659 };
660
661 // The solution (or potentially multiple solutions) to an LP or MIP. For LP,
662 // if the problem is solved to completion (i.e. we don't have an error or hit a
663 // limit), then at least one of these should be populated.
664 struct IndexedSolutions {
665 std::vector<IndexedPrimalSolution> primal_solutions;
666 std::vector<IndexedPrimalRay> primal_rays;
667 std::vector<IndexedDualSolution> dual_solutions;
668 std::vector<IndexedDualRay> dual_rays;
669 std::vector<IndexedBasis> basis;
670 };
671
672 IndexedSolutions IndexedSolutionsFromProto(
673 const SolveResultProto& solve_result);
674
675 ////////////////////////////////////////////////////////////////////////////////
676 ////////////////////////////////////////////////////////////////////////////////
677 // Inlined function implementations
678 ////////////////////////////////////////////////////////////////////////////////
679 ////////////////////////////////////////////////////////////////////////////////
680
681 ////////////////////////////////////////////////////////////////////////////////
682 // Variables
683 ////////////////////////////////////////////////////////////////////////////////
684
AddVariable(absl::string_view name)685 VariableId IndexedModel::AddVariable(absl::string_view name) {
686 return AddVariable(-std::numeric_limits<double>::infinity(),
687 std::numeric_limits<double>::infinity(), false, name);
688 }
689
variable_lower_bound(const VariableId id)690 double IndexedModel::variable_lower_bound(const VariableId id) const {
691 return variables_.at(id).lower_bound;
692 }
693
variable_upper_bound(const VariableId id)694 double IndexedModel::variable_upper_bound(const VariableId id) const {
695 return variables_.at(id).upper_bound;
696 }
697
is_variable_integer(VariableId id)698 bool IndexedModel::is_variable_integer(VariableId id) const {
699 return variables_.at(id).is_integer;
700 }
701
variable_name(const VariableId id)702 const std::string& IndexedModel::variable_name(const VariableId id) const {
703 return variables_.at(id).name;
704 }
705
706 template <typename T>
set_variable_property(const VariableId id,const T value,T VariableData::* const field,absl::flat_hash_set<VariableId> & dirty_set)707 void IndexedModel::set_variable_property(
708 const VariableId id, const T value, T VariableData::*const field,
709 absl::flat_hash_set<VariableId>& dirty_set) {
710 VariableData& var_data = variables_.at(id);
711 if (var_data.*field != value) {
712 var_data.*field = value;
713 if (id < variables_checkpoint_) {
714 dirty_set.insert(id);
715 }
716 }
717 }
718
set_variable_lower_bound(const VariableId id,const double lower_bound)719 void IndexedModel::set_variable_lower_bound(const VariableId id,
720 const double lower_bound) {
721 set_variable_property(id, lower_bound, &VariableData::lower_bound,
722 dirty_variable_lower_bounds_);
723 }
724
set_variable_upper_bound(const VariableId id,const double upper_bound)725 void IndexedModel::set_variable_upper_bound(const VariableId id,
726 const double upper_bound) {
727 set_variable_property(id, upper_bound, &VariableData::upper_bound,
728 dirty_variable_upper_bounds_);
729 }
730
set_variable_is_integer(const VariableId id,const bool is_integer)731 void IndexedModel::set_variable_is_integer(const VariableId id,
732 const bool is_integer) {
733 set_variable_property(id, is_integer, &VariableData::is_integer,
734 dirty_variable_is_integer_);
735 }
736
set_variable_as_integer(VariableId id)737 void IndexedModel::set_variable_as_integer(VariableId id) {
738 set_variable_is_integer(id, true);
739 }
740
set_variable_as_continuous(VariableId id)741 void IndexedModel::set_variable_as_continuous(VariableId id) {
742 set_variable_is_integer(id, false);
743 }
744
num_variables()745 int IndexedModel::num_variables() const { return variables_.size(); }
746
next_variable_id()747 VariableId IndexedModel::next_variable_id() const { return next_variable_id_; }
748
has_variable(const VariableId id)749 bool IndexedModel::has_variable(const VariableId id) const {
750 return variables_.contains(id);
751 }
752
753 ////////////////////////////////////////////////////////////////////////////////
754 // Linear Constraints
755 ////////////////////////////////////////////////////////////////////////////////
756
AddLinearConstraint(absl::string_view name)757 LinearConstraintId IndexedModel::AddLinearConstraint(absl::string_view name) {
758 return AddLinearConstraint(-std::numeric_limits<double>::infinity(),
759 std::numeric_limits<double>::infinity(), name);
760 }
761
linear_constraint_lower_bound(const LinearConstraintId id)762 double IndexedModel::linear_constraint_lower_bound(
763 const LinearConstraintId id) const {
764 return linear_constraints_.at(id).lower_bound;
765 }
766
linear_constraint_upper_bound(const LinearConstraintId id)767 double IndexedModel::linear_constraint_upper_bound(
768 const LinearConstraintId id) const {
769 return linear_constraints_.at(id).upper_bound;
770 }
771
linear_constraint_name(const LinearConstraintId id)772 const std::string& IndexedModel::linear_constraint_name(
773 const LinearConstraintId id) const {
774 return linear_constraints_.at(id).name;
775 }
776
set_linear_constraint_property(const LinearConstraintId id,const double value,double LinearConstraintData::* const field,absl::flat_hash_set<LinearConstraintId> & dirty_set)777 void IndexedModel::set_linear_constraint_property(
778 const LinearConstraintId id, const double value,
779 double LinearConstraintData::*const field,
780 absl::flat_hash_set<LinearConstraintId>& dirty_set) {
781 LinearConstraintData& lin_con_data = linear_constraints_.at(id);
782 if (lin_con_data.*field != value) {
783 lin_con_data.*field = value;
784 if (id < linear_constraints_checkpoint_) {
785 dirty_set.insert(id);
786 }
787 }
788 }
789
set_linear_constraint_lower_bound(const LinearConstraintId id,const double lower_bound)790 void IndexedModel::set_linear_constraint_lower_bound(
791 const LinearConstraintId id, const double lower_bound) {
792 set_linear_constraint_property(id, lower_bound,
793 &LinearConstraintData::lower_bound,
794 dirty_linear_constraint_lower_bounds_);
795 }
796
set_linear_constraint_upper_bound(const LinearConstraintId id,const double upper_bound)797 void IndexedModel::set_linear_constraint_upper_bound(
798 const LinearConstraintId id, const double upper_bound) {
799 set_linear_constraint_property(id, upper_bound,
800 &LinearConstraintData::upper_bound,
801 dirty_linear_constraint_upper_bounds_);
802 }
803
num_linear_constraints()804 int IndexedModel::num_linear_constraints() const {
805 return linear_constraints_.size();
806 }
807
next_linear_constraint_id()808 LinearConstraintId IndexedModel::next_linear_constraint_id() const {
809 return next_linear_constraint_id_;
810 }
811
has_linear_constraint(const LinearConstraintId id)812 bool IndexedModel::has_linear_constraint(const LinearConstraintId id) const {
813 return linear_constraints_.contains(id);
814 }
815
816 ////////////////////////////////////////////////////////////////////////////////
817 // Linear Constraint Matrix
818 ////////////////////////////////////////////////////////////////////////////////
819
linear_constraint_coefficient(LinearConstraintId constraint,VariableId variable)820 double IndexedModel::linear_constraint_coefficient(
821 LinearConstraintId constraint, VariableId variable) const {
822 return gtl::FindWithDefault(linear_constraint_matrix_,
823 {constraint, variable});
824 }
825
is_linear_constraint_coefficient_nonzero(LinearConstraintId constraint,VariableId variable)826 bool IndexedModel::is_linear_constraint_coefficient_nonzero(
827 LinearConstraintId constraint, VariableId variable) const {
828 return linear_constraint_matrix_.contains({constraint, variable});
829 }
830
set_linear_constraint_coefficient(LinearConstraintId constraint,VariableId variable,double value)831 void IndexedModel::set_linear_constraint_coefficient(
832 LinearConstraintId constraint, VariableId variable, double value) {
833 bool was_updated = false;
834 if (value == 0.0) {
835 if (linear_constraint_matrix_.erase({constraint, variable}) > 0) {
836 was_updated = true;
837 if (!lazy_matrix_columns_.empty()) {
838 lazy_matrix_columns_.at(variable).erase(constraint);
839 }
840 if (!lazy_matrix_rows_.empty()) {
841 lazy_matrix_rows_.at(constraint).erase(variable);
842 }
843 }
844 } else {
845 const auto [iterator, inserted] =
846 linear_constraint_matrix_.try_emplace({constraint, variable}, value);
847 if (inserted) {
848 was_updated = true;
849 } else if (iterator->second != value) {
850 iterator->second = value;
851 was_updated = true;
852 }
853 if (!lazy_matrix_columns_.empty()) {
854 lazy_matrix_columns_.at(variable).insert(constraint);
855 }
856 if (!lazy_matrix_rows_.empty()) {
857 lazy_matrix_rows_.at(constraint).insert(variable);
858 }
859 }
860 if (was_updated && constraint < linear_constraints_checkpoint_ &&
861 variable < variables_checkpoint_) {
862 dirty_linear_constraint_matrix_keys_.emplace(constraint, variable);
863 }
864 }
865
866 const absl::flat_hash_map<std::pair<LinearConstraintId, VariableId>, double>&
linear_constraint_matrix()867 IndexedModel::linear_constraint_matrix() const {
868 return linear_constraint_matrix_;
869 }
870
871 const absl::flat_hash_set<VariableId>&
variables_in_linear_constraint(LinearConstraintId constraint)872 IndexedModel::variables_in_linear_constraint(LinearConstraintId constraint) {
873 EnsureLazyMatrixRows();
874 return lazy_matrix_rows_.at(constraint);
875 }
876
877 const absl::flat_hash_set<LinearConstraintId>&
linear_constraints_with_variable(VariableId variable)878 IndexedModel::linear_constraints_with_variable(VariableId variable) {
879 EnsureLazyMatrixColumns();
880 return lazy_matrix_columns_.at(variable);
881 }
882
883 ////////////////////////////////////////////////////////////////////////////////
884 // Objective
885 ////////////////////////////////////////////////////////////////////////////////
886
is_maximize()887 bool IndexedModel::is_maximize() const { return is_maximize_; }
888
objective_offset()889 double IndexedModel::objective_offset() const { return objective_offset_; }
890
linear_objective_coefficient(VariableId variable)891 double IndexedModel::linear_objective_coefficient(VariableId variable) const {
892 return gtl::FindWithDefault(linear_objective_, variable);
893 }
894
is_linear_objective_coefficient_nonzero(VariableId variable)895 bool IndexedModel::is_linear_objective_coefficient_nonzero(
896 VariableId variable) const {
897 return linear_objective_.contains(variable);
898 }
899
set_is_maximize(bool is_maximize)900 void IndexedModel::set_is_maximize(bool is_maximize) {
901 if (is_maximize_ != is_maximize) {
902 dirty_objective_direction_ = true;
903 is_maximize_ = is_maximize;
904 }
905 }
906
set_maximize()907 void IndexedModel::set_maximize() { set_is_maximize(true); }
908
set_minimize()909 void IndexedModel::set_minimize() { set_is_maximize(false); }
910
set_objective_offset(double value)911 void IndexedModel::set_objective_offset(double value) {
912 if (value != objective_offset_) {
913 dirty_objective_offset_ = true;
914 objective_offset_ = value;
915 }
916 }
917
set_linear_objective_coefficient(VariableId variable,double value)918 void IndexedModel::set_linear_objective_coefficient(VariableId variable,
919 double value) {
920 bool was_updated = false;
921 if (value == 0.0) {
922 if (linear_objective_.erase(variable) > 0) {
923 was_updated = true;
924 }
925 } else {
926 const auto [iterator, inserted] =
927 linear_objective_.try_emplace(variable, value);
928 if (inserted) {
929 was_updated = true;
930 } else if (iterator->second != value) {
931 iterator->second = value;
932 was_updated = true;
933 }
934 }
935 if (was_updated && variable < variables_checkpoint_) {
936 dirty_linear_objective_coefficients_.insert(variable);
937 }
938 }
939
clear_objective()940 void IndexedModel::clear_objective() {
941 set_objective_offset(0.0);
942 while (!linear_objective_.empty()) {
943 set_linear_objective_coefficient(linear_objective_.begin()->first, 0.0);
944 }
945 }
946
linear_objective()947 const absl::flat_hash_map<VariableId, double>& IndexedModel::linear_objective()
948 const {
949 return linear_objective_;
950 }
951
952 } // namespace math_opt
953 } // namespace operations_research
954
955 #endif // OR_TOOLS_MATH_OPT_CORE_INDEXED_MODEL_H_
956