Math Opt API

[Mark]

Just saw the new Math Opt API in this commit:

https://github.com/google/or-tools/commit/b9e5d2e5558ab72693623eb4007ff3851e0a8c42

and examples here:

https://github.com/google/or-tools/tree/master/ortools/math_opt/samples

Looks like this is focused on making incremental updates easier and more portable.  Is this meant as a stand-alone addition, or is it part of / prerequisite for something bigger?  Just curious about the motivations for what looks like a really useful addition to ORTools.

[Ross Anderson]

You are correct, better supporting incrementalism is one of the primary motivations for MathOpt. A few other goals include supporting callbacks, nonlinearities, reducing the SWIGed surface area, and not making users call generated (SWIG) code directly.

The project is in a very early phase. It isn't really documented and will continue to have breaking changes. I would recommend users stick with MPSolver or the MPModelProto API instead for the time being.

[Mark]

Just curious as to the status of this.

[Ross Anderson]

The C++ API is now reasonably stable, and well used/tested internally. We are actively working on java/python language support. We haven't created public documentation yet (beyond the inline comments, although these are generally pretty detailed).

Our unit tests are generally not exported, and as the API is not used much externally, you may find some rough edges/issues with the exported code.

[Ethan]

Dear all, 

I am trying to porting the benders algorithm [1] using Python wrapper.
But I get stuck in the following function.

I cannot find a suitable mapping from the C++ code to the Python code.
Could you give me some hints about the implementation following C++ functions in ortools Python:

1. second_stage_result.ray_reduced_costs()
2. second_stage_result.ray_dual_values()


Thank you very much.

//////////////
absl::StatusOr<Cut> SecondStageSolver::FeasibilityCut(
    const math_opt::SolveResult& second_stage_result) {
  const int num_facilities = network_.num_facilities();
  Cut result;

  if (!second_stage_result.has_dual_ray()) {
    // MathOpt does not require solvers to return a dual solution on optimal,
    // but most LP solvers always will, see go/mathopt-solver-contracts for
    // details.
    return util::InternalErrorBuilder()
           << "no dual ray available for feasibility cut";
  }

  for (int facility = 0; facility < num_facilities; ++facility) {
    double coefficient = 0.0;
    for (const auto& edge : network_.edges_incident_to_facility(facility)) {
      const double reduced_cost =
          second_stage_result.ray_reduced_costs().at(x_.at(edge));
      coefficient += location_fraction_ * std::min(reduced_cost, 0.0);
    }
    const double dual_value =
        second_stage_result.ray_dual_values().at(supply_constraints_[facility]);
    coefficient += std::min(dual_value, 0.0);
    result.z_coefficients.push_back(coefficient);
  }
  result.constant = 0.0;
  for (const auto& constraint : demand_constraints_) {
    const double dual_value =
        second_stage_result.ray_dual_values().at(constraint);
    result.constant += std::max(dual_value, 0.0);
  }
  result.w_coefficient = 0.0;
  return result;
}

[1] https://github.com/google/or-tools/blob/master/ortools/math_opt/samples/facility_lp_benders_mo.cc

ran...@google.com 在 2023年3月8日 星期三晚上11:59:22 [UTC+8] 的信中寫道：

[Ross Anderson]

Presumably you are using the python bindings for linear_solver.h/MPSolver (pywraplp as seen here). The MathOpt python bindings are not available in open source yet.

I believe that MPSolver does not support getting dual rays. So it is not possible to do what you want.

I would suggest the following:

• Formulate your problem so that your stage two problem cannot be infeasible. Then you don't need this feature.
• Wait for MathOpt's Python bindings to be released (probably not too long from now), or use MathOpt's C++ bindings
• If you are using Gurobi's python API directly, you can get the dual ray. HiGHS also has a Python API that hopefully has this feature (glop does not have a python API).
• If you need solver independent modeling, you can try looking at various alternatives to ortools (e.g. CVX) although I do not know which of them support infeasibility certificates.

[Ethan]

Hi Ross,

Thank you. Yes, I am using the python bindings (linear_solver.h/MPSolver).

I will try MathOpt's C++ bindings. And if it is not OK, to integrate the C++ part into my python framework , I will reformulate the subproblems.

ran...@google.com 在 2023年10月10日 星期二晚上10:17:13 [UTC+8] 的信中寫道：

[Mark]

Very impressed by what was just made public for the mathopt interface:  https://github.com/google/or-tools/commit/84962a42817ef182a7f043af526e821018d8d49c

Do the python bindings suffer from the same 2 GB protobuf serialization limit as all the other python bindings (presumably yes)?

Mostly asking because mathopt has callbacks and other features suitable for decompositions, and decompositions are typically used for large models, so just wanted to clarify whether it would be wise to spend one's time familiarising oneself with the c++ api over the python api in such cases.

[Laurent Perron]

yes for the 2GB.

Happy you like it.

I would recommend C++ as this is the most used API internally.

I will make a stand-alone post about it, but this gist is:
  - Next OR-Tools release will be 10.0

  - MPSolver is deprecated.

  - ModelBuilder (Python, Java, .NET) is available. This is for simple solve as there is no support for fast incremental solve (you can update the model, but the solver state is lost)

  - MathOpt will be available for Python and C++. Java will follow. C# will most likely never be implemented

  - Currently MathOpt is supported with bazel. We need to work to make it available with cmake.

and

  - CP-SAT python will be rewritten for PEP8 (snake case names) with compatibility + sed script.

  - Lots of cleaning on the graph APIs

  

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/75825aca-acae-4a26-85f6-62e6847f5ac5n%40googlegroups.com.

[Mark]

Just saw this commit suggesting that the python protobufs are being removed in favor of proxies on the c++ protobufs.

https://github.com/google/or-tools/commit/e5dc796ef6bdb146fb7f47855fd3a935efe89e44

Does this remove the 2 GB limit on the python CP-SAT interface?

Also while I'm here on this thread, probably a good time to ask about an update on the status of MathOpt since the last post is a year and a half old.

[Laurent Perron]

Yes it does for CP-SAT 

Math-opt python api should be stable in 9.14

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/67ea2a31-b8f8-4a34-898c-9c99672e853fn%40googlegroups.com.