Questions about usage

[Darin Goldstein]

First, thank you so much for creating such a useful tool. I had some questions that I hope you could answer because I could not find them in the documentation. I am using the C++ version of ortools version 9.3 in Windows. (If there is no way to do these things yet, then that's fine. It would just be good to know.)

I'm specifically using the PDLP features of version 9.3 for all of these questions.

1. If I want to stop iterating after a certain time limit regardless of whether one knows whether a solution exists, how does one accomplish that?

2. Which C++ file holds the inner loop of the computation? I would like to take a look at possibly improving the code/speeding up the algorithm for my particular situation (unlikely to be of any help to anyone but me so I won't bore you with details unless you want them), and it would be a great help to know where the inner loop is. (see below)

3. You are probably already aware of this, but just in case you're not, Boyd et al. came out with another paper a few years ago for termination criteria for infeasibility. I've been trying out ortools on my application, and it finds a solution extremely quickly should one exist (well done, by the way), but whenever there is an infeasibility, it takes the algorithm some time to recognize it. This paper presents some stopping criteria: https://stanford.edu/~boyd/papers/pdf/admm_infeas.pdf (I would attempt to implement it myself, but I'm not sure if you're specifically using ADMM because I can't find the inner loop.)

4. How can you set the primal and dual thresholds? Is there a way to do this within MPSolverParameters and then pass them into the MPSolver?

Again, my compliments on PDLP. It is excellent work, D

[Darin Goldstein]

I believe that I've found the inner loop in primal_dual_hybrid_gradient (and I don't believe that you're using ADMM; if I'm wrong, please correct me). It would be great to get an answer to my questions 1 and 4 though. Thanks, D

[Miles Lubin]

Questions 1 and 4: PDLP's parameters are encoded in the PrimalDualHybridGradientParams message. An example of non-default termination criteria are:

std::string pdlp_params_str = "termination_criteria: {  time_limit_sec: 60 eps_optimal_absolute: 1e-4 eps_optimal_relative: 1e-4 }";

If you're using MPSolver, pass the parameters as: solver.SetSolverSpecificParametersAsString(pdlp_params_str);

If you're using MPModelRequest, set the solver_specific_parameters field instead.

See the documentation on PrimalDualHybridGradientParams for the precise definitions of the termination criteria and other parameters you can set.

Question 2: Yes, you found it in primal_dual_hybrid_gradient.cc. We do not use ADMM; see https://arxiv.org/abs/2106.04756 for details on PDLP's algorithm.

Question 3: PDLP's infeasibility detection rules are based on https://arxiv.org/abs/2102.04592. It hasn't been extensively tuned; if you have problems where it's slow we may be able to take a look at what's wrong. I can give two tips for speeding up infeasibility detection.

1. Try "presolve_options: { use_glop: true }". Presolve can often detect infeasible problems without even needing to run the solver.

2. Set "termination_criteria: { eps_primal_infeasible: 1e-6 }" (or any other value greater than the default of 1e-8). This will make infeasibility detection faster at the cost of a possibly higher false positive rate.

Hope this helps!

[Darin Goldstein]

If I could ask one more question: Is it possible to easily set a "warm start" (an approximate solution) for PDLP? If so, can you direct me to the command? Again, thanks so much for your help. Best, D

[Miles Lubin]

Yes, you can provide initial starting points, but only if you use PDLP's direct API. See the initial_solution argument at https://github.com/google/or-tools/blob/a6431c11884a2475befc4bbd5474fe89e8a04436/ortools/pdlp/primal_dual_hybrid_gradient.h#L134.

MPSolver and MPModelRequest don't provide a mechanism to specify a primal/dual solution hint.

[Darin Goldstein]

Hello, Miles. Thank you so much for your quick response. I have attempted to get the PDLP source code to compile inside of Microsoft Visual Studio 2019 (where my codebase currently resides) by copying in the file primal_dual_hybrid_gradient.cc and all of its dependencies, and I get weird errors that don't seem "real." For example:

ortools\pdlp\iteration_stats.cc(514,1): error C2440: 'return': cannot convert from 'const absl::lts_20210324::nullopt_t' to 'std::optional<operations_research::pdlp::ConvergenceInformation>'

ortools\pdlp\iteration_stats.cc(525,1): error C2440: 'return': cannot convert from 'const absl::lts_20210324::nullopt_t' to 'std::optional<operations_research::pdlp::InfeasibilityInformation>'

and several other strange ones like that, in addition to

ortools\pdlp\primal_dual_hybrid_gradient.cc(1635,57): error C2039: 'begin': is not a member of 'Eigen::Matrix<double,-1,1,0,-1,1>'

and others.

Is there a way to access PDLP's API directly from the compiled library (as you mentioned, without using MPSolver or MPModelRequest) or will I have to find some way to work around these errors to use the source code? Thanks again for your help. Best, Darin

[Laurent Perron]

I think you need to force C++17.

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/14e34e46-73f7-42ca-90b6-027379169a3bn%40googlegroups.com.

[Darin Goldstein]

Hi, Laurent. Thank you for the suggestion. When I forced C++17, the errors that you were referring to did go away. However, new errors appeared of this kind:

ortools\pdlp\primal_dual_hybrid_gradient.cc(451,7): error C7555: use of designated initializers requires at least '/std:c++20'

repeated ~20 times.

Do you happen to know what C++17-specific features you used? If you could tell me, I'll comb through the code myself and remove them; I need the asynchronous standards from C++20 anyway for the codebase that I'm trying to integrate with. Again, thanks so much for your help, D

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEeYzhad%3D-a0NDCkQTME5PHuZCvbHWcOwijQ8Zj%2BD1gGdvQ%40mail.gmail.com.

[Miles Lubin]

PDLP should be accessible from the or-tools compiled library. If it's not, that's a bug.

[Darin Goldstein]

Hi, Miles. Again, thanks for your extremely quick responses (on the weekend, no less). I thought that access to PDLP was exclusively through the MPSolver interface. Is there a way to access the functions and classes directly? If so, is there documentation that you can direct me to? Best, Darin

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/21ce7da8-3e50-4206-a57d-361ff342026en%40googlegroups.com.

[Miles Lubin]

> Is there a way to access the functions and classes directly?

Conceptually, you should be able to access PDLP the same way you access MPSolver, i.e.,

1. Use the header files in ortools/pdlp

2. Link against the PDLP library (ortools/pdlp/CMakeLists.txt)

As for the specifics, I'm not sure as I don't have experience with using OR-Tools from Visual Studio. What have you tried and what error messages do you get?

[Darin Goldstein]

Hi, Miles. Thanks again for your response. I believe that I've figured out all of the issues with regard to Visual Studio. Just one more question please: It appears as if the constraint_matrix is represented as an Eigen::DiagonalMatrix. Unless I'm misunderstanding the documentation, that means that off-diagonal elements are not allowed in pdlp when performing quadratic programming. Is that correct? Or does the internal constraint_matrix represent the result of some kind of preprocessing (i.e. a transformation of the variables that is supposed to leave the matrix in diagonal form and the user is required to make this transformation)?

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/8a32b9d5-9e64-4412-982c-cb10823d45e6n%40googlegroups.com.

[Darin Goldstein]

I apologize. I meant objective_matrix, not constraint_matrix, of course.

[Miles Lubin]

Yes, that's correct. Only diagonal (separable) quadratic terms are supported. Note that QP support in PDLP is experimental (not tuned or benchmarked to nearly the same extent as LP). If you'd like to try it, you'll have to put your objective matrix in diagonal form, e.g. by introducing extra variables. For example, min ||b - A*x||^2 becomes min ||s||^2 where "s = b - A*x" are added as equality constraints.