28#include "absl/algorithm/container.h"
29#include "absl/container/flat_hash_map.h"
30#include "absl/container/flat_hash_set.h"
31#include "absl/log/check.h"
32#include "absl/memory/memory.h"
33#include "absl/meta/type_traits.h"
34#include "absl/status/status.h"
35#include "absl/status/statusor.h"
36#include "absl/strings/escaping.h"
37#include "absl/strings/str_cat.h"
38#include "absl/strings/str_join.h"
39#include "absl/strings/string_view.h"
40#include "absl/time/clock.h"
41#include "absl/time/time.h"
42#include "absl/types/span.h"
43#include "google/protobuf/repeated_ptr_field.h"
49#include "ortools/math_opt/callback.pb.h"
58#include "ortools/math_opt/infeasible_subsystem.pb.h"
59#include "ortools/math_opt/model.pb.h"
60#include "ortools/math_opt/model_parameters.pb.h"
61#include "ortools/math_opt/model_update.pb.h"
62#include "ortools/math_opt/parameters.pb.h"
63#include "ortools/math_opt/result.pb.h"
64#include "ortools/math_opt/solution.pb.h"
65#include "ortools/math_opt/solvers/gurobi.pb.h"
69#include "ortools/math_opt/sparse_containers.pb.h"
78constexpr SupportedProblemStructures kGurobiSupportedStructures = {
88absl::StatusOr<std::unique_ptr<Gurobi>> GurobiFromInitArgs(
89 const SolverInterface::InitArgs& init_args) {
91 return absl::FailedPreconditionError(
92 "the Gurobi library is not compatible with any sanitizer (MSAN, ASAN "
98 const NonStreamableGurobiInitArguments*
const non_streamable_args =
99 init_args.non_streamable !=
nullptr
100 ? init_args.non_streamable->ToNonStreamableGurobiInitArguments()
102 std::unique_ptr<Gurobi>
gurobi;
103 if (non_streamable_args !=
nullptr &&
104 non_streamable_args->primary_env !=
nullptr) {
106 }
else if (init_args.streamable.has_gurobi() &&
107 init_args.streamable.gurobi().has_isv_key()) {
117inline BasisStatusProto ConvertVariableStatus(
const int status) {
120 return BASIS_STATUS_BASIC;
122 return BASIS_STATUS_AT_LOWER_BOUND;
124 return BASIS_STATUS_AT_UPPER_BOUND;
126 return BASIS_STATUS_FREE;
128 return BASIS_STATUS_UNSPECIFIED;
132inline int GrbVariableStatus(
const BasisStatusProto
status) {
134 case BASIS_STATUS_BASIC:
136 case BASIS_STATUS_AT_LOWER_BOUND:
137 case BASIS_STATUS_FIXED_VALUE:
139 case BASIS_STATUS_AT_UPPER_BOUND:
141 case BASIS_STATUS_FREE:
143 case BASIS_STATUS_UNSPECIFIED:
145 LOG(FATAL) <<
"Unexpected invalid initial_basis.";
152absl::StatusOr<GurobiParametersProto> MergeParameters(
153 const SolveParametersProto& solve_parameters,
const bool is_mip) {
154 GurobiParametersProto merged_parameters;
157 GurobiParametersProto::Parameter*
const parameter =
158 merged_parameters.add_parameters();
160 parameter->set_value(solve_parameters.enable_output() ?
"1" :
"0");
163 if (solve_parameters.has_time_limit()) {
164 const double time_limit = absl::ToDoubleSeconds(
166 GurobiParametersProto::Parameter*
const parameter =
167 merged_parameters.add_parameters();
169 parameter->set_value(absl::StrCat(
time_limit));
172 if (solve_parameters.has_node_limit()) {
173 GurobiParametersProto::Parameter*
const parameter =
174 merged_parameters.add_parameters();
176 parameter->set_value(absl::StrCat(solve_parameters.node_limit()));
179 if (solve_parameters.has_threads()) {
180 const int threads = solve_parameters.threads();
181 GurobiParametersProto::Parameter*
const parameter =
182 merged_parameters.add_parameters();
184 parameter->set_value(absl::StrCat(threads));
187 if (solve_parameters.has_absolute_gap_tolerance()) {
188 const double absolute_gap_tolerance =
189 solve_parameters.absolute_gap_tolerance();
190 GurobiParametersProto::Parameter*
const parameter =
191 merged_parameters.add_parameters();
193 parameter->set_value(absl::StrCat(absolute_gap_tolerance));
196 if (solve_parameters.has_relative_gap_tolerance()) {
197 const double relative_gap_tolerance =
198 solve_parameters.relative_gap_tolerance();
199 GurobiParametersProto::Parameter*
const parameter =
200 merged_parameters.add_parameters();
202 parameter->set_value(absl::StrCat(relative_gap_tolerance));
205 if (solve_parameters.has_cutoff_limit()) {
206 GurobiParametersProto::Parameter*
const parameter =
207 merged_parameters.add_parameters();
209 parameter->set_value(absl::StrCat(solve_parameters.cutoff_limit()));
212 if (solve_parameters.has_objective_limit()) {
214 return absl::InvalidArgumentError(
215 "objective_limit is only supported for Gurobi on MIP models");
217 GurobiParametersProto::Parameter*
const parameter =
218 merged_parameters.add_parameters();
220 parameter->set_value(absl::StrCat(solve_parameters.objective_limit()));
223 if (solve_parameters.has_best_bound_limit()) {
225 return absl::InvalidArgumentError(
226 "best_bound_limit is only supported for Gurobi on MIP models");
228 GurobiParametersProto::Parameter*
const parameter =
229 merged_parameters.add_parameters();
231 parameter->set_value(absl::StrCat(solve_parameters.best_bound_limit()));
234 if (solve_parameters.has_solution_limit()) {
235 GurobiParametersProto::Parameter*
const parameter =
236 merged_parameters.add_parameters();
238 parameter->set_value(absl::StrCat(solve_parameters.solution_limit()));
241 if (solve_parameters.has_random_seed()) {
242 const int random_seed =
243 std::min(
GRB_MAXINT, std::max(solve_parameters.random_seed(), 0));
244 GurobiParametersProto::Parameter*
const parameter =
245 merged_parameters.add_parameters();
247 parameter->set_value(absl::StrCat(random_seed));
250 if (solve_parameters.has_solution_pool_size()) {
251 GurobiParametersProto::Parameter*
const solution_pool_size =
252 merged_parameters.add_parameters();
254 solution_pool_size->set_value(
255 absl::StrCat(solve_parameters.solution_pool_size()));
258 if (solve_parameters.lp_algorithm() != LP_ALGORITHM_UNSPECIFIED) {
259 GurobiParametersProto::Parameter*
const parameter =
260 merged_parameters.add_parameters();
262 switch (solve_parameters.lp_algorithm()) {
263 case LP_ALGORITHM_PRIMAL_SIMPLEX:
266 case LP_ALGORITHM_DUAL_SIMPLEX:
269 case LP_ALGORITHM_BARRIER:
272 case LP_ALGORITHM_FIRST_ORDER:
273 return absl::InvalidArgumentError(
274 "lp_algorithm FIRST_ORDER is not supported for gurobi");
276 LOG(FATAL) <<
"LPAlgorithm: "
278 <<
" unknown, error setting Gurobi parameters";
282 if (solve_parameters.scaling() != EMPHASIS_UNSPECIFIED) {
283 GurobiParametersProto::Parameter*
const parameter =
284 merged_parameters.add_parameters();
286 switch (solve_parameters.scaling()) {
288 parameter->set_value(absl::StrCat(0));
291 case EMPHASIS_MEDIUM:
292 parameter->set_value(absl::StrCat(1));
295 parameter->set_value(absl::StrCat(2));
297 case EMPHASIS_VERY_HIGH:
298 parameter->set_value(absl::StrCat(3));
301 LOG(FATAL) <<
"Scaling emphasis: "
303 <<
" unknown, error setting Gurobi parameters";
307 if (solve_parameters.cuts() != EMPHASIS_UNSPECIFIED) {
308 GurobiParametersProto::Parameter*
const parameter =
309 merged_parameters.add_parameters();
311 switch (solve_parameters.cuts()) {
313 parameter->set_value(absl::StrCat(0));
316 case EMPHASIS_MEDIUM:
317 parameter->set_value(absl::StrCat(1));
320 parameter->set_value(absl::StrCat(2));
322 case EMPHASIS_VERY_HIGH:
323 parameter->set_value(absl::StrCat(3));
326 LOG(FATAL) <<
"Cuts emphasis: "
328 <<
" unknown, error setting Gurobi parameters";
332 if (solve_parameters.heuristics() != EMPHASIS_UNSPECIFIED) {
333 GurobiParametersProto::Parameter*
const parameter =
334 merged_parameters.add_parameters();
336 switch (solve_parameters.heuristics()) {
338 parameter->set_value(absl::StrCat(0.0));
341 parameter->set_value(absl::StrCat(0.025));
343 case EMPHASIS_MEDIUM:
346 parameter->set_value(absl::StrCat(0.05));
349 parameter->set_value(absl::StrCat(0.1));
351 case EMPHASIS_VERY_HIGH:
352 parameter->set_value(absl::StrCat(0.2));
355 LOG(FATAL) <<
"Heuristics emphasis: "
357 <<
" unknown, error setting Gurobi parameters";
361 if (solve_parameters.presolve() != EMPHASIS_UNSPECIFIED) {
362 GurobiParametersProto::Parameter*
const parameter =
363 merged_parameters.add_parameters();
365 switch (solve_parameters.presolve()) {
367 parameter->set_value(absl::StrCat(0));
370 case EMPHASIS_MEDIUM:
371 parameter->set_value(absl::StrCat(1));
374 case EMPHASIS_VERY_HIGH:
375 parameter->set_value(absl::StrCat(2));
378 LOG(FATAL) <<
"Presolve emphasis: "
380 <<
" unknown, error setting Gurobi parameters";
384 if (solve_parameters.has_iteration_limit()) {
385 GurobiParametersProto::Parameter*
const iterationlimit =
386 merged_parameters.add_parameters();
388 iterationlimit->set_value(absl::StrCat(solve_parameters.iteration_limit()));
389 GurobiParametersProto::Parameter*
const bariterlimit =
390 merged_parameters.add_parameters();
392 double val = std::min<double>(std::numeric_limits<int32_t>::max(),
393 solve_parameters.iteration_limit());
394 bariterlimit->set_value(absl::StrCat(val));
397 for (
const GurobiParametersProto::Parameter& parameter :
399 *merged_parameters.add_parameters() = parameter;
402 return merged_parameters;
405absl::StatusOr<int64_t> SafeInt64FromDouble(
const double d) {
406 const int64_t result =
static_cast<int64_t
>(d);
407 if (
static_cast<double>(result) != d) {
408 return absl::InternalError(
409 absl::StrCat(
"Expected double ", d,
" to contain an int64_t."));
414const absl::flat_hash_set<CallbackEventProto>& SupportedMIPEvents() {
415 static const auto*
const kEvents =
416 new absl::flat_hash_set<CallbackEventProto>({
417 CALLBACK_EVENT_PRESOLVE, CALLBACK_EVENT_SIMPLEX, CALLBACK_EVENT_MIP,
418 CALLBACK_EVENT_MIP_SOLUTION, CALLBACK_EVENT_MIP_NODE,
427const absl::flat_hash_set<CallbackEventProto>& SupportedLPEvents() {
428 static const auto*
const kEvents =
429 new absl::flat_hash_set<CallbackEventProto>({
430 CALLBACK_EVENT_PRESOLVE,
431 CALLBACK_EVENT_SIMPLEX,
432 CALLBACK_EVENT_BARRIER,
439constexpr std::size_t kMaxNameSize = 255;
442std::string TruncateName(
const std::string_view original_name) {
444 original_name.substr(0, std::min(kMaxNameSize, original_name.size())));
448std::vector<std::string> TruncateNames(
449 const google::protobuf::RepeatedPtrField<std::string>& original_names) {
450 std::vector<std::string> result;
451 result.reserve(original_names.size());
452 for (
const std::string& original_name : original_names) {
453 result.push_back(TruncateName(original_name));
458absl::Status SafeGurobiDouble(
const double d) {
461 <<
"finite value: " << d <<
" will be treated as infinite by Gurobi";
463 return absl::OkStatus();
466std::string EscapedNameForLogging(
const absl::string_view
name) {
467 return absl::StrCat(
"\"", absl::Utf8SafeCEscape(
name),
"\"");
470constexpr int kDeletedIndex = -1;
471constexpr int kUnsetIndex = -2;
478std::vector<int> IndexUpdateMap(
const int size_before_delete,
479 absl::Span<const int> deletes) {
480 std::vector<int> result(size_before_delete, kUnsetIndex);
481 for (
const int del : deletes) {
482 result[del] = kDeletedIndex;
485 for (
int& r : result) {
486 if (r != kDeletedIndex) {
490 CHECK_GT(r, kUnsetIndex);
495absl::StatusOr<bool> GetIntAttrElementAsBool(Gurobi&
gurobi,
496 const char*
const name,
499 const bool cast_value(
value);
500 if (
static_cast<int>(cast_value) !=
value) {
502 <<
"Gurobi unexpectedly returned non-boolean value for " <<
name
510 OrAccumulator() =
default;
513 absl::Status Or(absl::StatusOr<bool> update) {
516 return absl::OkStatus();
518 bool value()
const {
return value_; }
526absl::Status AddMapEntryIfPresent(
527 const int64_t map_id,
528 absl::StatusOr<std::optional<ModelSubsetProto::Bounds>> maybe_value,
529 google::protobuf::Map<int64_t, ModelSubsetProto::Bounds>& target) {
531 if (maybe_value->has_value()) {
532 target[map_id] = **std::move(maybe_value);
534 return absl::OkStatus();
539absl::Status AppendEntryIfTrue(
540 const int64_t
id, absl::StatusOr<bool> should_append,
541 google::protobuf::RepeatedField<int64_t>& target) {
543 if (*should_append) {
546 return absl::OkStatus();
551GurobiSolver::GurobiSolver(std::unique_ptr<Gurobi> g_gurobi)
552 : gurobi_(
std::move(g_gurobi)) {}
554GurobiSolver::GurobiModelElements
555GurobiSolver::LinearConstraintData::DependentElements()
const {
556 GurobiModelElements elements;
559 if (slack_index != kUnspecifiedIndex) {
560 elements.variables.push_back(slack_index);
565GurobiSolver::GurobiModelElements
566GurobiSolver::SecondOrderConeConstraintData::DependentElements()
const {
567 const auto index_is_valid = [](
const auto index) {
return index >= 0; };
568 CHECK(absl::c_all_of(slack_variables, index_is_valid));
569 CHECK(absl::c_all_of(slack_constraints, index_is_valid));
571 GurobiModelElements elements{.variables = slack_variables,
572 .linear_constraints = slack_constraints};
577GurobiSolver::GurobiModelElements
578GurobiSolver::SosConstraintData::DependentElements()
const {
579 const auto index_is_valid = [](
const auto index) {
return index >= 0; };
580 CHECK(absl::c_all_of(slack_variables, index_is_valid));
581 CHECK(absl::c_all_of(slack_constraints, index_is_valid));
583 GurobiModelElements elements{.variables = slack_variables,
584 .linear_constraints = slack_constraints};
589absl::StatusOr<TerminationProto> GurobiSolver::ConvertTerminationReason(
590 const int gurobi_status,
const SolutionClaims solution_claims,
591 const double best_primal_bound,
const double best_dual_bound) {
593 switch (gurobi_status) {
602 is_maximize, solution_claims.dual_feasible_solution_exists
603 ? FEASIBILITY_STATUS_FEASIBLE
604 : FEASIBILITY_STATUS_UNDETERMINED);
608 if (solution_claims.primal_feasible_solution_exists) {
613 FEASIBILITY_STATUS_INFEASIBLE,
614 "Gurobi status GRB_UNBOUNDED");
618 FEASIBILITY_STATUS_UNDETERMINED,
619 "Gurobi status GRB_UNBOUNDED");
624 LIMIT_ITERATION, best_primal_bound, best_dual_bound,
625 solution_claims.dual_feasible_solution_exists);
628 LIMIT_NODE, best_primal_bound, best_dual_bound,
629 solution_claims.dual_feasible_solution_exists);
632 LIMIT_TIME, best_primal_bound, best_dual_bound,
633 solution_claims.dual_feasible_solution_exists);
636 LIMIT_SOLUTION, best_primal_bound, best_dual_bound,
637 solution_claims.dual_feasible_solution_exists);
640 LIMIT_INTERRUPTED, best_primal_bound, best_dual_bound,
641 solution_claims.dual_feasible_solution_exists);
644 TERMINATION_REASON_NUMERICAL_ERROR);
653 LIMIT_OBJECTIVE, best_primal_bound, best_dual_bound,
654 solution_claims.dual_feasible_solution_exists);
656 return absl::InternalError(
657 "Error creating termination reason, unexpected gurobi status code "
660 return absl::InternalError(
661 "Error creating termination reason, unexpected gurobi status code "
664 return absl::InternalError(absl::StrCat(
665 "Missing Gurobi optimization status code case: ", gurobi_status));
669absl::StatusOr<bool> GurobiSolver::IsMaximize()
const {
675absl::StatusOr<bool> GurobiSolver::IsMIP()
const {
677 return static_cast<bool>(is_mip);
681absl::StatusOr<bool> GurobiSolver::IsQP()
const {
683 return static_cast<bool>(is_qp);
686absl::StatusOr<bool> GurobiSolver::IsQCP()
const {
688 return static_cast<bool>(is_qcp);
694void GurobiSolver::GurobiVectorToSparseDoubleVector(
695 const absl::Span<const double> gurobi_values,
const T& map,
696 SparseDoubleVectorProto& result,
697 const SparseVectorFilterProto& filter)
const {
698 SparseVectorFilterPredicate predicate(filter);
699 for (
auto [
id, gurobi_data] : map) {
700 const double value = gurobi_values[get_model_index(gurobi_data)];
701 if (predicate.AcceptsAndUpdate(
id,
value)) {
703 result.add_values(
value);
708absl::Status GurobiSolver::SetGurobiBasis(
const BasisProto& basis) {
709 std::vector<int> gurobi_variable_basis_status(num_gurobi_variables_);
710 for (
const auto [
id,
value] :
MakeView(basis.variable_status())) {
711 gurobi_variable_basis_status[variables_map_.at(
id)] =
712 GrbVariableStatus(
static_cast<BasisStatusProto
>(
value));
715 std::vector<int> gurobi_constraint_basis_status;
716 gurobi_constraint_basis_status.reserve(num_gurobi_lin_cons_);
717 for (
const auto [
id,
value] :
MakeView(basis.constraint_status())) {
718 const LinearConstraintData& constraint_data =
719 linear_constraints_map_.at(
id);
721 if (constraint_data.slack_index == kUnspecifiedIndex) {
722 if (
value == BASIS_STATUS_BASIC) {
723 gurobi_constraint_basis_status.push_back(kGrbBasicConstraint);
725 gurobi_constraint_basis_status.push_back(kGrbNonBasicConstraint);
728 }
else if (
value == BASIS_STATUS_BASIC) {
732 gurobi_variable_basis_status[constraint_data.slack_index] =
GRB_BASIC;
733 gurobi_constraint_basis_status.push_back(kGrbNonBasicConstraint);
735 gurobi_variable_basis_status[constraint_data.slack_index] =
736 GrbVariableStatus(
static_cast<BasisStatusProto
>(
value));
737 gurobi_constraint_basis_status.push_back(kGrbNonBasicConstraint);
741 gurobi_variable_basis_status));
743 gurobi_constraint_basis_status));
744 return absl::OkStatus();
747absl::StatusOr<BasisProto> GurobiSolver::GetGurobiBasis() {
750 const std::vector<int> gurobi_variable_basis_status,
753 for (
auto [variable_id, gurobi_variable_index] : variables_map_) {
754 basis.mutable_variable_status()->add_ids(variable_id);
755 const BasisStatusProto variable_status = ConvertVariableStatus(
756 gurobi_variable_basis_status[gurobi_variable_index]);
757 if (variable_status == BASIS_STATUS_UNSPECIFIED) {
758 return absl::InternalError(
759 absl::StrCat(
"Invalid Gurobi variable basis status: ",
760 gurobi_variable_basis_status[gurobi_variable_index]));
762 basis.mutable_variable_status()->add_values(variable_status);
766 const std::vector<int> gurobi_constraint_basis_status,
768 for (
auto [constraint_id, gurobi_data] : linear_constraints_map_) {
769 basis.mutable_constraint_status()->add_ids(constraint_id);
770 const int gurobi_constraint_status =
771 gurobi_constraint_basis_status[gurobi_data.constraint_index];
772 if ((gurobi_constraint_status != kGrbBasicConstraint) &&
773 (gurobi_constraint_status != kGrbNonBasicConstraint)) {
774 return absl::InternalError(
775 absl::StrCat(
"Invalid Gurobi constraint basis status: ",
776 gurobi_constraint_status));
781 if (gurobi_constraint_status == kGrbBasicConstraint) {
782 basis.mutable_constraint_status()->add_values(BASIS_STATUS_BASIC);
784 basis.mutable_constraint_status()->add_values(
785 BASIS_STATUS_AT_UPPER_BOUND);
790 if (gurobi_constraint_status == kGrbBasicConstraint) {
791 basis.mutable_constraint_status()->add_values(BASIS_STATUS_BASIC);
793 basis.mutable_constraint_status()->add_values(
794 BASIS_STATUS_AT_LOWER_BOUND);
797 }
else if (gurobi_data.lower_bound == gurobi_data.upper_bound) {
798 if (gurobi_constraint_status == kGrbBasicConstraint) {
799 basis.mutable_constraint_status()->add_values(BASIS_STATUS_BASIC);
803 basis.mutable_constraint_status()->add_values(BASIS_STATUS_FIXED_VALUE);
807 const BasisStatusProto slack_status = ConvertVariableStatus(
808 gurobi_variable_basis_status[gurobi_data.slack_index]);
809 if (slack_status == BASIS_STATUS_UNSPECIFIED) {
810 return absl::InternalError(absl::StrCat(
811 "Invalid Gurobi slack variable basis status: ", slack_status));
813 if ((gurobi_constraint_status == kGrbBasicConstraint) ||
814 (slack_status == BASIS_STATUS_BASIC)) {
815 basis.mutable_constraint_status()->add_values(BASIS_STATUS_BASIC);
817 basis.mutable_constraint_status()->add_values(slack_status);
824absl::StatusOr<DualRayProto> GurobiSolver::GetGurobiDualRay(
825 const SparseVectorFilterProto& linear_constraints_filter,
826 const SparseVectorFilterProto& variables_filter,
const bool is_maximize) {
830 num_gurobi_lin_cons_));
832 DualRayProto dual_ray;
836 SparseVectorFilterPredicate predicate(linear_constraints_filter);
837 for (
auto [constraint_id, gurobi_data] : linear_constraints_map_) {
839 const double value = -farkas_dual[gurobi_data.constraint_index];
840 if (predicate.AcceptsAndUpdate(constraint_id,
value)) {
841 dual_ray.mutable_dual_values()->add_ids(constraint_id);
843 dual_ray.mutable_dual_values()->add_values(-
value);
845 dual_ray.mutable_dual_values()->add_values(
value);
853 SparseVectorFilterPredicate predicate(variables_filter);
854 for (
auto [var_id, gurobi_variable_index] : variables_map_) {
857 double reduced_cost_value = 0.0;
859 gurobi_->GetVars(gurobi_variable_index, 1));
860 for (
int i = 0;
i <
column.inds.size(); ++
i) {
861 reduced_cost_value += farkas_dual[
column.inds[
i]] *
column.vals[
i];
863 if (predicate.AcceptsAndUpdate(var_id, reduced_cost_value)) {
864 dual_ray.mutable_reduced_costs()->add_ids(var_id);
866 dual_ray.mutable_reduced_costs()->add_values(-reduced_cost_value);
868 dual_ray.mutable_reduced_costs()->add_values(reduced_cost_value);
876absl::StatusOr<SolveResultProto> GurobiSolver::ExtractSolveResultProto(
877 const absl::Time
start,
const ModelSolveParametersProto& model_parameters) {
878 SolveResultProto result;
881 SolutionClaims solution_claims;
883 GetSolutions(model_parameters));
891 solution_and_claims.solutions.clear();
892 solution_and_claims.solution_claims.primal_feasible_solution_exists =
false;
893 solution_and_claims.solution_claims.dual_feasible_solution_exists =
true;
896 GetBestPrimalBound(solution_and_claims.solutions));
898 GetBestDualBound(solution_and_claims.solutions));
899 solution_claims = solution_and_claims.solution_claims;
904 for (SolutionProto&
solution : solution_and_claims.solutions) {
905 *result.add_solutions() = std::move(
solution);
910 *result.mutable_termination(),
911 ConvertTerminationReason(grb_termination, solution_claims,
912 best_primal_bound, best_dual_bound));
915 return std::move(result);
918absl::StatusOr<bool> GurobiSolver::AnyElementInIIS(
919 const GurobiModelElements& grb_elements) {
920 OrAccumulator any_in_iis;
921 for (
const GurobiVariableIndex grb_index : grb_elements.variables) {
924 for (
const GurobiLinearConstraintIndex grb_index :
925 grb_elements.linear_constraints) {
929 for (
const GurobiQuadraticConstraintIndex grb_index :
930 grb_elements.quadratic_constraints) {
934 for (
const GurobiSosConstraintIndex grb_index :
935 grb_elements.sos_constraints) {
939 for (
const GurobiGeneralConstraintIndex grb_index :
940 grb_elements.general_constraints) {
944 return any_in_iis.value();
949absl::StatusOr<std::optional<ModelSubsetProto::Bounds>>
950GurobiSolver::VariableBoundsInIIS(
const GurobiVariableIndex grb_index) {
952 const bool var_lb_is_in_iis,
955 const bool var_ub_is_in_iis,
957 if (!var_lb_is_in_iis && !var_ub_is_in_iis) {
960 ModelSubsetProto::Bounds
bounds;
961 bounds.set_lower(var_lb_is_in_iis);
962 bounds.set_upper(var_ub_is_in_iis);
966absl::StatusOr<bool> GurobiSolver::VariableInIIS(
967 const GurobiVariableIndex grb_index) {
969 VariableBoundsInIIS(grb_index));
970 return bounds.has_value();
973absl::StatusOr<std::optional<ModelSubsetProto::Bounds>>
974GurobiSolver::LinearConstraintInIIS(
const LinearConstraintData& grb_data) {
981 AnyElementInIIS(grb_data.DependentElements()));
982 if (!constr_in_iis) {
985 ModelSubsetProto::Bounds result;
986 result.set_lower(grb_data.lower_bound != -kInf);
987 result.set_upper(grb_data.upper_bound != kInf);
991absl::StatusOr<std::optional<ModelSubsetProto::Bounds>>
992GurobiSolver::QuadraticConstraintInIIS(
993 const GurobiQuadraticConstraintIndex grb_index) {
995 const bool constr_in_iis,
997 if (!constr_in_iis) {
1001 const char constr_sense,
1003 ModelSubsetProto::Bounds result;
1004 result.set_lower(constr_sense ==
GRB_EQUAL ||
1010absl::StatusOr<ComputeInfeasibleSubsystemResultProto>
1011GurobiSolver::ExtractComputeInfeasibleSubsystemResultProto(
1012 const bool proven_infeasible) {
1013 ComputeInfeasibleSubsystemResultProto result;
1014 if (!proven_infeasible) {
1015 result.set_feasibility(FEASIBILITY_STATUS_UNDETERMINED);
1018 result.set_feasibility(FEASIBILITY_STATUS_INFEASIBLE);
1022 result.set_is_minimal(is_minimal);
1024 for (
const auto [
id, grb_index] : variables_map_) {
1026 id, VariableBoundsInIIS(grb_index),
1027 *result.mutable_infeasible_subsystem()->mutable_variable_bounds()));
1032 const char var_type,
1035 result.mutable_infeasible_subsystem()->add_variable_integrality(
1041 for (
const auto [
id, grb_data] : linear_constraints_map_) {
1043 id, LinearConstraintInIIS(grb_data),
1044 *result.mutable_infeasible_subsystem()->mutable_linear_constraints()));
1047 for (
const auto [
id, grb_index] : quadratic_constraints_map_) {
1049 id, QuadraticConstraintInIIS(grb_index),
1050 *result.mutable_infeasible_subsystem()
1051 ->mutable_quadratic_constraints()));
1054 for (
const auto& [
id, grb_data] : soc_constraints_map_) {
1056 id, AnyElementInIIS(grb_data.DependentElements()),
1057 *result.mutable_infeasible_subsystem()
1058 ->mutable_second_order_cone_constraints()));
1061 for (
const auto& [
id, grb_data] : sos1_constraints_map_) {
1063 id, AnyElementInIIS(grb_data.DependentElements()),
1064 *result.mutable_infeasible_subsystem()->mutable_sos1_constraints()));
1067 for (
const auto& [
id, grb_data] : sos2_constraints_map_) {
1069 id, AnyElementInIIS(grb_data.DependentElements()),
1070 *result.mutable_infeasible_subsystem()->mutable_sos2_constraints()));
1073 for (
const auto& [
id, maybe_grb_data] : indicator_constraints_map_) {
1074 if (!maybe_grb_data.has_value()) {
1081 maybe_grb_data->constraint_index),
1082 *result.mutable_infeasible_subsystem()
1083 ->mutable_indicator_constraints()));
1091absl::StatusOr<GurobiSolver::SolutionsAndClaims> GurobiSolver::GetSolutions(
1092 const ModelSolveParametersProto& model_parameters) {
1099 return GetMipSolutions(model_parameters);
1100 }
else if (is_qcp) {
1101 return GetQcpSolution(model_parameters);
1103 return GetQpSolution(model_parameters);
1105 return GetLpSolution(model_parameters);
1109absl::StatusOr<SolveStatsProto> GurobiSolver::GetSolveStats(
1110 const absl::Time
start)
const {
1111 SolveStatsProto solve_stats;
1114 solve_stats.mutable_solve_time()));
1120 SafeInt64FromDouble(simplex_iters_double));
1121 solve_stats.set_simplex_iterations(simplex_iters);
1127 solve_stats.set_barrier_iterations(barrier_iters);
1134 solve_stats.set_node_count(
nodes);
1139absl::StatusOr<GurobiSolver::SolutionsAndClaims> GurobiSolver::GetMipSolutions(
1140 const ModelSolveParametersProto& model_parameters) {
1141 int num_solutions = 0;
1145 std::vector<SolutionProto> solutions;
1146 solutions.reserve(num_solutions);
1148 for (
int i = 0;
i < num_solutions; ++
i) {
1155 if (is_multi_objective_mode()) {
1156 for (
const auto [
id, grb_index] : multi_objectives_map_) {
1162 if (
id.has_value()) {
1173 i == 0 ? SOLUTION_STATUS_FEASIBLE : SOLUTION_STATUS_UNDETERMINED);
1175 const std::vector<double> grb_var_values,
1177 GurobiVectorToSparseDoubleVector(grb_var_values, variables_map_,
1179 model_parameters.variable_values_filter());
1180 *solutions.emplace_back(SolutionProto()).mutable_primal_solution() =
1181 std::move(primal_solution);
1199 const SolutionClaims solution_claims = {
1200 .primal_feasible_solution_exists = num_solutions > 0,
1201 .dual_feasible_solution_exists =
1202 std::isfinite(best_dual_bound) || grb_termination ==
GRB_INFEASIBLE ||
1203 (is_multi_objective_mode() && grb_termination ==
GRB_OPTIMAL)};
1206 if (grb_termination ==
GRB_OPTIMAL && num_solutions == 0) {
1207 return absl::InternalError(
1208 "GRB_INT_ATTR_STATUS == GRB_OPTIMAL, but solution pool is empty.");
1212 if (!is_multi_objective_mode() && grb_termination ==
GRB_OPTIMAL &&
1213 !std::isfinite(best_dual_bound)) {
1214 return absl::InternalError(
1215 "GRB_INT_ATTR_STATUS == GRB_OPTIMAL, but GRB_DBL_ATTR_OBJBOUND is "
1216 "unavailable or infinite.");
1219 return SolutionsAndClaims{.solutions = std::move(solutions),
1220 .solution_claims = solution_claims};
1223absl::StatusOr<GurobiSolver::SolutionAndClaim<PrimalSolutionProto>>
1224GurobiSolver::GetConvexPrimalSolutionIfAvailable(
1225 const ModelSolveParametersProto& model_parameters) {
1227 return SolutionAndClaim<PrimalSolutionProto>{
1228 .solution = std::nullopt, .feasible_solution_exists =
false};
1235 const std::vector<double> grb_var_values,
1236 gurobi_->GetDoubleAttrArray(
GRB_DBL_ATTR_X, num_gurobi_variables_));
1252 const std::vector<double> linear_obj_coefs,
1254 for (
int i = 0;
i < num_gurobi_variables_; ++
i) {
1265 }
else if (PrimalSolutionQualityAvailable()) {
1266 ASSIGN_OR_RETURN(
const double solution_quality, GetPrimalSolutionQuality());
1269 if (solution_quality <= tolerance) {
1276 GurobiVectorToSparseDoubleVector(grb_var_values, variables_map_,
1278 model_parameters.variable_values_filter());
1279 const bool primal_feasible_solution_exists =
1281 return SolutionAndClaim<PrimalSolutionProto>{
1282 .solution = std::move(primal_solution),
1283 .feasible_solution_exists = primal_feasible_solution_exists};
1286bool GurobiSolver::PrimalSolutionQualityAvailable()
const {
1295absl::StatusOr<double> GurobiSolver::GetPrimalSolutionQuality()
const {
1308 return std::max({constraint_residual, constraint_violation, bound_violation,
1309 constraint_scaled_residual, constraint_scaled_violation,
1310 bound_scaled_violation});
1313absl::StatusOr<double> GurobiSolver::GetBestPrimalBound(
1314 absl::Span<const SolutionProto> solutions)
const {
1321 double best_objective_value = is_maximize ? -
kInf :
kInf;
1322 for (
const SolutionProto&
solution : solutions) {
1323 if (
solution.has_primal_solution() &&
1324 solution.primal_solution().feasibility_status() ==
1325 SOLUTION_STATUS_FEASIBLE) {
1326 const double sol_val =
solution.primal_solution().objective_value();
1327 best_objective_value = is_maximize
1328 ? std::max(best_objective_value, sol_val)
1329 :
std::
min(best_objective_value, sol_val);
1332 return best_objective_value;
1335absl::StatusOr<double> GurobiSolver::GetBestDualBound(
1336 const std::vector<SolutionProto>& solutions)
const {
1342 for (
const SolutionProto&
solution : solutions) {
1343 if (
solution.has_dual_solution() &&
1344 solution.dual_solution().feasibility_status() ==
1345 SOLUTION_STATUS_FEASIBLE &&
1346 solution.dual_solution().has_objective_value()) {
1347 const double sol_val =
solution.dual_solution().objective_value();
1348 best_dual_bound = is_maximize ? std::min(best_dual_bound, sol_val)
1349 :
std::
max(best_dual_bound, sol_val);
1352 return best_dual_bound;
1355absl::StatusOr<double> GurobiSolver::GetGurobiBestDualBound()
const {
1360 !is_multi_objective_mode()) {
1373absl::StatusOr<std::optional<BasisProto>> GurobiSolver::GetBasisIfAvailable() {
1379 basis.set_basic_dual_feasibility(SOLUTION_STATUS_UNDETERMINED);
1381 basis.set_basic_dual_feasibility(SOLUTION_STATUS_FEASIBLE);
1383 basis.set_basic_dual_feasibility(SOLUTION_STATUS_INFEASIBLE);
1386 return std::move(basis);
1388 return std::nullopt;
1391absl::StatusOr<GurobiSolver::SolutionsAndClaims> GurobiSolver::GetLpSolution(
1392 const ModelSolveParametersProto& model_parameters) {
1394 GetConvexPrimalSolutionIfAvailable(model_parameters));
1396 GetLpDualSolutionIfAvailable(model_parameters));
1398 const SolutionClaims solution_claims = {
1399 .primal_feasible_solution_exists =
1400 primal_solution_and_claim.feasible_solution_exists,
1401 .dual_feasible_solution_exists =
1402 dual_solution_and_claim.feasible_solution_exists};
1404 if (!primal_solution_and_claim.solution.has_value() &&
1405 !dual_solution_and_claim.solution.has_value() && !basis.has_value()) {
1406 return SolutionsAndClaims{.solution_claims = solution_claims};
1408 SolutionsAndClaims solution_and_claims{.solution_claims = solution_claims};
1410 solution_and_claims.solutions.emplace_back(SolutionProto());
1411 if (primal_solution_and_claim.solution.has_value()) {
1412 *
solution.mutable_primal_solution() =
1413 std::move(*primal_solution_and_claim.solution);
1415 if (dual_solution_and_claim.solution.has_value()) {
1416 *
solution.mutable_dual_solution() =
1417 std::move(*dual_solution_and_claim.solution);
1419 if (basis.has_value()) {
1420 *
solution.mutable_basis() = std::move(*basis);
1422 return solution_and_claims;
1425absl::StatusOr<GurobiSolver::SolutionAndClaim<DualSolutionProto>>
1426GurobiSolver::GetLpDualSolutionIfAvailable(
1427 const ModelSolveParametersProto& model_parameters) {
1430 return SolutionAndClaim<DualSolutionProto>{
1431 .solution = std::nullopt, .feasible_solution_exists =
false};
1436 DualSolutionProto dual_solution;
1437 bool dual_feasible_solution_exists =
false;
1439 const std::vector<double> grb_constraint_duals,
1441 GurobiVectorToSparseDoubleVector(grb_constraint_duals,
1442 linear_constraints_map_,
1443 *dual_solution.mutable_dual_values(),
1444 model_parameters.dual_values_filter());
1447 const std::vector<double> grb_reduced_cost_values,
1449 GurobiVectorToSparseDoubleVector(grb_reduced_cost_values, variables_map_,
1450 *dual_solution.mutable_reduced_costs(),
1451 model_parameters.reduced_costs_filter());
1459 dual_solution.set_objective_value(obj_val);
1462 dual_solution.set_feasibility_status(SOLUTION_STATUS_UNDETERMINED);
1464 dual_solution.set_feasibility_status(SOLUTION_STATUS_FEASIBLE);
1465 dual_feasible_solution_exists =
true;
1467 dual_solution.set_feasibility_status(SOLUTION_STATUS_INFEASIBLE);
1483 if (dual_feasible_solution_exists || std::isfinite(best_dual_bound)) {
1484 dual_feasible_solution_exists =
true;
1486 return absl::InternalError(
1487 "GRB_INT_ATTR_STATUS == GRB_OPTIMAL, but GRB_DBL_ATTR_OBJBOUND is "
1488 "unavailable or infinite, and no dual feasible solution is returned");
1490 return SolutionAndClaim<DualSolutionProto>{
1491 .solution = std::move(dual_solution),
1492 .feasible_solution_exists = dual_feasible_solution_exists};
1495absl::Status GurobiSolver::FillRays(
1496 const ModelSolveParametersProto& model_parameters,
1497 const SolutionClaims solution_claims, SolveResultProto& result) {
1502 if (!solution_claims.dual_feasible_solution_exists &&
1503 num_gurobi_variables_ > 0 &&
1507 num_gurobi_variables_));
1508 PrimalRayProto*
const primal_ray = result.add_primal_rays();
1509 GurobiVectorToSparseDoubleVector(grb_ray_var_values, variables_map_,
1510 *primal_ray->mutable_variable_values(),
1511 model_parameters.variable_values_filter());
1516 if (!solution_claims.primal_feasible_solution_exists &&
1517 num_gurobi_lin_cons_ > 0 &&
1520 DualRayProto dual_ray,
1521 GetGurobiDualRay(model_parameters.dual_values_filter(),
1522 model_parameters.reduced_costs_filter(), is_maximize));
1523 result.mutable_dual_rays()->Add(std::move(dual_ray));
1525 return absl::OkStatus();
1528absl::StatusOr<GurobiSolver::SolutionsAndClaims> GurobiSolver::GetQpSolution(
1529 const ModelSolveParametersProto& model_parameters) {
1531 GetConvexPrimalSolutionIfAvailable(model_parameters));
1535 GetLpDualSolutionIfAvailable(model_parameters));
1539 const SolutionClaims solution_claims = {
1540 .primal_feasible_solution_exists = found_primal_feasible_solution,
1541 .dual_feasible_solution_exists = found_dual_feasible_solution};
1544 return GurobiSolver::SolutionsAndClaims{.solution_claims = solution_claims};
1546 SolutionsAndClaims solution_and_claims{.solution_claims = solution_claims};
1548 solution_and_claims.solutions.emplace_back(SolutionProto());
1550 *
solution.mutable_primal_solution() = *std::move(primal_solution);
1552 if (dual_solution.has_value()) {
1553 *
solution.mutable_dual_solution() = *std::move(dual_solution);
1555 return solution_and_claims;
1558absl::StatusOr<GurobiSolver::SolutionsAndClaims> GurobiSolver::GetQcpSolution(
1559 const ModelSolveParametersProto& model_parameters) {
1561 GetConvexPrimalSolutionIfAvailable(model_parameters));
1565 GetLpDualSolutionIfAvailable(model_parameters));
1570 const bool proven_feasible = grb_termination ==
GRB_OPTIMAL;
1571 const SolutionClaims solution_claims = {
1572 .primal_feasible_solution_exists = found_primal_feasible_solution,
1573 .dual_feasible_solution_exists =
1574 found_dual_feasible_solution || proven_feasible};
1576 SolutionsAndClaims solution_and_claims{.solution_claims = solution_claims};
1578 *solution_and_claims.solutions.emplace_back().mutable_primal_solution() =
1579 *std::move(primal_solution);
1581 return solution_and_claims;
1584absl::Status GurobiSolver::SetParameters(
1589 std::vector<std::string> parameter_errors;
1590 for (
const GurobiParametersProto::Parameter& parameter :
1592 absl::Status param_status =
1593 gurobi_->SetParam(parameter.name().c_str(), parameter.value());
1594 if (!param_status.ok()) {
1595 parameter_errors.emplace_back(std::move(param_status).
message());
1598 if (!parameter_errors.empty()) {
1599 return absl::InvalidArgumentError(absl::StrJoin(parameter_errors,
"; "));
1601 return absl::OkStatus();
1604absl::Status GurobiSolver::AddNewVariables(
1605 const VariablesProto& new_variables) {
1606 const int num_new_variables = new_variables.lower_bounds().size();
1607 std::vector<char> variable_type(num_new_variables);
1608 for (
int j = 0; j < num_new_variables; ++j) {
1609 const VariableId
id = new_variables.ids(j);
1615 const std::vector<std::string> variable_names =
1616 TruncateNames(new_variables.names());
1619 new_variables.lower_bounds(),
1620 new_variables.upper_bounds(),
1621 variable_type, variable_names));
1622 num_gurobi_variables_ += num_new_variables;
1624 return absl::OkStatus();
1627absl::Status GurobiSolver::AddSingleObjective(
const ObjectiveProto& objective) {
1632 RETURN_IF_ERROR(UpdateDoubleListAttribute(objective.linear_coefficients(),
1635 ResetQuadraticObjectiveTerms(objective.quadratic_coefficients()));
1636 return absl::OkStatus();
1639absl::Status GurobiSolver::AddMultiObjectives(
1640 const ObjectiveProto& primary_objective,
1641 const google::protobuf::Map<int64_t, ObjectiveProto>&
1642 auxiliary_objectives) {
1643 absl::flat_hash_set<int64_t> priorities = {primary_objective.priority()};
1644 for (
const auto& [
id, objective] : auxiliary_objectives) {
1645 const int64_t priority = objective.priority();
1646 if (!priorities.insert(priority).second) {
1648 <<
"repeated objective priority: " << priority;
1651 const bool is_maximize = primary_objective.maximize();
1655 primary_objective, std::nullopt, is_maximize));
1656 for (
const int64_t
id :
SortedMapKeys(auxiliary_objectives)) {
1658 AddNewMultiObjective(auxiliary_objectives.at(
id),
id, is_maximize));
1660 return absl::OkStatus();
1663absl::Status GurobiSolver::AddNewMultiObjective(
1664 const ObjectiveProto& objective,
1665 const std::optional<AuxiliaryObjectiveId> objective_id,
1666 const bool is_maximize) {
1668 var_indices.reserve(objective.linear_coefficients().ids_size());
1669 for (
const int64_t var_id : objective.linear_coefficients().ids()) {
1672 const GurobiMultiObjectiveIndex grb_index =
1673 static_cast<int>(multi_objectives_map_.size());
1683 grb_index,
static_cast<int>(-objective.priority()),
1684 objective.maximize() == is_maximize ? +1.0 : -1.0,
1686 0.0, objective.
name(),
1688 objective.linear_coefficients().values()));
1689 multi_objectives_map_.insert({objective_id, grb_index});
1690 return absl::OkStatus();
1696absl::Status GurobiSolver::AddNewSlacks(
1697 const std::vector<LinearConstraintData*>& new_slacks) {
1704 const int num_slacks = new_slacks.size();
1705 if (num_slacks == 0) {
1706 return absl::OkStatus();
1709 const std::vector<double> column_non_zeros(num_slacks, -1.0);
1713 std::vector<GurobiLinearConstraintIndex> row_indices;
1714 std::vector<int> column_non_zero_begin;
1715 column_non_zero_begin.reserve(num_slacks);
1716 row_indices.reserve(num_slacks);
1719 for (
int k = 0; k < num_slacks; ++k) {
1720 CHECK_NE(new_slacks[k],
nullptr);
1721 const LinearConstraintData& constraint_data = *new_slacks[k];
1722 row_indices.push_back(constraint_data.constraint_index);
1725 column_non_zero_begin.push_back(k);
1730 column_non_zeros, {},
1733 num_gurobi_variables_ += num_slacks;
1734 return absl::OkStatus();
1737absl::Status GurobiSolver::AddNewLinearConstraints(
1738 const LinearConstraintsProto& constraints) {
1739 const int num_new_constraints = constraints.lower_bounds().size();
1743 const std::vector<std::string> constraint_names =
1744 TruncateNames(constraints.names());
1754 std::vector<double> constraint_rhs;
1755 std::vector<char> constraint_sense;
1756 std::vector<LinearConstraintData*> new_slacks;
1757 constraint_rhs.reserve(num_new_constraints);
1758 constraint_sense.reserve(num_new_constraints);
1759 new_slacks.reserve(num_new_constraints);
1760 for (
int i = 0;
i < num_new_constraints; ++
i) {
1761 const int64_t
id = constraints.ids(i);
1762 LinearConstraintData& constraint_data =
1764 const double lb = constraints.lower_bounds(i);
1765 const double ub = constraints.upper_bounds(i);
1767 <<
"lower bound for linear constraint " <<
id <<
": "
1768 << EscapedNameForLogging(
1769 constraints.names().empty() ?
"" : constraints.names(
i));
1771 <<
"upper bound for linear constraint " <<
id <<
": "
1772 << EscapedNameForLogging(
1773 constraints.names().empty() ?
"" : constraints.names(
i));
1774 constraint_data.lower_bound = lb;
1775 constraint_data.upper_bound = ub;
1776 constraint_data.constraint_index =
i + num_gurobi_lin_cons_;
1781 if (lb_is_grb_neg_inf && !ub_is_grb_pos_inf) {
1784 }
else if (!lb_is_grb_neg_inf && ub_is_grb_pos_inf) {
1787 }
else if (lb == ub) {
1793 constraint_data.slack_index = new_slacks.size() + num_gurobi_variables_;
1794 new_slacks.push_back(&constraint_data);
1796 constraint_rhs.emplace_back(rhs);
1797 constraint_sense.emplace_back(sense);
1801 gurobi_->AddConstrs(constraint_sense, constraint_rhs, constraint_names));
1802 num_gurobi_lin_cons_ += num_new_constraints;
1804 if (!new_slacks.empty()) {
1807 return absl::OkStatus();
1810absl::Status GurobiSolver::AddNewQuadraticConstraints(
1811 const google::protobuf::Map<QuadraticConstraintId,
1812 QuadraticConstraintProto>& constraints) {
1822 for (
const auto& [
id, constraint] : constraints) {
1825 const double lb = constraint.lower_bound();
1826 const double ub = constraint.upper_bound();
1828 <<
"lower bound for quadratic constraint " <<
id <<
": "
1829 << EscapedNameForLogging(constraint.name());
1831 <<
"upper bound for quadratic constraint " <<
id <<
": "
1832 << EscapedNameForLogging(constraint.name());
1835 if (lb_is_grb_neg_inf && ub_is_grb_pos_inf) {
1839 }
else if (lb_is_grb_neg_inf && !ub_is_grb_pos_inf) {
1842 }
else if (!lb_is_grb_neg_inf && ub_is_grb_pos_inf) {
1845 }
else if (lb == ub) {
1851 return absl::UnimplementedError(
1852 "ranged quadratic constraints are not currently supported in Gurobi "
1855 const SparseDoubleVectorProto& linear_coeffs = constraint.linear_terms();
1856 const int num_linear_coeffs = linear_coeffs.ids_size();
1857 std::vector<GurobiVariableIndex> linear_col_index(num_linear_coeffs);
1858 for (
int k = 0; k < num_linear_coeffs; ++k) {
1859 linear_col_index[k] = variables_map_.at(linear_coeffs.ids(k));
1861 const SparseDoubleMatrixProto& quad_coeffs = constraint.quadratic_terms();
1862 const int num_quad_coeffs = quad_coeffs.row_ids_size();
1863 std::vector<GurobiVariableIndex> quad_row_index(num_quad_coeffs);
1864 std::vector<GurobiVariableIndex> quad_col_index(num_quad_coeffs);
1865 for (
int k = 0; k < num_quad_coeffs; ++k) {
1866 quad_row_index[k] = variables_map_.at(quad_coeffs.row_ids(k));
1867 quad_col_index[k] = variables_map_.at(quad_coeffs.column_ids(k));
1870 linear_col_index, linear_coeffs.values(), quad_row_index,
1871 quad_col_index, quad_coeffs.coefficients(), sense, rhs,
1872 TruncateName(constraint.name())));
1874 ++num_gurobi_quad_cons_;
1876 return absl::OkStatus();
1879std::optional<GurobiSolver::VariableId> GurobiSolver::TryExtractVariable(
1880 const LinearExpressionProto& expression) {
1881 if (expression.offset() == 0 && expression.ids_size() == 1 &&
1882 expression.coefficients(0) == 1) {
1883 return expression.ids(0);
1885 return std::nullopt;
1888absl::StatusOr<GurobiSolver::VariableEqualToExpression>
1889GurobiSolver::CreateSlackVariableEqualToExpression(
1890 const LinearExpressionProto& expression) {
1891 const GurobiVariableIndex slack_variable = num_gurobi_variables_;
1892 std::vector<GurobiVariableIndex> slack_col_indices = {slack_variable};
1893 std::vector<double> slack_coeffs = {-1.0};
1894 for (
int j = 0; j < expression.ids_size(); ++j) {
1895 slack_col_indices.push_back(variables_map_.at(expression.ids(j)));
1896 slack_coeffs.push_back(expression.coefficients(j));
1900 -expression.offset(),
""));
1901 return VariableEqualToExpression{.variable_index = num_gurobi_variables_++,
1902 .constraint_index = num_gurobi_lin_cons_++};
1905absl::Status GurobiSolver::AddNewSecondOrderConeConstraints(
1906 const google::protobuf::Map<SecondOrderConeConstraintId,
1907 SecondOrderConeConstraintProto>& constraints) {
1908 for (
const auto& [
id, constraint] : constraints) {
1921 SecondOrderConeConstraintData& constraint_data =
1923 constraint_data.constraint_index = num_gurobi_quad_cons_;
1928 (
const auto [ub_var, ub_cons]),
1929 CreateSlackVariableEqualToExpression(constraint.upper_bound()));
1932 constraint_data.slack_variables.push_back(ub_var);
1933 constraint_data.slack_constraints.push_back(ub_cons);
1934 std::vector<GurobiVariableIndex> quad_var_indices = {ub_var};
1935 std::vector<double> quad_coeffs = {-1.0};
1936 for (
const LinearExpressionProto& expression :
1937 constraint.arguments_to_norm()) {
1938 quad_coeffs.push_back(1.0);
1939 if (
const std::optional<VariableId> maybe_variable =
1940 TryExtractVariable(expression);
1941 maybe_variable.has_value()) {
1942 quad_var_indices.push_back(variables_map_.at(*maybe_variable));
1946 CreateSlackVariableEqualToExpression(expression));
1947 quad_var_indices.push_back(arg_var);
1948 constraint_data.slack_variables.push_back(arg_var);
1949 constraint_data.slack_constraints.push_back(arg_cons);
1952 quad_var_indices, quad_coeffs,
1954 ++num_gurobi_quad_cons_;
1956 return absl::OkStatus();
1959absl::Status GurobiSolver::AddNewSosConstraints(
1960 const google::protobuf::Map<AnyConstraintId, SosConstraintProto>&
1963 absl::flat_hash_map<int64_t, SosConstraintData>& constraints_map) {
1964 for (
const auto& [
id, constraint] : constraints) {
1965 SosConstraintData& constraint_data =
1967 constraint_data.constraint_index = num_gurobi_sos_cons_;
1968 std::vector<GurobiVariableIndex> sos_var_indices;
1969 std::vector<double> weights;
1975 absl::flat_hash_set<VariableId> reused_variables;
1976 for (
int i = 0;
i < constraint.expressions_size(); ++
i) {
1977 weights.push_back(constraint.weights().empty() ? i + 1
1978 : constraint.weights(
i));
1979 if (
const std::optional<VariableId> maybe_variable =
1980 TryExtractVariable(constraint.expressions(i));
1981 maybe_variable.has_value() &&
1982 !reused_variables.contains(*maybe_variable)) {
1983 sos_var_indices.push_back(variables_map_.at(*maybe_variable));
1984 reused_variables.insert(*maybe_variable);
1985 if (sos_type == 2) {
1989 undeletable_variables_.insert(*maybe_variable);
1995 CreateSlackVariableEqualToExpression(constraint.expressions(i)));
1997 constraint_data.slack_variables.push_back(
var_index);
1998 constraint_data.slack_constraints.push_back(cons_index);
2000 RETURN_IF_ERROR(gurobi_->AddSos({sos_type}, {0}, sos_var_indices, weights));
2001 ++num_gurobi_sos_cons_;
2003 return absl::OkStatus();
2006absl::Status GurobiSolver::AddNewIndicatorConstraints(
2007 const google::protobuf::Map<IndicatorConstraintId,
2008 IndicatorConstraintProto>& constraints) {
2009 for (
const auto& [
id, constraint] : constraints) {
2010 if (!constraint.has_indicator_id()) {
2011 if (constraint.activate_on_zero()) {
2013 <<
"MathOpt does not currently support Gurobi models with "
2014 "indicator constraints that activate on zero with unset "
2015 "indicator variables; encountered one at id: "
2021 const int num_terms = constraint.expression().ids_size();
2022 std::vector<GurobiVariableIndex> grb_ids(num_terms);
2023 for (
int k = 0; k < num_terms; ++k) {
2024 grb_ids[k] = variables_map_.at(constraint.expression().ids(k));
2028 const double lb = constraint.lower_bound();
2029 const double ub = constraint.upper_bound();
2031 <<
"lower bound for indicator constraint " <<
id <<
": "
2032 << EscapedNameForLogging(constraint.name());
2034 <<
"upper bound for indicator constraint " <<
id <<
": "
2035 << EscapedNameForLogging(constraint.name());
2038 if (lb_is_grb_neg_inf && ub_is_grb_pos_inf) {
2041 }
else if (lb_is_grb_neg_inf && !ub_is_grb_pos_inf) {
2044 }
else if (!lb_is_grb_neg_inf && ub_is_grb_pos_inf) {
2047 }
else if (lb == ub) {
2053 return absl::UnimplementedError(
2054 "ranged indicator constraints are not currently supported in "
2060 variables_map_.at(constraint.indicator_id()),
2061 constraint.activate_on_zero() ? 0 : 1,
2062 grb_ids, constraint.expression().values(),
2065 IndicatorConstraintData{
2066 .constraint_index = num_gurobi_gen_cons_,
2067 .indicator_variable_id = constraint.indicator_id()});
2068 ++num_gurobi_gen_cons_;
2071 undeletable_variables_.insert(constraint.indicator_id());
2073 return absl::OkStatus();
2076absl::Status GurobiSolver::ChangeCoefficients(
2077 const SparseDoubleMatrixProto& matrix) {
2078 const int num_coefficients = matrix.row_ids().size();
2079 std::vector<GurobiLinearConstraintIndex> row_index(num_coefficients);
2080 std::vector<GurobiVariableIndex> col_index(num_coefficients);
2081 for (
int k = 0; k < num_coefficients; ++k) {
2083 linear_constraints_map_.at(matrix.row_ids(k)).constraint_index;
2084 col_index[k] = variables_map_.at(matrix.column_ids(k));
2086 return gurobi_->ChgCoeffs(row_index, col_index, matrix.coefficients());
2089absl::Status GurobiSolver::UpdateDoubleListAttribute(
2090 const SparseDoubleVectorProto& update,
const char* attribute_name,
2091 const IdHashMap& id_hash_map) {
2092 if (update.ids_size() == 0) {
2093 return absl::OkStatus();
2095 std::vector<int>
index;
2096 index.reserve(update.ids_size());
2097 for (
const int64_t
id : update.ids()) {
2098 index.push_back(id_hash_map.at(
id));
2100 return gurobi_->SetDoubleAttrList(attribute_name,
index, update.values());
2103absl::Status GurobiSolver::UpdateInt32ListAttribute(
2104 const SparseInt32VectorProto& update,
const char* attribute_name,
2105 const IdHashMap& id_hash_map) {
2106 if (update.ids_size() == 0) {
2107 return absl::OkStatus();
2109 std::vector<int>
index;
2110 index.reserve(update.ids_size());
2111 for (
const int64_t
id : update.ids()) {
2112 index.push_back(id_hash_map.at(
id));
2114 return gurobi_->SetIntAttrList(attribute_name,
index, update.values());
2117absl::Status GurobiSolver::LoadModel(
const ModelProto& input_model) {
2118 CHECK(gurobi_ !=
nullptr);
2120 TruncateName(input_model.name())));
2123 RETURN_IF_ERROR(AddNewLinearConstraints(input_model.linear_constraints()));
2125 AddNewQuadraticConstraints(input_model.quadratic_constraints()));
2127 input_model.second_order_cone_constraints()));
2133 AddNewIndicatorConstraints(input_model.indicator_constraints()));
2135 RETURN_IF_ERROR(ChangeCoefficients(input_model.linear_constraint_matrix()));
2137 if (input_model.auxiliary_objectives().empty()) {
2141 input_model.auxiliary_objectives()));
2143 return absl::OkStatus();
2146absl::Status GurobiSolver::ResetQuadraticObjectiveTerms(
2147 const SparseDoubleMatrixProto& terms) {
2148 quadratic_objective_coefficients_.clear();
2150 const int num_terms = terms.row_ids().size();
2151 if (num_terms > 0) {
2152 std::vector<GurobiVariableIndex> first_var_index(num_terms);
2153 std::vector<GurobiVariableIndex> second_var_index(num_terms);
2154 for (
int k = 0; k < num_terms; ++k) {
2155 const VariableId row_id = terms.row_ids(k);
2156 const VariableId column_id = terms.column_ids(k);
2157 first_var_index[k] = variables_map_.at(row_id);
2158 second_var_index[k] = variables_map_.at(column_id);
2159 quadratic_objective_coefficients_[{row_id, column_id}] =
2160 terms.coefficients(k);
2162 RETURN_IF_ERROR(gurobi_->AddQpTerms(first_var_index, second_var_index,
2163 terms.coefficients()));
2165 return absl::OkStatus();
2168absl::Status GurobiSolver::UpdateQuadraticObjectiveTerms(
2169 const SparseDoubleMatrixProto& terms) {
2170 CHECK(gurobi_ !=
nullptr);
2171 const int num_terms = terms.row_ids().size();
2172 if (num_terms > 0) {
2173 std::vector<GurobiVariableIndex> first_var_index(num_terms);
2174 std::vector<GurobiVariableIndex> second_var_index(num_terms);
2175 std::vector<double> coefficient_updates(num_terms);
2176 for (
int k = 0; k < num_terms; ++k) {
2177 const VariableId row_id = terms.row_ids(k);
2178 const VariableId column_id = terms.column_ids(k);
2179 first_var_index[k] = variables_map_.at(row_id);
2180 second_var_index[k] = variables_map_.at(column_id);
2181 const std::pair<VariableId, VariableId> qp_term_key(row_id, column_id);
2182 const double new_coefficient = terms.coefficients(k);
2187 coefficient_updates[k] =
2188 new_coefficient - quadratic_objective_coefficients_[qp_term_key];
2189 quadratic_objective_coefficients_[qp_term_key] = new_coefficient;
2191 RETURN_IF_ERROR(gurobi_->AddQpTerms(first_var_index, second_var_index,
2192 coefficient_updates));
2194 return absl::OkStatus();
2200absl::Status GurobiSolver::UpdateLinearConstraints(
2201 const LinearConstraintUpdatesProto& constraints_update,
2202 std::vector<GurobiVariableIndex>& deleted_variables_index) {
2203 const SparseDoubleVectorProto& constraint_lower_bounds =
2204 constraints_update.lower_bounds();
2205 const SparseDoubleVectorProto& constraint_upper_bounds =
2206 constraints_update.upper_bounds();
2209 if (constraint_lower_bounds.ids().empty() &&
2210 constraint_upper_bounds.ids().empty()) {
2211 return absl::OkStatus();
2218 struct UpdateConstraintData {
2219 LinearConstraintId constraint_id;
2220 LinearConstraintData& source;
2221 double new_lower_bound;
2222 double new_upper_bound;
2223 UpdateConstraintData(
const LinearConstraintId
id,
2224 LinearConstraintData& reference)
2225 : constraint_id(id),
2230 const int upper_bounds_size = constraint_upper_bounds.ids().size();
2231 const int lower_bounds_size = constraint_lower_bounds.ids().size();
2232 std::vector<UpdateConstraintData> update_vector;
2233 update_vector.reserve(upper_bounds_size + lower_bounds_size);
2236 for (
int lower_index = 0, upper_index = 0;
2237 lower_index < lower_bounds_size || upper_index < upper_bounds_size;) {
2238 VariableId lower_id = std::numeric_limits<int64_t>::max();
2239 if (lower_index < lower_bounds_size) {
2240 lower_id = constraint_lower_bounds.ids(lower_index);
2242 VariableId upper_id = std::numeric_limits<int64_t>::max();
2243 if (upper_index < upper_bounds_size) {
2244 upper_id = constraint_upper_bounds.ids(upper_index);
2246 const VariableId
id = std::min(lower_id, upper_id);
2247 DCHECK(
id < std::numeric_limits<int64_t>::max());
2248 UpdateConstraintData update(
id, linear_constraints_map_.at(
id));
2249 if (lower_id == upper_id) {
2250 update.new_lower_bound = constraint_lower_bounds.values(lower_index++);
2251 update.new_upper_bound = constraint_upper_bounds.values(upper_index++);
2252 }
else if (lower_id < upper_id) {
2253 update.new_lower_bound = constraint_lower_bounds.values(lower_index++);
2255 update.new_upper_bound = constraint_upper_bounds.values(upper_index++);
2257 update_vector.emplace_back(update);
2264 std::vector<char> sense_data;
2265 std::vector<double> rhs_data;
2266 std::vector<GurobiLinearConstraintIndex> rhs_index;
2268 std::vector<double> lower_bound_data;
2269 std::vector<double> upper_bound_data;
2270 std::vector<GurobiVariableIndex> bound_index;
2272 std::vector<LinearConstraintData*> new_slacks;
2274 for (UpdateConstraintData& update_data : update_vector) {
2275 const bool same_lower_bound =
2276 (update_data.source.lower_bound == update_data.new_lower_bound) ||
2279 const bool same_upper_bound =
2280 (update_data.source.upper_bound == update_data.new_upper_bound) ||
2283 if (same_upper_bound && same_lower_bound)
continue;
2286 update_data.source.lower_bound = update_data.new_lower_bound;
2287 update_data.source.upper_bound = update_data.new_upper_bound;
2288 bool delete_slack =
false;
2292 delete_slack =
true;
2293 rhs_index.emplace_back(update_data.source.constraint_index);
2294 rhs_data.emplace_back(update_data.new_upper_bound);
2296 }
else if (update_data.new_lower_bound > -
GRB_INFINITY &&
2298 delete_slack =
true;
2299 rhs_index.emplace_back(update_data.source.constraint_index);
2300 rhs_data.emplace_back(update_data.new_lower_bound);
2302 }
else if (update_data.new_lower_bound == update_data.new_upper_bound) {
2303 delete_slack =
true;
2304 rhs_index.emplace_back(update_data.source.constraint_index);
2305 rhs_data.emplace_back(update_data.new_lower_bound);
2311 if (update_data.source.slack_index != kUnspecifiedIndex) {
2312 bound_index.emplace_back(update_data.source.slack_index);
2313 lower_bound_data.emplace_back(update_data.new_lower_bound);
2314 upper_bound_data.emplace_back(update_data.new_upper_bound);
2318 rhs_index.emplace_back(update_data.source.constraint_index);
2319 rhs_data.emplace_back(0.0);
2322 update_data.source.slack_index =
2323 new_slacks.size() + num_gurobi_variables_;
2325 new_slacks.push_back(&update_data.source);
2332 if (delete_slack && update_data.source.slack_index != kUnspecifiedIndex) {
2333 deleted_variables_index.emplace_back(update_data.source.slack_index);
2334 update_data.source.slack_index = kUnspecifiedIndex;
2339 if (!rhs_index.empty()) {
2345 if (!bound_index.empty()) {
2352 if (!new_slacks.empty()) {
2355 return absl::OkStatus();
2363void GurobiSolver::UpdateGurobiIndices(
const DeletedIndices& deleted_indices) {
2365 if (!deleted_indices.variables.empty()) {
2366 const std::vector<GurobiVariableIndex> old_to_new =
2367 IndexUpdateMap(num_gurobi_variables_, deleted_indices.variables);
2368 for (
auto& [_, grb_index] : variables_map_) {
2369 grb_index = old_to_new[grb_index];
2370 CHECK_NE(grb_index, kDeletedIndex);
2372 for (
auto& [_, lin_con_data] : linear_constraints_map_) {
2373 if (lin_con_data.slack_index != kUnspecifiedIndex) {
2374 lin_con_data.slack_index = old_to_new[lin_con_data.slack_index];
2375 CHECK_NE(lin_con_data.slack_index, kDeletedIndex);
2378 for (
auto& [_, soc_con_data] : soc_constraints_map_) {
2379 for (GurobiVariableIndex&
index : soc_con_data.slack_variables) {
2381 CHECK_NE(
index, kDeletedIndex);
2384 for (
auto& [_, sos1_con_data] : sos1_constraints_map_) {
2385 for (GurobiVariableIndex&
index : sos1_con_data.slack_variables) {
2387 CHECK_NE(
index, kDeletedIndex);
2390 for (
auto& [_, sos2_con_data] : sos2_constraints_map_) {
2391 for (GurobiVariableIndex&
index : sos2_con_data.slack_variables) {
2393 CHECK_NE(
index, kDeletedIndex);
2398 if (!deleted_indices.linear_constraints.empty()) {
2399 const std::vector<GurobiLinearConstraintIndex> old_to_new = IndexUpdateMap(
2400 num_gurobi_lin_cons_, deleted_indices.linear_constraints);
2401 for (
auto& [_, lin_con_data] : linear_constraints_map_) {
2402 lin_con_data.constraint_index = old_to_new[lin_con_data.constraint_index];
2403 CHECK_NE(lin_con_data.constraint_index, kDeletedIndex);
2405 for (
auto& [_, soc_con_data] : soc_constraints_map_) {
2406 for (GurobiLinearConstraintIndex&
index :
2407 soc_con_data.slack_constraints) {
2409 CHECK_NE(
index, kDeletedIndex);
2412 for (
auto& [_, sos1_con_data] : sos1_constraints_map_) {
2413 for (GurobiLinearConstraintIndex&
index :
2414 sos1_con_data.slack_constraints) {
2416 CHECK_NE(
index, kDeletedIndex);
2419 for (
auto& [_, sos2_con_data] : sos2_constraints_map_) {
2420 for (GurobiLinearConstraintIndex&
index :
2421 sos2_con_data.slack_constraints) {
2423 CHECK_NE(
index, kDeletedIndex);
2428 if (!deleted_indices.quadratic_constraints.empty()) {
2429 const std::vector<GurobiQuadraticConstraintIndex> old_to_new =
2430 IndexUpdateMap(num_gurobi_quad_cons_,
2431 deleted_indices.quadratic_constraints);
2432 for (
auto& [_, grb_index] : quadratic_constraints_map_) {
2433 grb_index = old_to_new[grb_index];
2434 CHECK_NE(grb_index, kDeletedIndex);
2436 for (
auto& [_, soc_con_data] : soc_constraints_map_) {
2437 GurobiQuadraticConstraintIndex& grb_index = soc_con_data.constraint_index;
2438 grb_index = old_to_new[soc_con_data.constraint_index];
2439 CHECK_NE(grb_index, kDeletedIndex);
2443 if (!deleted_indices.sos_constraints.empty()) {
2444 const std::vector<GurobiSosConstraintIndex> old_to_new =
2445 IndexUpdateMap(num_gurobi_sos_cons_, deleted_indices.sos_constraints);
2446 for (
auto& [_, sos1_data] : sos1_constraints_map_) {
2447 GurobiSosConstraintIndex& grb_index = sos1_data.constraint_index;
2448 grb_index = old_to_new[grb_index];
2449 CHECK_NE(grb_index, kDeletedIndex);
2451 for (
auto& [_, sos2_data] : sos2_constraints_map_) {
2452 GurobiSosConstraintIndex& grb_index = sos2_data.constraint_index;
2453 grb_index = old_to_new[grb_index];
2454 CHECK_NE(grb_index, kDeletedIndex);
2458 if (!deleted_indices.general_constraints.empty()) {
2459 const std::vector<GurobiGeneralConstraintIndex> old_to_new = IndexUpdateMap(
2460 num_gurobi_gen_cons_, deleted_indices.general_constraints);
2461 for (
auto& [_, indicator_data] : indicator_constraints_map_) {
2462 if (!indicator_data.has_value()) {
2465 GurobiGeneralConstraintIndex& grb_index =
2466 indicator_data->constraint_index;
2467 grb_index = old_to_new[grb_index];
2468 CHECK_NE(grb_index, kDeletedIndex);
2473absl::StatusOr<bool> GurobiSolver::Update(
2474 const ModelUpdateProto& model_update) {
2475 if (!undeletable_variables_.empty()) {
2476 for (
const VariableId
id : model_update.deleted_variable_ids()) {
2477 if (undeletable_variables_.contains(
id)) {
2487 if (
const AuxiliaryObjectivesUpdatesProto& objs_update =
2488 model_update.auxiliary_objectives_updates();
2489 !objs_update.deleted_objective_ids().empty() ||
2490 !objs_update.new_objectives().empty() ||
2491 !objs_update.objective_updates().empty()) {
2495 if (is_multi_objective_mode() && model_update.has_objective_updates()) {
2502 AddNewLinearConstraints(model_update.new_linear_constraints()));
2505 model_update.quadratic_constraint_updates().new_constraints()));
2507 model_update.second_order_cone_constraint_updates().new_constraints()));
2509 model_update.sos1_constraint_updates().new_constraints(),
GRB_SOS_TYPE1,
2510 sos1_constraints_map_));
2512 model_update.sos2_constraint_updates().new_constraints(),
GRB_SOS_TYPE2,
2513 sos2_constraints_map_));
2515 model_update.indicator_constraint_updates().new_constraints()));
2518 ChangeCoefficients(model_update.linear_constraint_matrix_updates()));
2520 if (model_update.objective_updates().has_direction_update()) {
2521 const int model_sense = model_update.objective_updates().direction_update()
2527 if (model_update.objective_updates().has_offset_update()) {
2537 model_update.objective_updates().quadratic_coefficients()));
2540 UpdateDoubleListAttribute(model_update.variable_updates().lower_bounds(),
2544 UpdateDoubleListAttribute(model_update.variable_updates().upper_bounds(),
2547 if (model_update.variable_updates().has_integers()) {
2548 const SparseBoolVectorProto& update =
2549 model_update.variable_updates().integers();
2550 std::vector<GurobiVariableIndex>
index;
2551 index.reserve(update.ids_size());
2552 for (
const int64_t
id : update.ids()) {
2553 index.push_back(variables_map_.at(
id));
2555 std::vector<char>
value;
2556 value.reserve(update.values_size());
2557 for (
const bool val : update.values()) {
2566 const absl::flat_hash_set<VariableId> variable_ids_to_be_deleted(
2567 model_update.deleted_variable_ids().begin(),
2568 model_update.deleted_variable_ids().end());
2571 for (
auto it = quadratic_objective_coefficients_.cbegin();
2572 it != quadratic_objective_coefficients_.cend();
2574 if (variable_ids_to_be_deleted.contains(it->first.first) ||
2575 variable_ids_to_be_deleted.contains(it->first.second)) {
2576 quadratic_objective_coefficients_.erase(it++);
2583 DeletedIndices deleted_indices;
2586 model_update.linear_constraint_updates(), deleted_indices.variables));
2588 for (
const VariableId
id : model_update.deleted_variable_ids()) {
2589 deleted_indices.variables.emplace_back(variables_map_.at(
id));
2590 variables_map_.erase(
id);
2593 for (
const LinearConstraintId
id :
2594 model_update.deleted_linear_constraint_ids()) {
2595 LinearConstraintData& constraint_data = linear_constraints_map_.at(
id);
2596 deleted_indices.linear_constraints.push_back(
2597 constraint_data.constraint_index);
2598 if (constraint_data.slack_index != kUnspecifiedIndex) {
2599 deleted_indices.variables.push_back(constraint_data.slack_index);
2600 constraint_data.slack_index = kUnspecifiedIndex;
2602 linear_constraints_map_.erase(
id);
2605 for (
const QuadraticConstraintId
id :
2606 model_update.quadratic_constraint_updates().deleted_constraint_ids()) {
2607 const GurobiQuadraticConstraintIndex grb_index =
2608 quadratic_constraints_map_.at(
id);
2609 deleted_indices.quadratic_constraints.push_back(grb_index);
2610 quadratic_constraints_map_.erase(
id);
2613 for (
const SecondOrderConeConstraintId
id :
2614 model_update.second_order_cone_constraint_updates()
2615 .deleted_constraint_ids()) {
2616 deleted_indices.quadratic_constraints.push_back(
2617 soc_constraints_map_.at(
id).constraint_index);
2618 for (
const GurobiVariableIndex
index :
2619 soc_constraints_map_.at(
id).slack_variables) {
2620 deleted_indices.variables.push_back(
index);
2622 for (
const GurobiLinearConstraintIndex
index :
2623 soc_constraints_map_.at(
id).slack_constraints) {
2624 deleted_indices.linear_constraints.push_back(
index);
2626 soc_constraints_map_.erase(
id);
2629 const auto sos_updater = [&](
const SosConstraintData& sos_constraint) {
2630 deleted_indices.sos_constraints.push_back(sos_constraint.constraint_index);
2631 for (
const GurobiVariableIndex
index : sos_constraint.slack_variables) {
2632 deleted_indices.variables.push_back(
index);
2634 for (
const GurobiLinearConstraintIndex
index :
2635 sos_constraint.slack_constraints) {
2636 deleted_indices.linear_constraints.push_back(
index);
2639 for (
const Sos1ConstraintId
id :
2640 model_update.sos1_constraint_updates().deleted_constraint_ids()) {
2641 sos_updater(sos1_constraints_map_.at(
id));
2642 sos1_constraints_map_.erase(
id);
2645 for (
const Sos2ConstraintId
id :
2646 model_update.sos2_constraint_updates().deleted_constraint_ids()) {
2647 sos_updater(sos2_constraints_map_.at(
id));
2648 sos2_constraints_map_.erase(
id);
2651 for (
const IndicatorConstraintId
id :
2652 model_update.indicator_constraint_updates().deleted_constraint_ids()) {
2654 const auto it = indicator_constraints_map_.find(
id);
2655 CHECK(it != indicator_constraints_map_.end()) <<
"id: " << id;
2656 if (it->second.has_value()) {
2657 deleted_indices.general_constraints.push_back(
2658 it->second->constraint_index);
2660 indicator_constraints_map_.erase(it);
2663 UpdateGurobiIndices(deleted_indices);
2670 if (!deleted_indices.linear_constraints.empty()) {
2671 RETURN_IF_ERROR(gurobi_->DelConstrs(deleted_indices.linear_constraints));
2672 num_gurobi_lin_cons_ -= deleted_indices.linear_constraints.size();
2675 if (!deleted_indices.quadratic_constraints.empty()) {
2677 gurobi_->DelQConstrs(deleted_indices.quadratic_constraints));
2678 num_gurobi_quad_cons_ -= deleted_indices.quadratic_constraints.size();
2681 if (!deleted_indices.sos_constraints.empty()) {
2685 if (!deleted_indices.general_constraints.empty()) {
2687 gurobi_->DelGenConstrs(deleted_indices.general_constraints));
2690 if (!deleted_indices.variables.empty()) {
2692 num_gurobi_variables_ -= deleted_indices.variables.size();
2701absl::StatusOr<std::unique_ptr<GurobiSolver>> GurobiSolver::New(
2704 return absl::InvalidArgumentError(
"Gurobi is not correctly installed.");
2708 if (!input_model.auxiliary_objectives().empty() &&
2709 !input_model.objective().quadratic_coefficients().row_ids().empty()) {
2711 <<
"Gurobi does not support multiple objective models with "
2712 "quadratic objectives";
2714 for (
const auto& [
id, obj] : input_model.auxiliary_objectives()) {
2715 if (!obj.quadratic_coefficients().row_ids().empty()) {
2717 <<
"Gurobi does not support multiple objective models with "
2718 "quadratic objectives";
2722 GurobiFromInitArgs(init_args));
2725 return gurobi_solver;
2728absl::StatusOr<std::unique_ptr<GurobiSolver::GurobiCallbackData>>
2729GurobiSolver::RegisterCallback(
const CallbackRegistrationProto& registration,
2732 const absl::Time
start,
2734 const absl::flat_hash_set<CallbackEventProto> events =
EventSet(registration);
2745 registration, is_mip ? SupportedMIPEvents() : SupportedLPEvents()))
2746 <<
"for a " << (is_mip ?
"MIP" :
"LP") <<
" model";
2749 if (message_cb !=
nullptr) {
2754 if (registration.add_cuts() || registration.add_lazy_constraints()) {
2759 if (registration.add_lazy_constraints()) {
2764 return std::make_unique<GurobiCallbackData>(
2765 GurobiCallbackInput{
2767 .message_cb = message_cb,
2768 .variable_ids = variables_map_,
2769 .num_gurobi_vars = num_gurobi_variables_,
2771 .mip_solution_filter = registration.mip_solution_filter(),
2772 .mip_node_filter = registration.mip_node_filter(),
2777absl::StatusOr<InvertedBounds> GurobiSolver::ListInvertedBounds()
const {
2778 InvertedBounds inverted_bounds;
2781 const std::vector<double> var_lbs,
2784 const std::vector<double> var_ubs,
2786 for (
const auto& [
id,
index] : variables_map_) {
2788 inverted_bounds.variables.push_back(
id);
2792 for (
const auto& [
id, cstr_data] : linear_constraints_map_) {
2793 if (cstr_data.lower_bound > cstr_data.upper_bound) {
2794 inverted_bounds.linear_constraints.push_back(
id);
2799 std::sort(inverted_bounds.variables.begin(), inverted_bounds.variables.end());
2800 std::sort(inverted_bounds.linear_constraints.begin(),
2801 inverted_bounds.linear_constraints.end());
2802 return inverted_bounds;
2805absl::StatusOr<InvalidIndicators> GurobiSolver::ListInvalidIndicators()
const {
2806 InvalidIndicators invalid_indicators;
2807 for (
const auto& [constraint_id, indicator_data] :
2808 indicator_constraints_map_) {
2809 if (!indicator_data.has_value()) {
2812 const int64_t indicator_id = indicator_data->indicator_variable_id;
2813 const GurobiVariableIndex variable_index = variables_map_.at(indicator_id);
2819 const char var_type,
2822 (var_type ==
GRB_INTEGER && var_lb >= 0.0 && var_ub <= 1.0))) {
2823 invalid_indicators.invalid_indicators.push_back(
2824 {.variable = indicator_id, .constraint = constraint_id});
2828 invalid_indicators.Sort();
2829 return invalid_indicators;
2832bool GurobiSolver::is_multi_objective_mode()
const {
2833 return !multi_objectives_map_.empty();
2836absl::Status GurobiSolver::SetMultiObjectiveTolerances(
2837 const ModelSolveParametersProto& model_parameters) {
2838 const auto set_tolerances =
2839 [&](
const GurobiMultiObjectiveIndex
index,
2840 const ObjectiveParametersProto& objective_parameters)
2843 if (objective_parameters.has_objective_degradation_absolute_tolerance()) {
2846 objective_parameters.objective_degradation_absolute_tolerance()));
2848 if (objective_parameters.has_objective_degradation_relative_tolerance()) {
2851 objective_parameters.objective_degradation_relative_tolerance()));
2853 return absl::OkStatus();
2855 if (model_parameters.has_primary_objective_parameters()) {
2857 set_tolerances(multi_objectives_map_.at(std::nullopt),
2858 model_parameters.primary_objective_parameters()));
2860 for (
const auto& [
id, objective_parameters] :
2861 model_parameters.auxiliary_objective_parameters()) {
2863 set_tolerances(multi_objectives_map_.at(
id), objective_parameters));
2865 return absl::OkStatus();
2868absl::Status GurobiSolver::ResetModelParameters(
2869 const ModelSolveParametersProto& model_parameters) {
2870 for (
int i = 0;
i < model_parameters.branching_priorities().ids_size(); ++
i) {
2871 const int64_t var_id = model_parameters.branching_priorities().ids(i);
2872 const GurobiVariableIndex grb_index = variables_map_.at(var_id);
2875 <<
"failed to reset branching priority for variable ID " << var_id
2876 <<
" (Gurobi index = " << grb_index <<
")";
2878 for (
const int64_t lazy_constraint_id :
2879 model_parameters.lazy_linear_constraint_ids()) {
2880 const GurobiLinearConstraintIndex lazy_constraint_index =
2881 linear_constraints_map_.at(lazy_constraint_id).constraint_index;
2884 <<
"failed to reset lazy constraint for lazy constraint ID "
2885 << lazy_constraint_id <<
" (Gurobi index = " << lazy_constraint_index
2888 return absl::OkStatus();
2891absl::StatusOr<SolveResultProto> GurobiSolver::Solve(
2893 const ModelSolveParametersProto& model_parameters,
2895 const CallbackRegistrationProto& callback_registration,
const Callback cb,
2897 const absl::Time
start = absl::Now();
2909 ListInvertedBounds());
2918 ListInvalidIndicators());
2929 std::unique_ptr<SolveInterrupter> local_interrupter;
2930 if (cb !=
nullptr || interrupter !=
nullptr) {
2931 local_interrupter = std::make_unique<SolveInterrupter>();
2934 local_interrupter.get(), [&]() {
2942 gurobi_->Terminate();
2952 interrupter, [&]() { local_interrupter->Interrupt(); });
2954 if (model_parameters.has_initial_basis()) {
2958 model_parameters.solution_hints_size()));
2959 for (
int i = 0; i < model_parameters.solution_hints_size(); ++i) {
2962 model_parameters.solution_hints(i).variable_values(),
2966 UpdateInt32ListAttribute(model_parameters.branching_priorities(),
2968 if (is_multi_objective_mode()) {
2971 for (
const int64_t lazy_constraint_id :
2972 model_parameters.lazy_linear_constraint_ids()) {
2973 const GurobiLinearConstraintIndex lazy_constraint_index =
2974 linear_constraints_map_.at(lazy_constraint_id).constraint_index;
2981 lazy_constraint_index, 1));
2988 std::unique_ptr<GurobiCallbackData> gurobi_cb_data;
2989 if (cb !=
nullptr || local_interrupter !=
nullptr || message_cb !=
nullptr) {
2991 RegisterCallback(callback_registration, cb, message_cb,
2992 start, local_interrupter.get()));
2993 grb_cb = [&gurobi_cb_data](
2996 gurobi_cb_data->message_callback_data,
2997 gurobi_cb_data->local_interrupter);
3005 if (gurobi_cb_data !=
nullptr) {
3007 gurobi_cb_data->message_callback_data);
3011 ExtractSolveResultProto(
start, model_parameters));
3018 return solve_result;
3022absl::StatusOr<ComputeInfeasibleSubsystemResultProto>
3023GurobiSolver::ComputeInfeasibleSubsystem(
const SolveParametersProto&
parameters,
3026 const absl::Time
start = absl::Now();
3038 ListInvalidIndicators());
3049 std::unique_ptr<SolveInterrupter> local_interrupter;
3050 if (interrupter !=
nullptr) {
3051 local_interrupter = std::make_unique<SolveInterrupter>();
3054 local_interrupter.get(), [&]() {
3063 gurobi_->Terminate();
3073 interrupter, [&]() { local_interrupter->Interrupt(); });
3079 std::unique_ptr<GurobiCallbackData> gurobi_cb_data;
3080 if (local_interrupter !=
nullptr || message_cb !=
nullptr) {
3082 RegisterCallback({},
nullptr, message_cb,
start,
3083 local_interrupter.get()));
3084 grb_cb = [&gurobi_cb_data](
3087 gurobi_cb_data->message_callback_data,
3088 gurobi_cb_data->local_interrupter);
3092 ASSIGN_OR_RETURN(
const bool proven_infeasible, gurobi_->ComputeIIS(grb_cb));
3096 if (gurobi_cb_data !=
nullptr) {
3098 gurobi_cb_data->message_callback_data);
3102 ComputeInfeasibleSubsystemResultProto iis_result,
3103 ExtractComputeInfeasibleSubsystemResultProto(proven_infeasible));
#define ASSIGN_OR_RETURN(lhs, rexpr)
#define RETURN_IF_ERROR(expr)
static absl::StatusOr< std::unique_ptr< Gurobi > > NewWithSharedPrimaryEnv(GRBenv *primary_env)
std::function< absl::Status(const CallbackContext &)> Callback
static absl::StatusOr< std::unique_ptr< Gurobi > > New(GRBenvUniquePtr primary_env=nullptr)
absl::StatusOr< int > GetIntAttrElement(const char *name, int element) const
std::function< void(const std::vector< std::string > &)> MessageCallback
std::function< absl::StatusOr< CallbackResultProto >( const CallbackDataProto &)> Callback
std::unique_ptr< SharedBoundsManager > bounds
These can be nullptr depending on the options.
const std::string name
A name for logging purposes.
#define GRB_INT_PAR_BARITERLIMIT
#define GRB_INT_PAR_LOGTOCONSOLE
#define GRB_INT_ATTR_BRANCHPRIORITY
#define GRB_DBL_ATTR_START
#define GRB_DBL_PAR_MIPGAP
#define GRB_DBL_PAR_FEASIBILITYTOL
#define GRB_SOLUTION_LIMIT
#define GRB_INT_PAR_SOLUTIONLIMIT
#define GRB_NONBASIC_LOWER
#define GRB_INT_ATTR_MODELSENSE
#define GRB_INT_ATTR_VBASIS
#define GRB_GREATER_EQUAL
#define GRB_DBL_ATTR_NODECOUNT
#define GRB_INT_PAR_PRESOLVE
#define GRB_DBL_PAR_MIPGAPABS
#define GRB_DBL_ATTR_ITERCOUNT
#define GRB_INT_PAR_THREADS
#define GRB_DBL_ATTR_BOUND_SVIO
#define GRB_DBL_PAR_CUTOFF
#define GRB_INT_ATTR_IIS_QCONSTR
#define GRB_DBL_PAR_ITERATIONLIMIT
#define GRB_INT_PAR_METHOD
#define GRB_INT_ATTR_IS_QP
#define GRB_DBL_ATTR_OBJVAL
#define GRB_INT_PAR_LAZYCONSTRAINTS
#define GRB_INT_PAR_OBJNUMBER
#define GRB_INT_PAR_SCALEFLAG
#define GRB_DBL_PAR_HEURISTICS
#define GRB_METHOD_BARRIER
#define GRB_INT_ATTR_IS_MIP
#define GRB_DBL_ATTR_CONSTR_RESIDUAL
#define GRB_DBL_ATTR_OBJNVAL
#define GRB_INT_PAR_POOLSOLUTIONS
#define GRB_CHAR_ATTR_VTYPE
#define GRB_INT_ATTR_NUMSTART
#define GRB_DBL_ATTR_BOUND_VIO
#define GRB_NONBASIC_UPPER
#define GRB_INT_ATTR_IIS_UB
#define GRB_DBL_ATTR_OBJCON
#define GRB_DBL_PAR_BESTBDSTOP
#define GRB_STR_ATTR_MODELNAME
#define GRB_DBL_ATTR_CONSTR_VIO
#define GRB_DBL_ATTR_CONSTR_SRESIDUAL
#define GRB_DBL_ATTR_CONSTR_SVIO
#define GRB_INT_ATTR_IS_QCP
#define GRB_DBL_PAR_BESTOBJSTOP
#define GRB_INT_ATTR_IIS_GENCONSTR
#define GRB_INT_ATTR_IIS_MINIMAL
#define GRB_INT_PAR_STARTNUMBER
#define GRB_CHAR_ATTR_QCSENSE
#define GRB_CHAR_ATTR_SENSE
#define GRB_INT_ATTR_IIS_SOS
#define GRB_INT_ATTR_CBASIS
#define GRB_INT_ATTR_IIS_CONSTR
#define GRB_INT_ATTR_BARITERCOUNT
#define GRB_INT_ATTR_STATUS
#define GRB_DBL_ATTR_FARKASDUAL
#define GRB_DBL_ATTR_POOLOBJVAL
#define GRB_INT_PAR_SOLUTIONNUMBER
#define GRB_ITERATION_LIMIT
#define GRB_INT_ATTR_SOLCOUNT
#define GRB_METHOD_PRIMAL
#define GRB_INT_ATTR_IIS_LB
#define GRB_DBL_PAR_TIMELIMIT
#define GRB_DBL_PAR_NODELIMIT
#define GRB_USER_OBJ_LIMIT
#define GRB_DBL_ATTR_UNBDRAY
#define GRB_DBL_ATTR_OBJBOUND
#define GRB_INT_PAR_PRECRUSH
#define GRB_INT_ATTR_LAZY
void InsertOrDie(Collection *const collection, const typename Collection::value_type &value)
auto & InsertKeyOrDie(Collection *const collection, const typename Collection::value_type::first_type &key)
TerminationProto TerminateForReason(const TerminationReasonProto reason, const absl::string_view detail)
absl::Status ModelIsSupported(const ModelProto &model, const SupportedProblemStructures &support_menu, const absl::string_view solver_name)
std::vector< bool > EventToGurobiWhere(const absl::flat_hash_set< CallbackEventProto > &events)
absl::StatusOr< GRBenvUniquePtr > NewPrimaryEnvironment(std::optional< GurobiInitializerProto::ISVKey > proto_isv_key)
std::function< CallbackResult(const CallbackData &)> Callback
absl::flat_hash_set< CallbackEventProto > EventSet(const CallbackRegistrationProto &callback_registration)
Returns the callback_registration.request_registration as a set of enums.
TerminationProto OptimalTerminationProto(const double finite_primal_objective, const double dual_objective, const absl::string_view detail)
TerminationProto LimitTerminationProto(const bool is_maximize, const LimitProto limit, const std::optional< double > optional_finite_primal_objective, const std::optional< double > optional_dual_objective, const absl::string_view detail)
TerminationProto InfeasibleOrUnboundedTerminationProto(bool is_maximize, const FeasibilityStatusProto dual_feasibility_status, const absl::string_view detail)
bool UpdateIsSupported(const ModelUpdateProto &update, const SupportedProblemStructures &support_menu)
std::function< void(const std::vector< std::string > &)> MessageCallback
void GurobiCallbackImplFlush(const GurobiCallbackInput &callback_input, MessageCallbackData &message_callback_data)
absl::Status CheckRegisteredCallbackEvents(const CallbackRegistrationProto ®istration, const absl::flat_hash_set< CallbackEventProto > &supported_events)
SparseVectorView< T > MakeView(absl::Span< const int64_t > ids, const Collection &values)
TerminationProto CutoffTerminationProto(bool is_maximize, const absl::string_view detail)
Calls NoSolutionFoundTerminationProto() with LIMIT_CUTOFF LIMIT.
absl::Status GurobiCallbackImpl(const Gurobi::CallbackContext &context, const GurobiCallbackInput &callback_input, MessageCallbackData &message_callback_data, SolveInterrupter *const local_interrupter)
std::unique_ptr< GRBenv, GurobiFreeEnv > GRBenvUniquePtr
TerminationProto InfeasibleTerminationProto(bool is_maximize, const FeasibilityStatusProto dual_feasibility_status, const absl::string_view detail)
TerminationProto UnboundedTerminationProto(const bool is_maximize, const absl::string_view detail)
std::vector< K > SortedMapKeys(const absl::flat_hash_map< K, V > &in_map)
In SWIG mode, we don't want anything besides these top-level includes.
bool GurobiIsCorrectlyInstalled()
std::string ProtoEnumToString(ProtoEnumType enum_value)
constexpr bool kAnyXsanEnabled
inline ::absl::StatusOr< absl::Duration > DecodeGoogleApiProto(const google::protobuf::Duration &proto)
inline ::absl::StatusOr< google::protobuf::Duration > EncodeGoogleApiProto(absl::Duration d)
StatusBuilder InternalErrorBuilder()
StatusBuilder UnimplementedErrorBuilder()
StatusBuilder InvalidArgumentErrorBuilder()
std::vector< double > lower_bounds
std::vector< int > var_indices
std::vector< double > upper_bounds
#define MATH_OPT_REGISTER_SOLVER(solver_type, solver_factory)
absl::Status ToStatus() const
absl::Status ToStatus() const
Initialization arguments.
double objective_value
The value objective_vector^T * (solution - center_point).