1806 lines
66 KiB
C++
1806 lines
66 KiB
C++
// Copyright 2010-2025 Google LLC
|
|
// Licensed under the Apache License, Version 2.0 (the "License");
|
|
// you may not use this file except in compliance with the License.
|
|
// You may obtain a copy of the License at
|
|
//
|
|
// http://www.apache.org/licenses/LICENSE-2.0
|
|
//
|
|
// Unless required by applicable law or agreed to in writing, software
|
|
// distributed under the License is distributed on an "AS IS" BASIS,
|
|
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
|
// See the License for the specific language governing permissions and
|
|
// limitations under the License.
|
|
|
|
#include "ortools/math_opt/cpp/solve_impl.h"
|
|
|
|
#include <limits>
|
|
#include <memory>
|
|
#include <optional>
|
|
#include <string>
|
|
#include <utility>
|
|
|
|
#include "absl/container/flat_hash_set.h"
|
|
#include "absl/functional/any_invocable.h"
|
|
#include "absl/log/die_if_null.h"
|
|
#include "absl/status/status.h"
|
|
#include "absl/status/statusor.h"
|
|
#include "absl/strings/string_view.h"
|
|
#include "absl/types/span.h"
|
|
#include "gtest/gtest.h"
|
|
#include "ortools/base/gmock.h"
|
|
#include "ortools/math_opt/callback.pb.h"
|
|
#include "ortools/math_opt/core/base_solver.h"
|
|
#include "ortools/math_opt/core/math_opt_proto_utils.h"
|
|
#include "ortools/math_opt/core/sparse_collection_matchers.h"
|
|
#include "ortools/math_opt/cpp/callback.h"
|
|
#include "ortools/math_opt/cpp/compute_infeasible_subsystem_arguments.h"
|
|
#include "ortools/math_opt/cpp/compute_infeasible_subsystem_result.h"
|
|
#include "ortools/math_opt/cpp/math_opt.h"
|
|
#include "ortools/math_opt/cpp/model.h"
|
|
#include "ortools/math_opt/cpp/update_result.h"
|
|
#include "ortools/math_opt/infeasible_subsystem.pb.h"
|
|
#include "ortools/math_opt/model_parameters.pb.h"
|
|
#include "ortools/math_opt/solution.pb.h"
|
|
#include "ortools/math_opt/sparse_containers.pb.h"
|
|
#include "ortools/util/solve_interrupter.h"
|
|
|
|
namespace operations_research::math_opt::internal {
|
|
namespace {
|
|
|
|
using ::testing::_;
|
|
using ::testing::ByMove;
|
|
using ::testing::Eq;
|
|
using ::testing::EquivToProto;
|
|
using ::testing::Field;
|
|
using ::testing::HasSubstr;
|
|
using ::testing::InSequence;
|
|
using ::testing::Mock;
|
|
using ::testing::Ne;
|
|
using ::testing::Optional;
|
|
using ::testing::Pair;
|
|
using ::testing::Return;
|
|
using ::testing::UnorderedElementsAre;
|
|
using ::testing::status::StatusIs;
|
|
|
|
class BaseSolverMock : public BaseSolver {
|
|
public:
|
|
MOCK_METHOD(absl::StatusOr<SolveResultProto>, Solve,
|
|
(const SolveArgs& arguments), (override));
|
|
|
|
MOCK_METHOD(absl::StatusOr<ComputeInfeasibleSubsystemResultProto>,
|
|
ComputeInfeasibleSubsystem,
|
|
(const ComputeInfeasibleSubsystemArgs& arguments), (override));
|
|
|
|
MOCK_METHOD(absl::StatusOr<bool>, Update, (ModelUpdateProto model_update),
|
|
(override));
|
|
};
|
|
|
|
// Mock for BaseSolverFactory.
|
|
using BaseSolverFactoryMock =
|
|
testing::MockFunction<absl::StatusOr<std::unique_ptr<BaseSolver>>(
|
|
SolverTypeProto solver_type, const ModelProto& model,
|
|
SolveInterrupter* local_canceller)>;
|
|
|
|
// Delegate all calls to another instance of BaseSolver.
|
|
//
|
|
// This is used as a return value in BaseSolverFactoryMock as:
|
|
// * this function needs to return a unique_ptr<BaseSolver>
|
|
// * but we want to be able to use a BaseSolverMock from the stack.
|
|
//
|
|
// Thus we can simply mock BaseSolverFactoryMock with
|
|
// BaseSolverMock solver;
|
|
//
|
|
// EXPECT_CALL(factory_mock,
|
|
// Call(EquivToProto(basic_lp.model.ExportModel()), _, _))
|
|
// .WillOnce(Return(ByMove(
|
|
// std::make_unique<DelegatingBaseSolver>(&solver))));
|
|
//
|
|
// and add other EXPECT_CALL(solver, ...) on the instance that exists on stack.
|
|
class DelegatingBaseSolver : public BaseSolver {
|
|
public:
|
|
// Wraps the input solver interface, delegating calls to it. The optional
|
|
// destructor_cb callback will be called in ~DelegatingBaseSolver().
|
|
explicit DelegatingBaseSolver(
|
|
BaseSolver* const solver,
|
|
absl::AnyInvocable<void()> destructor_cb = nullptr)
|
|
: solver_(ABSL_DIE_IF_NULL(solver)),
|
|
destructor_cb_(std::move(destructor_cb)) {}
|
|
|
|
~DelegatingBaseSolver() override {
|
|
if (destructor_cb_ != nullptr) {
|
|
destructor_cb_();
|
|
}
|
|
}
|
|
|
|
absl::StatusOr<SolveResultProto> Solve(const SolveArgs& arguments) override {
|
|
return solver_->Solve(arguments);
|
|
}
|
|
|
|
absl::StatusOr<ComputeInfeasibleSubsystemResultProto>
|
|
ComputeInfeasibleSubsystem(
|
|
const ComputeInfeasibleSubsystemArgs& arguments) override {
|
|
return solver_->ComputeInfeasibleSubsystem(arguments);
|
|
}
|
|
|
|
absl::StatusOr<bool> Update(ModelUpdateProto model_update) override {
|
|
return solver_->Update(std::move(model_update));
|
|
}
|
|
|
|
private:
|
|
BaseSolver* const solver_;
|
|
absl::AnyInvocable<void()> destructor_cb_;
|
|
};
|
|
|
|
// Returns a matcher that matches the fields of SolveArgs according to the
|
|
// provided matchers.
|
|
//
|
|
// Note that we have to use template parameters for function/data pointers
|
|
// fields as we can't use testing::Matcher<FuncType> or
|
|
// testing::Matcher<DataType*>.
|
|
template <typename MessageCallbackMatcher, typename CallbackMatcher,
|
|
typename SolveInterrupterPtrMatcher>
|
|
testing::Matcher<const BaseSolver::SolveArgs&> SolveArgsAre(
|
|
testing::Matcher<SolveParametersProto> parameters,
|
|
testing::Matcher<ModelSolveParametersProto> model_parameters,
|
|
MessageCallbackMatcher message_callback,
|
|
testing::Matcher<CallbackRegistrationProto> callback_registration,
|
|
CallbackMatcher user_cb, SolveInterrupterPtrMatcher interrupter) {
|
|
return AllOf(
|
|
Field("parameters", &BaseSolver::SolveArgs::parameters, parameters),
|
|
Field("model_parameters", &BaseSolver::SolveArgs::model_parameters,
|
|
model_parameters),
|
|
Field("message_callback", &BaseSolver::SolveArgs::message_callback,
|
|
message_callback),
|
|
Field("callback_registration",
|
|
&BaseSolver::SolveArgs::callback_registration,
|
|
callback_registration),
|
|
Field("user_cb", &BaseSolver::SolveArgs::user_cb, user_cb),
|
|
Field("interrupter", &BaseSolver::SolveArgs::interrupter, interrupter));
|
|
}
|
|
|
|
// Returns a matcher that matches the fields of ComputeInfeasibleSubsystemArgs
|
|
// according to the provided matchers.
|
|
//
|
|
// Note that we have to use template parameters for function/data pointers
|
|
// fields as we can't use testing::Matcher<FuncType> or
|
|
// testing::Matcher<DataType*>.
|
|
template <typename MessageCallbackMatcher, typename SolveInterrupterPtrMatcher>
|
|
testing::Matcher<const BaseSolver::ComputeInfeasibleSubsystemArgs&>
|
|
ComputeInfeasibleSubsystemArgsAre(
|
|
testing::Matcher<SolveParametersProto> parameters,
|
|
MessageCallbackMatcher message_callback,
|
|
SolveInterrupterPtrMatcher interrupter) {
|
|
return AllOf(
|
|
Field("parameters",
|
|
&BaseSolver::ComputeInfeasibleSubsystemArgs::parameters,
|
|
parameters),
|
|
Field("message_callback",
|
|
&BaseSolver::ComputeInfeasibleSubsystemArgs::message_callback,
|
|
message_callback),
|
|
Field("interrupter",
|
|
&BaseSolver::ComputeInfeasibleSubsystemArgs::interrupter,
|
|
interrupter));
|
|
}
|
|
|
|
constexpr double kInf = std::numeric_limits<double>::infinity();
|
|
|
|
// Basic LP model:
|
|
//
|
|
// a and b are continuous variable
|
|
//
|
|
// minimize a - b
|
|
// s.t. 0 <= a
|
|
// 0 <= b <= 3
|
|
struct BasicLp {
|
|
BasicLp();
|
|
|
|
// Sets the upper bound of variable b to 2.0 and returns the corresponding
|
|
// update.
|
|
std::optional<ModelUpdateProto> UpdateUpperBoundOfB();
|
|
|
|
// Returns the expected optimal result for this model. Only put the given set
|
|
// of variables in the result (to test filters). When `after_update` is true,
|
|
// returns the optimal result after UpdateUpperBoundOfB() has been called.
|
|
SolveResultProto OptimalResult(const absl::flat_hash_set<Variable>& vars,
|
|
bool after_update = false) const;
|
|
|
|
Model model;
|
|
const Variable a;
|
|
const Variable b;
|
|
};
|
|
|
|
BasicLp::BasicLp()
|
|
: a(model.AddVariable(0.0, kInf, false, "a")),
|
|
b(model.AddVariable(0.0, 3.0, false, "b")) {}
|
|
|
|
std::optional<ModelUpdateProto> BasicLp::UpdateUpperBoundOfB() {
|
|
const std::unique_ptr<UpdateTracker> tracker = model.NewUpdateTracker();
|
|
model.set_upper_bound(b, 2.0);
|
|
return tracker->ExportModelUpdate().value();
|
|
}
|
|
|
|
SolveResultProto BasicLp::OptimalResult(
|
|
const absl::flat_hash_set<Variable>& vars, bool after_update) const {
|
|
SolveResultProto result;
|
|
result.mutable_termination()->set_reason(TERMINATION_REASON_OPTIMAL);
|
|
result.mutable_solve_stats()->mutable_problem_status()->set_primal_status(
|
|
FEASIBILITY_STATUS_FEASIBLE);
|
|
result.mutable_solve_stats()->mutable_problem_status()->set_dual_status(
|
|
FEASIBILITY_STATUS_FEASIBLE);
|
|
PrimalSolutionProto* const solution =
|
|
result.add_solutions()->mutable_primal_solution();
|
|
solution->set_objective_value(0.0);
|
|
solution->set_feasibility_status(SOLUTION_STATUS_FEASIBLE);
|
|
if (vars.contains(a)) {
|
|
solution->mutable_variable_values()->add_ids(a.id());
|
|
solution->mutable_variable_values()->add_values(0.0);
|
|
}
|
|
if (vars.contains(b)) {
|
|
solution->mutable_variable_values()->add_ids(b.id());
|
|
solution->mutable_variable_values()->add_values(after_update ? 2.0 : 3.0);
|
|
}
|
|
return result;
|
|
}
|
|
|
|
// Basic infeasible LP model:
|
|
//
|
|
// minimize 0
|
|
// s.t. x <= -1 (linear constraint)
|
|
// 0 <= x <= 1 (bounds)
|
|
struct BasicInfeasibleLp {
|
|
BasicInfeasibleLp()
|
|
: x(model.AddContinuousVariable(0.0, 1.0, "x")),
|
|
c(model.AddLinearConstraint(x <= -1.0, "c")) {}
|
|
|
|
ComputeInfeasibleSubsystemResultProto InfeasibleResult() const {
|
|
ComputeInfeasibleSubsystemResultProto result;
|
|
result.set_feasibility(FEASIBILITY_STATUS_INFEASIBLE);
|
|
(*result.mutable_infeasible_subsystem()->mutable_variable_bounds())[0]
|
|
.set_lower(true);
|
|
(*result.mutable_infeasible_subsystem()->mutable_variable_bounds())[0]
|
|
.set_upper(false);
|
|
(*result.mutable_infeasible_subsystem()->mutable_linear_constraints())[0]
|
|
.set_lower(false);
|
|
(*result.mutable_infeasible_subsystem()->mutable_linear_constraints())[0]
|
|
.set_upper(true);
|
|
result.set_is_minimal(true);
|
|
return result;
|
|
}
|
|
|
|
// Sets the upper bound of constraint c to -2.0 and returns the corresponding
|
|
// update.
|
|
std::optional<ModelUpdateProto> UpdateUpperBoundOfC() {
|
|
const std::unique_ptr<UpdateTracker> tracker = model.NewUpdateTracker();
|
|
model.set_upper_bound(c, -2.0);
|
|
return tracker->ExportModelUpdate().value();
|
|
}
|
|
|
|
Model model;
|
|
const Variable x;
|
|
const LinearConstraint c;
|
|
};
|
|
|
|
// Test calling Solve() without any callback.
|
|
TEST(SolveImplTest, SuccessfulSolveNoCallback) {
|
|
BasicLp basic_lp;
|
|
|
|
SolveArguments args;
|
|
args.parameters.enable_output = true;
|
|
|
|
args.model_parameters =
|
|
ModelSolveParameters::OnlySomePrimalVariables({basic_lp.a});
|
|
|
|
SolveInterrupter interrupter;
|
|
args.interrupter = &interrupter;
|
|
|
|
args.message_callback = [](absl::Span<const std::string>) {};
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver;
|
|
{
|
|
InSequence s;
|
|
|
|
EXPECT_CALL(factory_mock,
|
|
Call(SOLVER_TYPE_GLOP,
|
|
EquivToProto(basic_lp.model.ExportModel()), Ne(nullptr)))
|
|
.WillOnce(
|
|
Return(ByMove(std::make_unique<DelegatingBaseSolver>(&solver))));
|
|
|
|
ASSERT_OK_AND_ASSIGN(const ModelSolveParametersProto model_parameters,
|
|
args.model_parameters.Proto());
|
|
EXPECT_CALL(solver, Solve(SolveArgsAre(
|
|
EquivToProto(args.parameters.Proto()),
|
|
EquivToProto(model_parameters), Ne(nullptr),
|
|
EquivToProto(args.callback_registration.Proto()),
|
|
Eq(nullptr), Eq(&interrupter))))
|
|
.WillOnce(Return(basic_lp.OptimalResult({basic_lp.a})));
|
|
}
|
|
|
|
ASSERT_OK_AND_ASSIGN(
|
|
const SolveResult result,
|
|
SolveImpl(factory_mock.AsStdFunction(), basic_lp.model, SolverType::kGlop,
|
|
args, /*user_canceller=*/nullptr,
|
|
/*remove_names=*/false));
|
|
|
|
EXPECT_EQ(result.termination.reason, TerminationReason::kOptimal);
|
|
EXPECT_THAT(result.variable_values(),
|
|
UnorderedElementsAre(Pair(basic_lp.a, 0.0)));
|
|
}
|
|
|
|
// Test calling Solve() with a callback.
|
|
TEST(SolveImplTest, SuccessfulSolveWithCallback) {
|
|
BasicLp basic_lp;
|
|
|
|
SolveArguments args;
|
|
args.parameters.enable_output = true;
|
|
|
|
args.model_parameters =
|
|
ModelSolveParameters::OnlySomePrimalVariables({basic_lp.a});
|
|
|
|
args.callback_registration.add_lazy_constraints = true;
|
|
args.callback_registration.events.insert(CallbackEvent::kMipSolution);
|
|
|
|
const auto fake_solve = [&](const BaseSolver::SolveArgs& args)
|
|
-> absl::StatusOr<SolveResultProto> {
|
|
CallbackDataProto cb_data;
|
|
cb_data.set_event(CALLBACK_EVENT_MIP_SOLUTION);
|
|
*cb_data.mutable_primal_solution_vector() = MakeSparseDoubleVector(
|
|
{{basic_lp.a.id(), 1.0}, {basic_lp.b.id(), 0.0}});
|
|
args.user_cb(cb_data);
|
|
return basic_lp.OptimalResult({basic_lp.a});
|
|
};
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver;
|
|
{
|
|
InSequence s;
|
|
|
|
EXPECT_CALL(
|
|
factory_mock,
|
|
Call(SOLVER_TYPE_GLOP, EquivToProto(basic_lp.model.ExportModel()), _))
|
|
.WillOnce(
|
|
Return(ByMove(std::make_unique<DelegatingBaseSolver>(&solver))));
|
|
|
|
ASSERT_OK_AND_ASSIGN(const ModelSolveParametersProto model_parameters,
|
|
args.model_parameters.Proto());
|
|
EXPECT_CALL(solver, Solve(SolveArgsAre(
|
|
EquivToProto(args.parameters.Proto()),
|
|
EquivToProto(model_parameters), Eq(nullptr),
|
|
EquivToProto(args.callback_registration.Proto()),
|
|
Ne(nullptr), Eq(nullptr))))
|
|
.WillOnce(fake_solve);
|
|
}
|
|
|
|
int callback_called_count = 0;
|
|
args.callback = [&](const CallbackData& callback_data) {
|
|
++callback_called_count;
|
|
CallbackResult result;
|
|
result.AddLazyConstraint(basic_lp.a + basic_lp.b <= 3);
|
|
return result;
|
|
};
|
|
ASSERT_OK_AND_ASSIGN(
|
|
const SolveResult result,
|
|
SolveImpl(factory_mock.AsStdFunction(), basic_lp.model, SolverType::kGlop,
|
|
args, /*user_canceller=*/nullptr, /*remove_names=*/false));
|
|
|
|
EXPECT_EQ(callback_called_count, 1);
|
|
EXPECT_EQ(result.termination.reason, TerminationReason::kOptimal);
|
|
EXPECT_THAT(result.variable_values(),
|
|
UnorderedElementsAre(Pair(basic_lp.a, 0.0)));
|
|
}
|
|
|
|
TEST(SolveImplTest, RemoveNamesSendsNoNames) {
|
|
Model model;
|
|
model.AddBinaryVariable("x");
|
|
|
|
ModelProto expected_model;
|
|
expected_model.mutable_variables()->add_ids(0);
|
|
expected_model.mutable_variables()->add_lower_bounds(0.0);
|
|
expected_model.mutable_variables()->add_upper_bounds(1.0);
|
|
expected_model.mutable_variables()->add_integers(true);
|
|
|
|
SolveResultProto fake_result;
|
|
*fake_result.mutable_termination() =
|
|
NoSolutionFoundTerminationProto(/*is_maximize=*/false, LIMIT_TIME);
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver;
|
|
{
|
|
InSequence s;
|
|
|
|
EXPECT_CALL(factory_mock,
|
|
Call(SOLVER_TYPE_GLOP, EquivToProto(expected_model), _))
|
|
.WillOnce(
|
|
Return(ByMove(std::make_unique<DelegatingBaseSolver>(&solver))));
|
|
|
|
EXPECT_CALL(solver, Solve(SolveArgsAre(_, _, _, _, _, _)))
|
|
.WillOnce(Return(fake_result));
|
|
}
|
|
|
|
ASSERT_OK_AND_ASSIGN(
|
|
const SolveResult result,
|
|
SolveImpl(factory_mock.AsStdFunction(), model, SolverType::kGlop, {},
|
|
/*user_canceller=*/nullptr, /*remove_names=*/true));
|
|
}
|
|
|
|
// Test calling Solve() with a solver that fails to returns the SolverInterface
|
|
// for a given model.
|
|
TEST(SolveImplTest, FailingSolveInstantiation) {
|
|
BasicLp basic_lp;
|
|
|
|
SolveArguments args;
|
|
args.parameters.enable_output = true;
|
|
|
|
args.model_parameters =
|
|
ModelSolveParameters::OnlySomePrimalVariables({basic_lp.a});
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver;
|
|
EXPECT_CALL(factory_mock, Call(SOLVER_TYPE_GLOP,
|
|
EquivToProto(basic_lp.model.ExportModel()), _))
|
|
.WillOnce(Return(ByMove(absl::InternalError("instantiation failed"))));
|
|
|
|
ASSERT_THAT(SolveImpl(factory_mock.AsStdFunction(), basic_lp.model,
|
|
SolverType::kGlop, args,
|
|
/*user_canceller=*/nullptr, /*remove_names=*/false),
|
|
StatusIs(absl::StatusCode::kInternal, "instantiation failed"));
|
|
}
|
|
|
|
// Test calling Solve() with a solver that returns an error on
|
|
// SolverInterface::Solve().
|
|
TEST(SolveImplTest, FailingSolve) {
|
|
BasicLp basic_lp;
|
|
|
|
SolveArguments args;
|
|
args.parameters.enable_output = true;
|
|
|
|
args.model_parameters =
|
|
ModelSolveParameters::OnlySomePrimalVariables({basic_lp.a});
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver;
|
|
{
|
|
InSequence s;
|
|
|
|
EXPECT_CALL(
|
|
factory_mock,
|
|
Call(SOLVER_TYPE_GLOP, EquivToProto(basic_lp.model.ExportModel()), _))
|
|
.WillOnce(
|
|
Return(ByMove(std::make_unique<DelegatingBaseSolver>(&solver))));
|
|
|
|
ASSERT_OK_AND_ASSIGN(const ModelSolveParametersProto model_parameters,
|
|
args.model_parameters.Proto());
|
|
EXPECT_CALL(solver, Solve(SolveArgsAre(
|
|
EquivToProto(args.parameters.Proto()),
|
|
EquivToProto(model_parameters), Eq(nullptr),
|
|
EquivToProto(args.callback_registration.Proto()),
|
|
Eq(nullptr), Eq(nullptr))))
|
|
.WillOnce(Return(absl::InternalError("solve failed")));
|
|
}
|
|
|
|
ASSERT_THAT(
|
|
SolveImpl(factory_mock.AsStdFunction(), basic_lp.model, SolverType::kGlop,
|
|
args, /*user_canceller=*/nullptr, /*remove_names=*/false),
|
|
StatusIs(absl::StatusCode::kInternal, "solve failed"));
|
|
}
|
|
|
|
TEST(SolveImplTest, WrongModelInModelParameters) {
|
|
BasicLp basic_lp;
|
|
BasicLp other_basic_lp;
|
|
|
|
SolveArguments args;
|
|
args.parameters.enable_output = true;
|
|
|
|
// Here we use the wrong variable.
|
|
args.model_parameters =
|
|
ModelSolveParameters::OnlySomePrimalVariables({other_basic_lp.a});
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver;
|
|
EXPECT_CALL(factory_mock, Call(SOLVER_TYPE_GLOP,
|
|
EquivToProto(basic_lp.model.ExportModel()), _))
|
|
.WillOnce(
|
|
Return(ByMove(std::make_unique<DelegatingBaseSolver>(&solver))));
|
|
|
|
EXPECT_THAT(
|
|
SolveImpl(factory_mock.AsStdFunction(), basic_lp.model, SolverType::kGlop,
|
|
args, /*user_canceller=*/nullptr, /*remove_names=*/false),
|
|
StatusIs(absl::StatusCode::kInvalidArgument,
|
|
HasSubstr(internal::kInputFromInvalidModelStorage)));
|
|
}
|
|
|
|
TEST(SolveImplTest, WrongModelInCallbackRegistration) {
|
|
BasicLp basic_lp;
|
|
BasicLp other_basic_lp;
|
|
|
|
SolveArguments args;
|
|
args.parameters.enable_output = true;
|
|
|
|
// Here we use the wrong variable.
|
|
args.callback_registration.mip_solution_filter =
|
|
MakeKeepKeysFilter({other_basic_lp.a});
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver;
|
|
EXPECT_CALL(factory_mock, Call(SOLVER_TYPE_GLOP,
|
|
EquivToProto(basic_lp.model.ExportModel()), _))
|
|
.WillOnce(
|
|
Return(ByMove(std::make_unique<DelegatingBaseSolver>(&solver))));
|
|
|
|
EXPECT_THAT(
|
|
SolveImpl(factory_mock.AsStdFunction(), basic_lp.model, SolverType::kGlop,
|
|
args, /*user_canceller=*/nullptr, /*remove_names=*/false),
|
|
StatusIs(absl::StatusCode::kInvalidArgument,
|
|
HasSubstr(internal::kInputFromInvalidModelStorage)));
|
|
}
|
|
|
|
TEST(SolveImplTest, WrongModelInCallbackResult) {
|
|
// We repeat the same test but either return a valid result or an error in
|
|
// fake_solve.
|
|
for (const bool return_an_error : {false, true}) {
|
|
SCOPED_TRACE(return_an_error ? "with fake_solve returning an error"
|
|
: "with fake_solve returning a result");
|
|
BasicLp basic_lp;
|
|
BasicLp other_basic_lp;
|
|
|
|
SolveArguments args;
|
|
args.parameters.enable_output = true;
|
|
|
|
args.callback_registration.add_lazy_constraints = true;
|
|
args.callback_registration.events.insert(CallbackEvent::kMipSolution);
|
|
|
|
// Will be set to the provided local_canceller in the factory.
|
|
SolveInterrupter* provided_local_canceller = nullptr;
|
|
|
|
const auto fake_solve = [&](const BaseSolver::SolveArgs& args)
|
|
-> absl::StatusOr<SolveResultProto> {
|
|
CallbackDataProto cb_data;
|
|
cb_data.set_event(CALLBACK_EVENT_MIP_SOLUTION);
|
|
*cb_data.mutable_primal_solution_vector() = MakeSparseDoubleVector(
|
|
{{basic_lp.a.id(), 1.0}, {basic_lp.b.id(), 0.0}});
|
|
CallbackResultProto result = args.user_cb(cb_data);
|
|
// Errors in callback should result in early termination.
|
|
EXPECT_TRUE(result.terminate());
|
|
// Errors in callback should trigger the cancellation.
|
|
EXPECT_TRUE(provided_local_canceller->IsInterrupted());
|
|
// The returned value should be ignored.
|
|
if (return_an_error) {
|
|
return absl::CancelledError("solver has been cancelled");
|
|
}
|
|
return basic_lp.OptimalResult({basic_lp.a, basic_lp.b});
|
|
};
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver;
|
|
{
|
|
InSequence s;
|
|
|
|
EXPECT_CALL(
|
|
factory_mock,
|
|
Call(SOLVER_TYPE_GLOP, EquivToProto(basic_lp.model.ExportModel()), _))
|
|
.WillOnce([&](const SolverTypeProto solver_type,
|
|
const ModelProto& model,
|
|
SolveInterrupter* const local_canceller) {
|
|
provided_local_canceller = local_canceller;
|
|
return std::make_unique<DelegatingBaseSolver>(&solver);
|
|
});
|
|
|
|
ASSERT_OK_AND_ASSIGN(const ModelSolveParametersProto model_parameters,
|
|
args.model_parameters.Proto());
|
|
EXPECT_CALL(solver, Solve(SolveArgsAre(
|
|
EquivToProto(args.parameters.Proto()),
|
|
EquivToProto(model_parameters), Eq(nullptr),
|
|
EquivToProto(args.callback_registration.Proto()),
|
|
Ne(nullptr), Eq(nullptr))))
|
|
.WillOnce(fake_solve);
|
|
}
|
|
|
|
args.callback = [&](const CallbackData& callback_data) {
|
|
CallbackResult result;
|
|
// We use the wrong model here.
|
|
result.AddLazyConstraint(other_basic_lp.a + other_basic_lp.b <= 3);
|
|
return result;
|
|
};
|
|
|
|
EXPECT_THAT(SolveImpl(factory_mock.AsStdFunction(), basic_lp.model,
|
|
SolverType::kGlop, args, /*user_canceller=*/nullptr,
|
|
/*remove_names=*/false),
|
|
StatusIs(absl::StatusCode::kInvalidArgument,
|
|
HasSubstr(internal::kInputFromInvalidModelStorage)));
|
|
}
|
|
}
|
|
|
|
TEST(SolveImplTest, UserCancellation) {
|
|
BasicLp basic_lp;
|
|
|
|
// Will be set to the provided local_canceller in the factory.
|
|
SolveInterrupter* provided_local_canceller = nullptr;
|
|
|
|
const auto fake_solve = [&](const BaseSolver::SolveArgs& args)
|
|
-> absl::StatusOr<SolveResultProto> {
|
|
// The solver should have been cancelled before its Solve() is called.
|
|
EXPECT_TRUE(provided_local_canceller->IsInterrupted());
|
|
return absl::CancelledError("solver has been cancelled");
|
|
};
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver;
|
|
{
|
|
InSequence s;
|
|
|
|
EXPECT_CALL(factory_mock, Call(SOLVER_TYPE_GLOP, _, Ne(nullptr)))
|
|
.WillOnce([&](const SolverTypeProto solver_type,
|
|
const ModelProto& model,
|
|
SolveInterrupter* const local_canceller) {
|
|
provided_local_canceller = local_canceller;
|
|
return std::make_unique<DelegatingBaseSolver>(&solver);
|
|
});
|
|
|
|
EXPECT_CALL(solver, Solve(_)).WillOnce(fake_solve);
|
|
}
|
|
|
|
SolveInterrupter user_canceller;
|
|
user_canceller.Interrupt();
|
|
|
|
ASSERT_THAT(
|
|
SolveImpl(factory_mock.AsStdFunction(), basic_lp.model, SolverType::kGlop,
|
|
{}, /*user_canceller=*/&user_canceller,
|
|
/*remove_names=*/false),
|
|
StatusIs(absl::StatusCode::kCancelled));
|
|
}
|
|
|
|
TEST(ComputeInfeasibleSubsystemImplTest, SuccessfulCall) {
|
|
BasicInfeasibleLp lp;
|
|
|
|
ComputeInfeasibleSubsystemArguments args;
|
|
args.parameters.enable_output = true;
|
|
|
|
SolveInterrupter interrupter;
|
|
args.interrupter = &interrupter;
|
|
|
|
args.message_callback = [](absl::Span<const std::string>) {};
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver;
|
|
{
|
|
InSequence s;
|
|
|
|
EXPECT_CALL(factory_mock,
|
|
Call(SOLVER_TYPE_GLOP, EquivToProto(lp.model.ExportModel()), _))
|
|
.WillOnce(
|
|
Return(ByMove(std::make_unique<DelegatingBaseSolver>(&solver))));
|
|
|
|
EXPECT_CALL(solver,
|
|
ComputeInfeasibleSubsystem(ComputeInfeasibleSubsystemArgsAre(
|
|
EquivToProto(args.parameters.Proto()), Ne(nullptr),
|
|
Eq(&interrupter))))
|
|
.WillOnce(Return(lp.InfeasibleResult()));
|
|
}
|
|
|
|
ASSERT_OK_AND_ASSIGN(
|
|
const ComputeInfeasibleSubsystemResult result,
|
|
ComputeInfeasibleSubsystemImpl(
|
|
factory_mock.AsStdFunction(), lp.model, SolverType::kGlop, args,
|
|
/*user_canceller=*/nullptr, /*remove_names=*/false));
|
|
|
|
EXPECT_EQ(result.feasibility, FeasibilityStatus::kInfeasible);
|
|
}
|
|
|
|
TEST(ComputeInfeasibleSubsystemImplTest, FailingSolve) {
|
|
BasicInfeasibleLp lp;
|
|
|
|
ComputeInfeasibleSubsystemArguments args;
|
|
args.parameters.enable_output = true;
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver;
|
|
{
|
|
InSequence s;
|
|
|
|
EXPECT_CALL(factory_mock,
|
|
Call(SOLVER_TYPE_GLOP, EquivToProto(lp.model.ExportModel()), _))
|
|
.WillOnce(
|
|
Return(ByMove(std::make_unique<DelegatingBaseSolver>(&solver))));
|
|
|
|
EXPECT_CALL(
|
|
solver,
|
|
ComputeInfeasibleSubsystem(ComputeInfeasibleSubsystemArgsAre(
|
|
EquivToProto(args.parameters.Proto()), Eq(nullptr), Eq(nullptr))))
|
|
.WillOnce(Return(absl::InternalError("infeasible subsystem failed")));
|
|
}
|
|
|
|
ASSERT_THAT(
|
|
ComputeInfeasibleSubsystemImpl(
|
|
factory_mock.AsStdFunction(), lp.model, SolverType::kGlop, args,
|
|
/*user_canceller=*/nullptr, /*remove_names=*/false),
|
|
StatusIs(absl::StatusCode::kInternal, "infeasible subsystem failed"));
|
|
}
|
|
|
|
TEST(ComputeInfeasibleSubsystemImplTest, UserCancellation) {
|
|
BasicLp basic_lp;
|
|
|
|
// Will be set to the provided local_canceller in the factory.
|
|
SolveInterrupter* provided_local_canceller = nullptr;
|
|
|
|
const auto fake_solve =
|
|
[&](const BaseSolver::ComputeInfeasibleSubsystemArgs& args)
|
|
-> absl::StatusOr<ComputeInfeasibleSubsystemResultProto> {
|
|
// The solver should have been cancelled before its
|
|
// ComputeInfeasibleSubsystem() is called.
|
|
EXPECT_TRUE(provided_local_canceller->IsInterrupted());
|
|
return absl::CancelledError("solver has been cancelled");
|
|
};
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver;
|
|
{
|
|
InSequence s;
|
|
|
|
EXPECT_CALL(factory_mock,
|
|
Call(SOLVER_TYPE_GLOP,
|
|
EquivToProto(basic_lp.model.ExportModel()), Ne(nullptr)))
|
|
.WillOnce([&](const SolverTypeProto solver_type,
|
|
const ModelProto& model,
|
|
SolveInterrupter* const local_canceller) {
|
|
provided_local_canceller = local_canceller;
|
|
return std::make_unique<DelegatingBaseSolver>(&solver);
|
|
});
|
|
|
|
EXPECT_CALL(solver, ComputeInfeasibleSubsystem(_)).WillOnce(fake_solve);
|
|
}
|
|
|
|
SolveInterrupter user_canceller;
|
|
user_canceller.Interrupt();
|
|
|
|
ASSERT_THAT(ComputeInfeasibleSubsystemImpl(
|
|
factory_mock.AsStdFunction(), basic_lp.model,
|
|
SolverType::kGlop, {}, /*user_canceller=*/&user_canceller,
|
|
/*remove_names=*/false),
|
|
StatusIs(absl::StatusCode::kCancelled));
|
|
}
|
|
|
|
TEST(IncrementalSolverImplTest, NullModel) {
|
|
BaseSolverFactoryMock factory_mock;
|
|
|
|
EXPECT_THAT(IncrementalSolverImpl::New(
|
|
factory_mock.AsStdFunction(), nullptr, SolverType::kGlop,
|
|
/*user_canceller=*/nullptr, /*remove_names=*/false),
|
|
StatusIs(absl::StatusCode::kInvalidArgument, HasSubstr("model")));
|
|
}
|
|
|
|
TEST(IncrementalSolverImplTest, SolverType) {
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver;
|
|
BasicLp basic_lp;
|
|
|
|
EXPECT_CALL(factory_mock,
|
|
Call(SOLVER_TYPE_GLOP, EquivToProto(basic_lp.model.ExportModel()),
|
|
Ne(nullptr)))
|
|
.WillOnce(
|
|
Return(ByMove(std::make_unique<DelegatingBaseSolver>(&solver))));
|
|
|
|
ASSERT_OK_AND_ASSIGN(
|
|
std::unique_ptr<IncrementalSolver> incremental_solver,
|
|
IncrementalSolverImpl::New(
|
|
factory_mock.AsStdFunction(), &basic_lp.model, SolverType::kGlop,
|
|
/*user_canceller=*/nullptr, /*remove_names=*/false));
|
|
EXPECT_EQ(incremental_solver->solver_type(), SolverType::kGlop);
|
|
}
|
|
|
|
// Test calling IncrementalSolver without any callback with a succeeding
|
|
// non-empty update.
|
|
TEST(IncrementalSolverImplTest, IncrementalSolveNoCallback) {
|
|
BasicLp basic_lp;
|
|
|
|
BaseSolverMock solver_interface;
|
|
|
|
// The first solve.
|
|
SolveArguments args_1;
|
|
args_1.parameters.enable_output = true;
|
|
args_1.model_parameters =
|
|
ModelSolveParameters::OnlySomePrimalVariables({basic_lp.a});
|
|
|
|
SolveInterrupter interrupter;
|
|
args_1.interrupter = &interrupter;
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
EXPECT_CALL(factory_mock, Call(SOLVER_TYPE_GLOP,
|
|
EquivToProto(basic_lp.model.ExportModel()), _))
|
|
.WillOnce(Return(
|
|
ByMove(std::make_unique<DelegatingBaseSolver>(&solver_interface))));
|
|
|
|
ASSERT_OK_AND_ASSIGN(
|
|
std::unique_ptr<IncrementalSolver> solver,
|
|
IncrementalSolverImpl::New(
|
|
factory_mock.AsStdFunction(), &basic_lp.model, SolverType::kGlop,
|
|
/*user_canceller=*/nullptr, /*remove_names=*/false));
|
|
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver_interface);
|
|
|
|
{
|
|
ASSERT_OK_AND_ASSIGN(const ModelSolveParametersProto model_parameters_1,
|
|
args_1.model_parameters.Proto());
|
|
EXPECT_CALL(
|
|
solver_interface,
|
|
Solve(SolveArgsAre(EquivToProto(args_1.parameters.Proto()),
|
|
EquivToProto(model_parameters_1), Eq(nullptr),
|
|
EquivToProto(args_1.callback_registration.Proto()),
|
|
Eq(nullptr), Eq(&interrupter))))
|
|
.WillOnce(Return(basic_lp.OptimalResult({basic_lp.a})));
|
|
}
|
|
|
|
ASSERT_OK_AND_ASSIGN(const SolveResult result_1,
|
|
solver->SolveWithoutUpdate(args_1));
|
|
|
|
EXPECT_EQ(result_1.termination.reason, TerminationReason::kOptimal);
|
|
EXPECT_THAT(result_1.variable_values(),
|
|
UnorderedElementsAre(Pair(basic_lp.a, 0.0)));
|
|
|
|
// Second solve with update.
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver_interface);
|
|
|
|
const std::optional<ModelUpdateProto> update = basic_lp.UpdateUpperBoundOfB();
|
|
ASSERT_TRUE(update);
|
|
|
|
SolveArguments args_2;
|
|
args_2.parameters.enable_output = true;
|
|
|
|
EXPECT_CALL(solver_interface, Update(EquivToProto(*update)))
|
|
.WillOnce(Return(true));
|
|
|
|
ASSERT_OK_AND_ASSIGN(const UpdateResult update_result, solver->Update());
|
|
EXPECT_TRUE(update_result.did_update);
|
|
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver_interface);
|
|
|
|
{
|
|
ASSERT_OK_AND_ASSIGN(const ModelSolveParametersProto model_parameters_2,
|
|
args_2.model_parameters.Proto());
|
|
EXPECT_CALL(
|
|
solver_interface,
|
|
Solve(SolveArgsAre(EquivToProto(args_2.parameters.Proto()),
|
|
EquivToProto(model_parameters_2), Eq(nullptr),
|
|
EquivToProto(args_2.callback_registration.Proto()),
|
|
Eq(nullptr), Eq(nullptr))))
|
|
.WillOnce(Return(basic_lp.OptimalResult({basic_lp.a, basic_lp.b},
|
|
/*after_update=*/true)));
|
|
}
|
|
|
|
ASSERT_OK_AND_ASSIGN(const SolveResult result_2,
|
|
solver->SolveWithoutUpdate(args_2));
|
|
|
|
EXPECT_EQ(result_2.termination.reason, TerminationReason::kOptimal);
|
|
EXPECT_THAT(
|
|
result_2.variable_values(),
|
|
UnorderedElementsAre(Pair(basic_lp.a, 0.0), Pair(basic_lp.b, 2.0)));
|
|
}
|
|
|
|
TEST(IncrementalSolverImplTest, RemoveNamesSendsNoNamesOnModel) {
|
|
Model model;
|
|
model.AddBinaryVariable("x");
|
|
|
|
ModelProto expected_model;
|
|
expected_model.mutable_variables()->add_ids(0);
|
|
expected_model.mutable_variables()->add_lower_bounds(0.0);
|
|
expected_model.mutable_variables()->add_upper_bounds(1.0);
|
|
expected_model.mutable_variables()->add_integers(true);
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver_interface;
|
|
EXPECT_CALL(factory_mock,
|
|
Call(SOLVER_TYPE_GLOP, EquivToProto(expected_model), _))
|
|
.WillOnce(Return(
|
|
ByMove(std::make_unique<DelegatingBaseSolver>(&solver_interface))));
|
|
|
|
EXPECT_OK(IncrementalSolverImpl::New(
|
|
factory_mock.AsStdFunction(), &model, SolverType::kGlop,
|
|
/*user_canceller=*/nullptr, /*remove_names=*/true));
|
|
}
|
|
|
|
TEST(IncrementalSolverImplTest, RemoveNamesSendsNoNamesOnModelUpdate) {
|
|
Model model;
|
|
|
|
SolveArguments args;
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver_interface;
|
|
EXPECT_CALL(factory_mock, Call(SOLVER_TYPE_GLOP, _, _))
|
|
.WillOnce(Return(
|
|
ByMove(std::make_unique<DelegatingBaseSolver>(&solver_interface))));
|
|
|
|
ASSERT_OK_AND_ASSIGN(std::unique_ptr<IncrementalSolver> solver,
|
|
IncrementalSolverImpl::New(factory_mock.AsStdFunction(),
|
|
&model, SolverType::kGlop,
|
|
/*user_canceller=*/nullptr,
|
|
/*remove_names=*/true));
|
|
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver_interface);
|
|
|
|
model.AddBinaryVariable("x");
|
|
|
|
ModelUpdateProto expected_update;
|
|
expected_update.mutable_new_variables()->add_ids(0);
|
|
expected_update.mutable_new_variables()->add_lower_bounds(0.0);
|
|
expected_update.mutable_new_variables()->add_upper_bounds(1.0);
|
|
expected_update.mutable_new_variables()->add_integers(true);
|
|
|
|
EXPECT_CALL(solver_interface, Update(EquivToProto(expected_update)))
|
|
.WillOnce(Return(true));
|
|
|
|
ASSERT_OK_AND_ASSIGN(const UpdateResult update_result, solver->Update());
|
|
EXPECT_TRUE(update_result.did_update);
|
|
}
|
|
|
|
TEST(IncrementalSolverImplTest, RemoveNamesOnFullModelAfterUpdateFails) {
|
|
Model model;
|
|
|
|
SolveArguments args;
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver_interface;
|
|
EXPECT_CALL(factory_mock, Call(SOLVER_TYPE_GLOP, _, _))
|
|
.WillOnce(Return(
|
|
ByMove(std::make_unique<DelegatingBaseSolver>(&solver_interface))));
|
|
|
|
ASSERT_OK_AND_ASSIGN(std::unique_ptr<IncrementalSolver> solver,
|
|
IncrementalSolverImpl::New(factory_mock.AsStdFunction(),
|
|
&model, SolverType::kGlop,
|
|
/*user_canceller=*/nullptr,
|
|
/*remove_names=*/true));
|
|
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver_interface);
|
|
|
|
model.AddBinaryVariable("x");
|
|
|
|
ModelProto expected_model;
|
|
expected_model.mutable_variables()->add_ids(0);
|
|
expected_model.mutable_variables()->add_lower_bounds(0.0);
|
|
expected_model.mutable_variables()->add_upper_bounds(1.0);
|
|
expected_model.mutable_variables()->add_integers(true);
|
|
|
|
EXPECT_CALL(solver_interface, Update(_)).WillOnce(Return(false));
|
|
BaseSolverMock solver_interface2;
|
|
EXPECT_CALL(factory_mock,
|
|
Call(SOLVER_TYPE_GLOP, EquivToProto(expected_model), _))
|
|
.WillOnce(Return(
|
|
ByMove(std::make_unique<DelegatingBaseSolver>(&solver_interface2))));
|
|
|
|
ASSERT_OK_AND_ASSIGN(const UpdateResult update_result, solver->Update());
|
|
EXPECT_FALSE(update_result.did_update);
|
|
}
|
|
|
|
// Test calling IncrementalSolver without any callback with an empty update.
|
|
TEST(IncrementalSolverImplTest, IncrementalSolveWithEmptyUpdate) {
|
|
BasicLp basic_lp;
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver_interface;
|
|
|
|
// The first solve.
|
|
SolveArguments args_1;
|
|
args_1.parameters.enable_output = true;
|
|
args_1.model_parameters =
|
|
ModelSolveParameters::OnlySomePrimalVariables({basic_lp.a});
|
|
|
|
EXPECT_CALL(factory_mock, Call(SOLVER_TYPE_GLOP,
|
|
EquivToProto(basic_lp.model.ExportModel()), _))
|
|
.WillOnce(Return(
|
|
ByMove(std::make_unique<DelegatingBaseSolver>(&solver_interface))));
|
|
|
|
ASSERT_OK_AND_ASSIGN(
|
|
std::unique_ptr<IncrementalSolver> solver,
|
|
IncrementalSolverImpl::New(
|
|
factory_mock.AsStdFunction(), &basic_lp.model, SolverType::kGlop,
|
|
/*user_canceller=*/nullptr, /*remove_names=*/false));
|
|
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver_interface);
|
|
|
|
{
|
|
ASSERT_OK_AND_ASSIGN(const ModelSolveParametersProto model_parameters_1,
|
|
args_1.model_parameters.Proto());
|
|
EXPECT_CALL(
|
|
solver_interface,
|
|
Solve(SolveArgsAre(EquivToProto(args_1.parameters.Proto()),
|
|
EquivToProto(model_parameters_1), Eq(nullptr),
|
|
EquivToProto(args_1.callback_registration.Proto()),
|
|
Eq(nullptr), Eq(nullptr))))
|
|
.WillOnce(Return(basic_lp.OptimalResult({basic_lp.a})));
|
|
}
|
|
|
|
ASSERT_OK_AND_ASSIGN(const SolveResult result_1,
|
|
solver->SolveWithoutUpdate(args_1));
|
|
|
|
EXPECT_EQ(result_1.termination.reason, TerminationReason::kOptimal);
|
|
EXPECT_THAT(result_1.variable_values(),
|
|
UnorderedElementsAre(Pair(basic_lp.a, 0.0)));
|
|
|
|
// Second solve with update.
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver_interface);
|
|
|
|
SolveArguments args_2;
|
|
args_2.parameters.enable_output = true;
|
|
|
|
{
|
|
ASSERT_OK_AND_ASSIGN(const ModelSolveParametersProto model_parameters_2,
|
|
args_2.model_parameters.Proto());
|
|
EXPECT_CALL(
|
|
solver_interface,
|
|
Solve(SolveArgsAre(EquivToProto(args_2.parameters.Proto()),
|
|
EquivToProto(model_parameters_2), Eq(nullptr),
|
|
EquivToProto(args_2.callback_registration.Proto()),
|
|
Eq(nullptr), Eq(nullptr))))
|
|
.WillOnce(Return(basic_lp.OptimalResult({basic_lp.a, basic_lp.b})));
|
|
}
|
|
|
|
ASSERT_OK_AND_ASSIGN(const UpdateResult update_result, solver->Update());
|
|
EXPECT_TRUE(update_result.did_update);
|
|
ASSERT_OK_AND_ASSIGN(const SolveResult result_2,
|
|
solver->SolveWithoutUpdate(args_2));
|
|
|
|
EXPECT_EQ(result_2.termination.reason, TerminationReason::kOptimal);
|
|
EXPECT_THAT(
|
|
result_2.variable_values(),
|
|
UnorderedElementsAre(Pair(basic_lp.a, 0.0), Pair(basic_lp.b, 3.0)));
|
|
}
|
|
|
|
// Test calling IncrementalSolver without any callback and with a failing
|
|
// update; thus resulting in the re-creation of the solver instead.
|
|
TEST(IncrementalSolverImplTest, IncrementalSolveWithFailedUpdate) {
|
|
BasicLp basic_lp;
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver_1;
|
|
|
|
// The first solve.
|
|
SolveArguments args_1;
|
|
args_1.parameters.enable_output = true;
|
|
args_1.model_parameters =
|
|
ModelSolveParameters::OnlySomePrimalVariables({basic_lp.a});
|
|
|
|
EXPECT_CALL(factory_mock, Call(SOLVER_TYPE_GLOP,
|
|
EquivToProto(basic_lp.model.ExportModel()), _))
|
|
.WillOnce(
|
|
Return(ByMove(std::make_unique<DelegatingBaseSolver>(&solver_1))));
|
|
|
|
ASSERT_OK_AND_ASSIGN(
|
|
std::unique_ptr<IncrementalSolver> solver,
|
|
IncrementalSolverImpl::New(
|
|
factory_mock.AsStdFunction(), &basic_lp.model, SolverType::kGlop,
|
|
/*user_canceller=*/nullptr, /*remove_names=*/false));
|
|
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver_1);
|
|
|
|
ASSERT_OK_AND_ASSIGN(const ModelSolveParametersProto model_parameters_1,
|
|
args_1.model_parameters.Proto());
|
|
EXPECT_CALL(solver_1, Solve(SolveArgsAre(
|
|
EquivToProto(args_1.parameters.Proto()),
|
|
EquivToProto(model_parameters_1), Eq(nullptr),
|
|
EquivToProto(args_1.callback_registration.Proto()),
|
|
Eq(nullptr), Eq(nullptr))))
|
|
.WillOnce(Return(basic_lp.OptimalResult({basic_lp.a})));
|
|
|
|
ASSERT_OK_AND_ASSIGN(const SolveResult result_1,
|
|
solver->SolveWithoutUpdate(args_1));
|
|
|
|
EXPECT_EQ(result_1.termination.reason, TerminationReason::kOptimal);
|
|
EXPECT_THAT(result_1.variable_values(),
|
|
UnorderedElementsAre(Pair(basic_lp.a, 0.0)));
|
|
|
|
// Second solve with update.
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver_1);
|
|
|
|
const std::optional<ModelUpdateProto> update = basic_lp.UpdateUpperBoundOfB();
|
|
ASSERT_TRUE(update);
|
|
|
|
SolveArguments args_2;
|
|
args_2.parameters.enable_output = true;
|
|
|
|
BaseSolverMock solver_2;
|
|
|
|
{
|
|
InSequence s;
|
|
|
|
EXPECT_CALL(solver_1, Update(EquivToProto(*update)))
|
|
.WillOnce(Return(false));
|
|
|
|
EXPECT_CALL(
|
|
factory_mock,
|
|
Call(SOLVER_TYPE_GLOP, EquivToProto(basic_lp.model.ExportModel()), _))
|
|
.WillOnce(
|
|
Return(ByMove(std::make_unique<DelegatingBaseSolver>(&solver_2))));
|
|
}
|
|
|
|
ASSERT_OK_AND_ASSIGN(const UpdateResult update_result, solver->Update());
|
|
EXPECT_FALSE(update_result.did_update);
|
|
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver_1);
|
|
Mock::VerifyAndClearExpectations(&solver_2);
|
|
|
|
ASSERT_OK_AND_ASSIGN(const ModelSolveParametersProto model_parameters_2,
|
|
args_2.model_parameters.Proto());
|
|
EXPECT_CALL(solver_2, Solve(SolveArgsAre(
|
|
EquivToProto(args_2.parameters.Proto()),
|
|
EquivToProto(model_parameters_2), Eq(nullptr),
|
|
EquivToProto(args_2.callback_registration.Proto()),
|
|
Eq(nullptr), Eq(nullptr))))
|
|
.WillOnce(Return(basic_lp.OptimalResult({basic_lp.a, basic_lp.b},
|
|
/*after_update=*/true)));
|
|
|
|
ASSERT_OK_AND_ASSIGN(const SolveResult result_2,
|
|
solver->SolveWithoutUpdate(args_2));
|
|
|
|
EXPECT_EQ(result_2.termination.reason, TerminationReason::kOptimal);
|
|
EXPECT_THAT(
|
|
result_2.variable_values(),
|
|
UnorderedElementsAre(Pair(basic_lp.a, 0.0), Pair(basic_lp.b, 2.0)));
|
|
}
|
|
|
|
// Test calling IncrementalSolver without any callback and with an impossible
|
|
// update, i.e. an update that contains an unsupported feature.
|
|
TEST(IncrementalSolverImplTest, IncrementalSolveWithImpossibleUpdate) {
|
|
BasicLp basic_lp;
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver_1;
|
|
|
|
// The first solve.
|
|
SolveArguments args_1;
|
|
args_1.parameters.enable_output = true;
|
|
args_1.model_parameters =
|
|
ModelSolveParameters::OnlySomePrimalVariables({basic_lp.a});
|
|
|
|
EXPECT_CALL(factory_mock, Call(SOLVER_TYPE_GLOP,
|
|
EquivToProto(basic_lp.model.ExportModel()), _))
|
|
.WillOnce(
|
|
Return(ByMove(std::make_unique<DelegatingBaseSolver>(&solver_1))));
|
|
|
|
ASSERT_OK_AND_ASSIGN(
|
|
std::unique_ptr<IncrementalSolver> solver,
|
|
IncrementalSolverImpl::New(
|
|
factory_mock.AsStdFunction(), &basic_lp.model, SolverType::kGlop,
|
|
/*user_canceller=*/nullptr, /*remove_names=*/false));
|
|
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver_1);
|
|
|
|
ASSERT_OK_AND_ASSIGN(const ModelSolveParametersProto model_parameters_1,
|
|
args_1.model_parameters.Proto());
|
|
EXPECT_CALL(solver_1, Solve(SolveArgsAre(
|
|
EquivToProto(args_1.parameters.Proto()),
|
|
EquivToProto(model_parameters_1), Eq(nullptr),
|
|
EquivToProto(args_1.callback_registration.Proto()),
|
|
Eq(nullptr), Eq(nullptr))))
|
|
.WillOnce(Return(basic_lp.OptimalResult({basic_lp.a})));
|
|
|
|
ASSERT_OK_AND_ASSIGN(const SolveResult result_1,
|
|
solver->SolveWithoutUpdate(args_1));
|
|
|
|
EXPECT_EQ(result_1.termination.reason, TerminationReason::kOptimal);
|
|
EXPECT_THAT(result_1.variable_values(),
|
|
UnorderedElementsAre(Pair(basic_lp.a, 0.0)));
|
|
|
|
// Update.
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver_1);
|
|
|
|
const std::optional<ModelUpdateProto> update = basic_lp.UpdateUpperBoundOfB();
|
|
ASSERT_TRUE(update);
|
|
|
|
SolveArguments args_2;
|
|
args_2.parameters.enable_output = true;
|
|
|
|
{
|
|
InSequence s;
|
|
|
|
// The solver will refuse the update with the unsupported feature.
|
|
EXPECT_CALL(solver_1, Update(EquivToProto(*update)))
|
|
.WillOnce(Return(false));
|
|
|
|
// The solver factory will fail for the same reason.
|
|
EXPECT_CALL(
|
|
factory_mock,
|
|
Call(SOLVER_TYPE_GLOP, EquivToProto(basic_lp.model.ExportModel()), _))
|
|
.WillOnce(Return(ByMove(absl::InternalError("*unsupported model*"))));
|
|
}
|
|
|
|
ASSERT_THAT(solver->Update(),
|
|
StatusIs(absl::StatusCode::kInternal,
|
|
AllOf(HasSubstr("*unsupported model*"),
|
|
HasSubstr("solver re-creation failed"))));
|
|
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver_1);
|
|
|
|
// Next calls should fail and not crash. Note that since we failed recreating
|
|
// a new solver we still will use solver_1; and this solver will return an
|
|
// error.
|
|
|
|
EXPECT_CALL(solver_1, Update(_))
|
|
.WillOnce(
|
|
Return(ByMove(absl::InvalidArgumentError("previous call failed"))));
|
|
|
|
basic_lp.model.set_lower_bound(basic_lp.a, -3.0);
|
|
EXPECT_THAT(solver->Update(), StatusIs(absl::StatusCode::kInvalidArgument,
|
|
HasSubstr("update failed")));
|
|
}
|
|
|
|
// Test calling IncrementalSolver with a callback. We don't test calling
|
|
// Update() here since only the Solve() function takes a callback.
|
|
TEST(IncrementalSolverImplTest, SuccessfulSolveWithCallback) {
|
|
BasicLp basic_lp;
|
|
|
|
SolveArguments args;
|
|
args.parameters.enable_output = true;
|
|
|
|
args.model_parameters =
|
|
ModelSolveParameters::OnlySomePrimalVariables({basic_lp.a});
|
|
|
|
args.callback_registration.add_lazy_constraints = true;
|
|
args.callback_registration.events.insert(CallbackEvent::kMipSolution);
|
|
|
|
const auto fake_solve = [&](const BaseSolver::SolveArgs& args)
|
|
-> absl::StatusOr<SolveResultProto> {
|
|
CallbackDataProto cb_data;
|
|
cb_data.set_event(CALLBACK_EVENT_MIP_SOLUTION);
|
|
*cb_data.mutable_primal_solution_vector() = MakeSparseDoubleVector(
|
|
{{basic_lp.a.id(), 1.0}, {basic_lp.b.id(), 0.0}});
|
|
args.user_cb(cb_data);
|
|
return basic_lp.OptimalResult({basic_lp.a});
|
|
};
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver_interface;
|
|
|
|
EXPECT_CALL(
|
|
factory_mock,
|
|
|
|
Call(SOLVER_TYPE_GLOP, EquivToProto(basic_lp.model.ExportModel()), _))
|
|
.WillOnce(Return(
|
|
ByMove(std::make_unique<DelegatingBaseSolver>(&solver_interface))));
|
|
|
|
ASSERT_OK_AND_ASSIGN(
|
|
std::unique_ptr<IncrementalSolver> solver,
|
|
IncrementalSolverImpl::New(
|
|
factory_mock.AsStdFunction(), &basic_lp.model, SolverType::kGlop,
|
|
/*user_canceller=*/nullptr, /*remove_names=*/false));
|
|
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver_interface);
|
|
|
|
ASSERT_OK_AND_ASSIGN(const ModelSolveParametersProto model_parameters,
|
|
args.model_parameters.Proto());
|
|
EXPECT_CALL(
|
|
solver_interface,
|
|
Solve(SolveArgsAre(EquivToProto(args.parameters.Proto()),
|
|
EquivToProto(model_parameters), Eq(nullptr),
|
|
EquivToProto(args.callback_registration.Proto()),
|
|
Ne(nullptr), Eq(nullptr))))
|
|
.WillOnce(fake_solve);
|
|
|
|
int callback_called_count = 0;
|
|
args.callback = [&](const CallbackData& callback_data) {
|
|
++callback_called_count;
|
|
CallbackResult result;
|
|
result.AddLazyConstraint(basic_lp.a + basic_lp.b <= 3);
|
|
return result;
|
|
};
|
|
ASSERT_OK_AND_ASSIGN(const SolveResult result,
|
|
solver->SolveWithoutUpdate(args));
|
|
|
|
EXPECT_EQ(callback_called_count, 1);
|
|
EXPECT_EQ(result.termination.reason, TerminationReason::kOptimal);
|
|
EXPECT_THAT(result.variable_values(),
|
|
UnorderedElementsAre(Pair(basic_lp.a, 0.0)));
|
|
}
|
|
|
|
// Test calling IncrementalSolver with a solver that fails to returns the
|
|
// SolverInterface for a given model.
|
|
TEST(IncrementalSolverImplTest, FailingSolverInstantiation) {
|
|
BasicLp basic_lp;
|
|
|
|
SolveArguments args;
|
|
args.parameters.enable_output = true;
|
|
|
|
args.model_parameters =
|
|
ModelSolveParameters::OnlySomePrimalVariables({basic_lp.a});
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver_interface;
|
|
EXPECT_CALL(factory_mock, Call(SOLVER_TYPE_GLOP,
|
|
EquivToProto(basic_lp.model.ExportModel()), _))
|
|
.WillOnce(Return(ByMove(absl::InternalError("instantiation failed"))));
|
|
|
|
ASSERT_THAT(IncrementalSolverImpl::New(factory_mock.AsStdFunction(),
|
|
&basic_lp.model, SolverType::kGlop,
|
|
/*user_canceller=*/nullptr,
|
|
/*remove_names=*/false),
|
|
StatusIs(absl::StatusCode::kInternal, "instantiation failed"));
|
|
}
|
|
|
|
// Test calling IncrementalSolver with a solver that returns an error on
|
|
// SolverInterface::Solve().
|
|
TEST(IncrementalSolverImplTest, FailingSolver) {
|
|
BasicLp basic_lp;
|
|
|
|
SolveArguments args;
|
|
args.parameters.enable_output = true;
|
|
|
|
args.model_parameters =
|
|
ModelSolveParameters::OnlySomePrimalVariables({basic_lp.a});
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver_interface;
|
|
|
|
EXPECT_CALL(factory_mock, Call(SOLVER_TYPE_GLOP,
|
|
EquivToProto(basic_lp.model.ExportModel()), _))
|
|
.WillOnce(Return(
|
|
ByMove(std::make_unique<DelegatingBaseSolver>(&solver_interface))));
|
|
|
|
ASSERT_OK_AND_ASSIGN(
|
|
std::unique_ptr<IncrementalSolver> solver,
|
|
IncrementalSolverImpl::New(
|
|
factory_mock.AsStdFunction(), &basic_lp.model, SolverType::kGlop,
|
|
/*user_canceller=*/nullptr, /*remove_names=*/false));
|
|
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver_interface);
|
|
|
|
ASSERT_OK_AND_ASSIGN(const ModelSolveParametersProto model_parameters,
|
|
args.model_parameters.Proto());
|
|
EXPECT_CALL(
|
|
solver_interface,
|
|
Solve(SolveArgsAre(EquivToProto(args.parameters.Proto()),
|
|
EquivToProto(model_parameters), Eq(nullptr),
|
|
EquivToProto(args.callback_registration.Proto()),
|
|
Eq(nullptr), Eq(nullptr))))
|
|
.WillOnce(Return(absl::InternalError("solve failed")));
|
|
|
|
ASSERT_THAT(solver->SolveWithoutUpdate(args),
|
|
StatusIs(absl::StatusCode::kInternal, "solve failed"));
|
|
}
|
|
|
|
// Test calling IncrementalSolver with a solver that returns an error on
|
|
// SolverInterface::Update().
|
|
TEST(IncrementalSolverImplTest, FailingSolverUpdate) {
|
|
BasicLp basic_lp;
|
|
|
|
SolveArguments args;
|
|
args.parameters.enable_output = true;
|
|
|
|
args.model_parameters =
|
|
ModelSolveParameters::OnlySomePrimalVariables({basic_lp.a});
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver_interface;
|
|
|
|
EXPECT_CALL(factory_mock, Call(SOLVER_TYPE_GLOP,
|
|
EquivToProto(basic_lp.model.ExportModel()), _))
|
|
.WillOnce(Return(
|
|
ByMove(std::make_unique<DelegatingBaseSolver>(&solver_interface))));
|
|
|
|
ASSERT_OK_AND_ASSIGN(
|
|
std::unique_ptr<IncrementalSolver> solver,
|
|
IncrementalSolverImpl::New(
|
|
factory_mock.AsStdFunction(), &basic_lp.model, SolverType::kGlop,
|
|
/*user_canceller=*/nullptr, /*remove_names=*/false));
|
|
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver_interface);
|
|
|
|
const std::optional<ModelUpdateProto> update = basic_lp.UpdateUpperBoundOfB();
|
|
ASSERT_TRUE(update);
|
|
|
|
EXPECT_CALL(solver_interface, Update(EquivToProto(*update)))
|
|
.WillOnce(Return(absl::InternalError("*update failure*")));
|
|
|
|
ASSERT_THAT(solver->Update(), StatusIs(absl::StatusCode::kInternal,
|
|
AllOf(HasSubstr("*update failure*"),
|
|
HasSubstr("update failed"))));
|
|
}
|
|
|
|
// Test calling IncrementalSolver::Solve() with a callback and a non trivial
|
|
// update.
|
|
TEST(IncrementalSolverImplTest, UpdateAndSolve) {
|
|
BasicLp basic_lp;
|
|
|
|
SolveArguments args;
|
|
args.parameters.enable_output = true;
|
|
|
|
args.model_parameters =
|
|
ModelSolveParameters::OnlySomePrimalVariables({basic_lp.a});
|
|
|
|
args.callback_registration.add_lazy_constraints = true;
|
|
args.callback_registration.events.insert(CallbackEvent::kMipSolution);
|
|
|
|
const auto fake_solve = [&](const BaseSolver::SolveArgs& args)
|
|
-> absl::StatusOr<SolveResultProto> {
|
|
CallbackDataProto cb_data;
|
|
cb_data.set_event(CALLBACK_EVENT_MIP_SOLUTION);
|
|
*cb_data.mutable_primal_solution_vector() = MakeSparseDoubleVector(
|
|
{{basic_lp.a.id(), 1.0}, {basic_lp.b.id(), 0.0}});
|
|
args.user_cb(cb_data);
|
|
return basic_lp.OptimalResult({basic_lp.a});
|
|
};
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver_interface;
|
|
|
|
EXPECT_CALL(
|
|
factory_mock,
|
|
|
|
Call(SOLVER_TYPE_GLOP, EquivToProto(basic_lp.model.ExportModel()), _))
|
|
.WillOnce(Return(
|
|
ByMove(std::make_unique<DelegatingBaseSolver>(&solver_interface))));
|
|
|
|
ASSERT_OK_AND_ASSIGN(
|
|
std::unique_ptr<IncrementalSolver> solver,
|
|
IncrementalSolverImpl::New(
|
|
factory_mock.AsStdFunction(), &basic_lp.model, SolverType::kGlop,
|
|
/*user_canceller=*/nullptr, /*remove_names=*/false));
|
|
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver_interface);
|
|
|
|
// Update the model before calling Solve().
|
|
const std::optional<ModelUpdateProto> update = basic_lp.UpdateUpperBoundOfB();
|
|
ASSERT_TRUE(update);
|
|
|
|
{
|
|
InSequence s;
|
|
|
|
EXPECT_CALL(solver_interface, Update(EquivToProto(*update)))
|
|
.WillOnce(Return(true));
|
|
ASSERT_OK_AND_ASSIGN(const ModelSolveParametersProto model_parameters,
|
|
args.model_parameters.Proto());
|
|
EXPECT_CALL(
|
|
solver_interface,
|
|
Solve(SolveArgsAre(EquivToProto(args.parameters.Proto()),
|
|
EquivToProto(model_parameters), Eq(nullptr),
|
|
EquivToProto(args.callback_registration.Proto()),
|
|
Ne(nullptr), Eq(nullptr))))
|
|
.WillOnce(fake_solve);
|
|
}
|
|
|
|
int callback_called_count = 0;
|
|
args.callback = [&](const CallbackData& callback_data) {
|
|
++callback_called_count;
|
|
CallbackResult result;
|
|
result.AddLazyConstraint(basic_lp.a + basic_lp.b <= 3);
|
|
return result;
|
|
};
|
|
ASSERT_OK_AND_ASSIGN(const SolveResult result, solver->Solve(args));
|
|
|
|
EXPECT_EQ(callback_called_count, 1);
|
|
EXPECT_EQ(result.termination.reason, TerminationReason::kOptimal);
|
|
EXPECT_THAT(result.variable_values(),
|
|
UnorderedElementsAre(Pair(basic_lp.a, 0.0)));
|
|
}
|
|
|
|
// Test calling IncrementalSolver::Solve() with a solver that returns an error
|
|
// on SolverInterface::Solve().
|
|
TEST(IncrementalSolverImplTest, UpdateAndSolveWithFailingSolver) {
|
|
BasicLp basic_lp;
|
|
|
|
SolveArguments args;
|
|
args.parameters.enable_output = true;
|
|
|
|
args.model_parameters =
|
|
ModelSolveParameters::OnlySomePrimalVariables({basic_lp.a});
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver_interface;
|
|
|
|
EXPECT_CALL(factory_mock, Call(SOLVER_TYPE_GLOP,
|
|
EquivToProto(basic_lp.model.ExportModel()), _))
|
|
.WillOnce(Return(
|
|
ByMove(std::make_unique<DelegatingBaseSolver>(&solver_interface))));
|
|
|
|
ASSERT_OK_AND_ASSIGN(
|
|
std::unique_ptr<IncrementalSolver> solver,
|
|
IncrementalSolverImpl::New(
|
|
factory_mock.AsStdFunction(), &basic_lp.model, SolverType::kGlop,
|
|
/*user_canceller=*/nullptr, /*remove_names=*/false));
|
|
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver_interface);
|
|
|
|
ASSERT_OK_AND_ASSIGN(const ModelSolveParametersProto model_parameters,
|
|
args.model_parameters.Proto());
|
|
EXPECT_CALL(
|
|
solver_interface,
|
|
Solve(SolveArgsAre(EquivToProto(args.parameters.Proto()),
|
|
EquivToProto(model_parameters), Eq(nullptr),
|
|
EquivToProto(args.callback_registration.Proto()),
|
|
Eq(nullptr), Eq(nullptr))))
|
|
.WillOnce(Return(absl::InternalError("solve failed")));
|
|
|
|
ASSERT_THAT(solver->Solve(args),
|
|
StatusIs(absl::StatusCode::kInternal, "solve failed"));
|
|
}
|
|
|
|
// Test calling IncrementalSolver::Solve() with a solver that returns an error
|
|
// on SolverInterface::Update().
|
|
TEST(IncrementalSolverImplTest, UpdateAndSolveWithFailingSolverUpdate) {
|
|
BasicLp basic_lp;
|
|
|
|
SolveArguments args;
|
|
args.parameters.enable_output = true;
|
|
|
|
args.model_parameters =
|
|
ModelSolveParameters::OnlySomePrimalVariables({basic_lp.a});
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver_interface;
|
|
|
|
EXPECT_CALL(factory_mock, Call(SOLVER_TYPE_GLOP,
|
|
EquivToProto(basic_lp.model.ExportModel()), _))
|
|
.WillOnce(Return(
|
|
ByMove(std::make_unique<DelegatingBaseSolver>(&solver_interface))));
|
|
|
|
ASSERT_OK_AND_ASSIGN(
|
|
std::unique_ptr<IncrementalSolver> solver,
|
|
IncrementalSolverImpl::New(
|
|
factory_mock.AsStdFunction(), &basic_lp.model, SolverType::kGlop,
|
|
/*user_canceller=*/nullptr, /*remove_names=*/false));
|
|
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver_interface);
|
|
|
|
const std::optional<ModelUpdateProto> update = basic_lp.UpdateUpperBoundOfB();
|
|
ASSERT_TRUE(update);
|
|
|
|
EXPECT_CALL(solver_interface, Update(EquivToProto(*update)))
|
|
.WillOnce(Return(absl::InternalError("*update failure*")));
|
|
|
|
ASSERT_THAT(solver->Solve({}), StatusIs(absl::StatusCode::kInternal,
|
|
AllOf(HasSubstr("*update failure*"),
|
|
HasSubstr("update failed"))));
|
|
}
|
|
|
|
TEST(IncrementalSolverImplTest, WrongModelInModelParameters) {
|
|
BasicLp basic_lp;
|
|
BasicLp other_basic_lp;
|
|
|
|
SolveArguments args;
|
|
args.parameters.enable_output = true;
|
|
|
|
// Here we use the wrong variable.
|
|
args.model_parameters =
|
|
ModelSolveParameters::OnlySomePrimalVariables({other_basic_lp.a});
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver_interface;
|
|
|
|
EXPECT_CALL(factory_mock, Call(SOLVER_TYPE_GLOP,
|
|
EquivToProto(basic_lp.model.ExportModel()), _))
|
|
.WillOnce(Return(
|
|
ByMove(std::make_unique<DelegatingBaseSolver>(&solver_interface))));
|
|
|
|
ASSERT_OK_AND_ASSIGN(
|
|
std::unique_ptr<IncrementalSolver> solver,
|
|
IncrementalSolverImpl::New(
|
|
factory_mock.AsStdFunction(), &basic_lp.model, SolverType::kGlop,
|
|
/*user_canceller=*/nullptr, /*remove_names=*/false));
|
|
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver_interface);
|
|
|
|
EXPECT_THAT(solver->SolveWithoutUpdate(args),
|
|
StatusIs(absl::StatusCode::kInvalidArgument,
|
|
HasSubstr(internal::kInputFromInvalidModelStorage)));
|
|
}
|
|
|
|
TEST(IncrementalSolverImplTest, WrongModelInCallbackRegistration) {
|
|
BasicLp basic_lp;
|
|
BasicLp other_basic_lp;
|
|
|
|
SolveArguments args;
|
|
args.parameters.enable_output = true;
|
|
|
|
// Here we use the wrong variable.
|
|
args.callback_registration.mip_solution_filter =
|
|
MakeKeepKeysFilter({other_basic_lp.a});
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver_interface;
|
|
|
|
EXPECT_CALL(
|
|
factory_mock,
|
|
|
|
Call(SOLVER_TYPE_GLOP, EquivToProto(basic_lp.model.ExportModel()), _))
|
|
.WillOnce(Return(
|
|
ByMove(std::make_unique<DelegatingBaseSolver>(&solver_interface))));
|
|
|
|
ASSERT_OK_AND_ASSIGN(
|
|
std::unique_ptr<IncrementalSolver> solver,
|
|
IncrementalSolverImpl::New(
|
|
factory_mock.AsStdFunction(), &basic_lp.model, SolverType::kGlop,
|
|
/*user_canceller=*/nullptr, /*remove_names=*/false));
|
|
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver_interface);
|
|
|
|
EXPECT_THAT(solver->SolveWithoutUpdate(args),
|
|
StatusIs(absl::StatusCode::kInvalidArgument,
|
|
HasSubstr(internal::kInputFromInvalidModelStorage)));
|
|
}
|
|
|
|
TEST(IncrementalSolverImplTest, WrongModelInCallbackResult) {
|
|
BasicLp basic_lp;
|
|
BasicLp other_basic_lp;
|
|
|
|
SolveArguments args;
|
|
args.parameters.enable_output = true;
|
|
|
|
args.callback_registration.add_lazy_constraints = true;
|
|
args.callback_registration.events.insert(CallbackEvent::kMipSolution);
|
|
|
|
const auto fake_solve = [&](const BaseSolver::SolveArgs& args)
|
|
-> absl::StatusOr<SolveResultProto> {
|
|
CallbackDataProto cb_data;
|
|
cb_data.set_event(CALLBACK_EVENT_MIP_SOLUTION);
|
|
*cb_data.mutable_primal_solution_vector() = MakeSparseDoubleVector(
|
|
{{basic_lp.a.id(), 1.0}, {basic_lp.b.id(), 0.0}});
|
|
args.user_cb(cb_data);
|
|
return basic_lp.OptimalResult({basic_lp.a, basic_lp.b});
|
|
};
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver_interface;
|
|
|
|
args.callback = [&](const CallbackData& callback_data) {
|
|
CallbackResult result;
|
|
// We use the wrong model here.
|
|
result.AddLazyConstraint(other_basic_lp.a + other_basic_lp.b <= 3);
|
|
return result;
|
|
};
|
|
|
|
EXPECT_CALL(factory_mock, Call(SOLVER_TYPE_GLOP,
|
|
EquivToProto(basic_lp.model.ExportModel()), _))
|
|
.WillOnce(Return(
|
|
ByMove(std::make_unique<DelegatingBaseSolver>(&solver_interface))));
|
|
|
|
ASSERT_OK_AND_ASSIGN(
|
|
std::unique_ptr<IncrementalSolver> solver,
|
|
IncrementalSolverImpl::New(
|
|
factory_mock.AsStdFunction(), &basic_lp.model, SolverType::kGlop,
|
|
/*user_canceller=*/nullptr, /*remove_names=*/false));
|
|
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver_interface);
|
|
|
|
ASSERT_OK_AND_ASSIGN(const ModelSolveParametersProto model_parameters,
|
|
args.model_parameters.Proto());
|
|
EXPECT_CALL(
|
|
solver_interface,
|
|
Solve(SolveArgsAre(EquivToProto(args.parameters.Proto()),
|
|
EquivToProto(model_parameters), Eq(nullptr),
|
|
EquivToProto(args.callback_registration.Proto()),
|
|
Ne(nullptr), Eq(nullptr))))
|
|
.WillOnce(fake_solve);
|
|
|
|
EXPECT_THAT(solver->SolveWithoutUpdate(args),
|
|
StatusIs(absl::StatusCode::kInvalidArgument,
|
|
HasSubstr(internal::kInputFromInvalidModelStorage)));
|
|
}
|
|
|
|
TEST(IncrementalSolverImplTest, ComputeInfeasibleSubsystem) {
|
|
BasicInfeasibleLp lp;
|
|
|
|
BaseSolverMock solver_interface;
|
|
|
|
// The first computation.
|
|
ComputeInfeasibleSubsystemArguments args_1;
|
|
args_1.parameters.enable_output = true;
|
|
|
|
SolveInterrupter interrupter;
|
|
args_1.interrupter = &interrupter;
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
EXPECT_CALL(factory_mock,
|
|
Call(SOLVER_TYPE_GLOP, EquivToProto(lp.model.ExportModel()), _))
|
|
.WillOnce(Return(
|
|
ByMove(std::make_unique<DelegatingBaseSolver>(&solver_interface))));
|
|
|
|
ASSERT_OK_AND_ASSIGN(std::unique_ptr<IncrementalSolver> solver,
|
|
IncrementalSolverImpl::New(factory_mock.AsStdFunction(),
|
|
&lp.model, SolverType::kGlop,
|
|
/*user_canceller=*/nullptr,
|
|
/*remove_names=*/false));
|
|
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver_interface);
|
|
|
|
EXPECT_CALL(solver_interface,
|
|
ComputeInfeasibleSubsystem(ComputeInfeasibleSubsystemArgsAre(
|
|
EquivToProto(args_1.parameters.Proto()), Eq(nullptr),
|
|
Eq(&interrupter))))
|
|
.WillOnce(Return(lp.InfeasibleResult()));
|
|
|
|
{
|
|
ASSERT_OK_AND_ASSIGN(
|
|
const ComputeInfeasibleSubsystemResult result,
|
|
solver->ComputeInfeasibleSubsystemWithoutUpdate(args_1));
|
|
EXPECT_EQ(result.feasibility, FeasibilityStatus::kInfeasible);
|
|
}
|
|
|
|
// Second computation with update.
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver_interface);
|
|
|
|
const std::optional<ModelUpdateProto> update = lp.UpdateUpperBoundOfC();
|
|
ASSERT_TRUE(update);
|
|
|
|
ComputeInfeasibleSubsystemArguments args_2;
|
|
args_2.parameters.enable_output = true;
|
|
|
|
{
|
|
InSequence s;
|
|
|
|
EXPECT_CALL(solver_interface, Update(EquivToProto(*update)))
|
|
.WillOnce(Return(true));
|
|
|
|
EXPECT_CALL(
|
|
solver_interface,
|
|
ComputeInfeasibleSubsystem(ComputeInfeasibleSubsystemArgsAre(
|
|
EquivToProto(args_2.parameters.Proto()), Eq(nullptr), Eq(nullptr))))
|
|
.WillOnce(Return(lp.InfeasibleResult()));
|
|
}
|
|
|
|
ASSERT_OK_AND_ASSIGN(const ComputeInfeasibleSubsystemResult result,
|
|
solver->ComputeInfeasibleSubsystem(args_2));
|
|
EXPECT_EQ(result.feasibility, FeasibilityStatus::kInfeasible);
|
|
}
|
|
|
|
TEST(IncrementalSolverImplTest, UserCancellation) {
|
|
BasicLp basic_lp;
|
|
|
|
// Will be set to the provided local_canceller in the factory.
|
|
SolveInterrupter* provided_local_canceller = nullptr;
|
|
|
|
BaseSolverFactoryMock factory_mock;
|
|
BaseSolverMock solver;
|
|
|
|
EXPECT_CALL(factory_mock, Call(SOLVER_TYPE_GLOP, _, Ne(nullptr)))
|
|
.WillOnce([&](const SolverTypeProto solver_type, const ModelProto& model,
|
|
SolveInterrupter* const local_canceller) {
|
|
provided_local_canceller = local_canceller;
|
|
return std::make_unique<DelegatingBaseSolver>(&solver);
|
|
});
|
|
|
|
SolveInterrupter user_canceller;
|
|
|
|
ASSERT_OK_AND_ASSIGN(
|
|
const std::unique_ptr<IncrementalSolver> incremental_solver,
|
|
IncrementalSolverImpl::New(factory_mock.AsStdFunction(), &basic_lp.model,
|
|
SolverType::kGlop,
|
|
/*user_canceller=*/&user_canceller,
|
|
/*remove_names=*/false));
|
|
|
|
Mock::VerifyAndClearExpectations(&factory_mock);
|
|
Mock::VerifyAndClearExpectations(&solver);
|
|
|
|
ASSERT_NE(provided_local_canceller, nullptr);
|
|
|
|
// Since user_canceller has not been cancelled yet the local canceller should
|
|
// still be untriggered.
|
|
EXPECT_FALSE(provided_local_canceller->IsInterrupted());
|
|
|
|
// Triggering the user canceller should trigger the local canceller.
|
|
user_canceller.Interrupt();
|
|
EXPECT_TRUE(provided_local_canceller->IsInterrupted());
|
|
}
|
|
|
|
} // namespace
|
|
} // namespace operations_research::math_opt::internal
|