Provide an initial starting solution for a MIP

[Kyrielsh1]

Dear all,

I noticed there exists a subject already in the list that wonders about the possibility to provide an initial solution to the solver so that we start from a given upper bound (for e.g. a minimization problem). An answer is proposed, i.e.:

"You can set an initial solution by filling solution_hint in the protocol buffer interface (linear_sover.proto). 

This is currently the only way.

If you are using the MPSolver interface directly, you can export the model to a proto, set this field, and then call SolveWithProto() to do the solving."

So the possibility exists but it is not really straightforward. I would like to ask whether something exists in the "or-tools to do list" regarding this, in order to make it easier like with other solvers where would only pass the vector of variables and values to a function that would fill solution_hint_ by itself. Alternatively (and in the mean time), are there examples of how to use this buffer protocol interface ? It would really help to have an example program which initializes the solver with a feasible solution so that we can reproduce it easily "at home".

Alternatively squared, what would happen if I wrote an additional class function in linear_solver.h which takes a vector of variables and values and fills the private variable solution_hint_ directly ? Is there some part of the code where the solver will automatically take the solution, solve the problem fixing the given variables and update the upper bound and solution list accordingly before starting the branch and cut, or is this the aim of the protocal buffer interface ?

[Kyrielsh1]

Pinging the thread: Is there any example out there on how to use Protocol Buffer Interfaces and passing an initial solution to the solver ? I think it's pretty crucial to many people.

Thanks in advance for any hint or help.

[kyrielsh]

Just to be sure that I'm not losing time for nothing: in the source code of linear_solver.h (v6.7, line 629), a line of comment is provided before the definition of solution_hint:

  // Note(user): as of 05/05/2015, we can't use >> because of some SWIG errors.

Is this line still valid ? Please tell me if these SWIG errors are still there because if so I stop losing time and come back to or tools when this is fixed. Having no way to warm start the solver is a pretty big downer for many practitioners...

Thanks in advance to the maintainers for providing some light on this issue.

[Frederic Didier]

This is just here to indicate that we need(ed):

std::vector<std::pair<MPVariable*, double> >

instead of 

std::vector<std::pair<MPVariable*, double>>

(notice the space between the closing  > >)

--
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.
For more options, visit https://groups.google.com/d/optout.

[kyrielsh]

Ok that was stupid sorry :-) Thanks for the answer.

[kyrielsh]

I'd have an additional question: is it obbligatory to go through Protocol Buffer to use solution_hint ? Meaning that the Protocol Buffer does some mojo of its own about solution_hint before passing it to the MPSolver object ? Because I wrote a public function to MPSolver based on how the Protocol Buffer object passes the solution hint to MPSolver:

void MPSolver::WarmStartSolution(std::vector<std::pair<MPVariable*, double> > starting_solution) {
  for (int i = 0; i < starting_solution.size(); ++i)
    solution_hint_.push_back(
        std::make_pair(starting_solution[i].first,
                       starting_solution[i].second));
}

My code compiles right but unfortunately it's not easy to see whether that has an effect on the model of the integer_programming.cc since it solves the model right away through cuts without any need to branch at all. Theoretically if I use this function with a more complicated model it should send the info to the solvers ? (through addMIPStart for Cplex etc...)

[kyrielsh]

Partially answering myself: I see that in the gurobi_interface.cc and scip_interface.cc files there is a use of solution_hint passing its values to the function that loads an initial solution in Gurobi and SCIP. In the other interface_*.cc files I do not see anything, which hints heavily towards the conclusion that solution_hint is not forwarded to Cplex, GLPK or CBC. I'll try to see if I can write a piece of code to add to these files that could do it and will post again if I manage and it seems to work, for those interested.

[kyrielsh]

I managed for CPLEX: in the file interface_cplex.cc, you can add in function CplexInterface::Solve (before the solve function CPXXmipopt) the following:

      // Set solution hints if any.
      const CPXNNZ beg[1]={0};
      CPXDIM varindices[solver_->solution_hint_.size()];
      double values[solver_->solution_hint_.size()];
      int i=0;
      for (const std::pair<MPVariable*, double>& p : solver_->solution_hint_) {
        varindices[i] = p.first->index();
        values[i++] = p.second;
      }
      CPXXaddmipstarts(mEnv, mLp, 1, (CPXNNZ)solver_->solution_hint_.size(), beg, (const CPXDIM *) varindices, (const double *) values, NULL, NULL);

to use a single starting solution with CPLEX. You can use it in conjunction with the WarmStartSolution I described in a previous message above, it compiles and works, I tried it on the IntegerProgramming example file provided by ortools, it changes the starting heuristic solution that CPLEX uses. If you decide to use LinearExpr for the variables as I did since it's much less of a headache for models that are a little involved, then you can't just provide the LinearExpr to the function, it has to be converted back to MPVariable* before. If you take the Integer Prorgamming example of OR-tools and define x1 and x2 as LinearExpr, you can do something like:

  std::vector<std::pair<MPVariable*, double> > starting_solution;
  starting_solution.push_back(std::make_pair((MPVariable*)x1.terms().begin()->first, 9.0));
  starting_solution.push_back(std::make_pair((MPVariable*)x2.terms().begin()->first, 0.0));
  solver.WarmStartSolution(starting_solution);

for example. Hope it might be of some help to people trying to use warm starting! I didn't find yet the function in the CBC and GLPK callable library to initialize the solution. When and if I find it I will post here the modifications I will have made to make it work.

Any comment is welcome :-)

[Evren Güney]

Hi everyone,

How do we provide an intial solution in C# in SCIP?
Do we have a method on the variables like in Gurobi?

In Gurobi you can do:
myvar.Start = initial_value;

[Evren Güney]

Any comments on this?
Thanks in advance :)

[Laurent Perron]

you can set hints directly on the solver (MPSolver instance).

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/55422ac9-9d61-479f-b393-b9933a96f128n%40googlegroups.com.