Query on settings for branch-and-cut where LP is converted to MIP

回答済み

OneCable OneCable

2026年01月10日 14:13

• 
• 
• 

Hello,

In the example provided with the library, tsp_c.c, 

GRBaddvar(model, 0, NULL, NULL, distance(x, y, i, j)/2,
                        0.0, 1.0, GRB_BINARY, name);
                        ...
/* Must set LazyConstraints parameter when using lazy constraints */
error = GRBsetintparam(GRBgetenv(model), GRB_INT_PAR_LAZYCONSTRAINTS,
                         1);

Here, the problem is initially itself declared to be an IP. For correctness, the LazyConstraints parameter needs to be appropriately set. I understand this approach completely.

What if, however, the user starts with a LP of the TSP

GRBaddvar(model, 0, NULL, NULL, distance(x, y, i, j)/2,
                        0.0, 1.0, GRB_CONTINUOUS, name);

obtains fractional solutions, has other heuristic separation routines which work on the fractional solution. The user adds these to the LP in order to improve the lower bound. Then, after the heuristic separation routines are done, the user converts the problem to a binary integer program (by changing the continuous variables to integer variables) and then submits the problem (along with all of the cuts that the user himself generated) to the gurobi solver [along with the LazyConstraints parameter set as above, and also registering/implementing a lazy cut callback]?

My question is, like the LazyConstraints parameter, when the user is generating valid inequalities for the TSP's initial LP formulation using his own heuristic separation routines, are there some settings that need to be provided at the LP stage itself? For e.g., if LP does some pre-solve and therefore some variables of the formulation are removed, the user could be generating cuts that include this variable. Would not issues like these cause undefined behaviour and therefore the user should set some parameter to indicate to Gurobi that he intends to self-generate some promising cuts at the LP stage itself before submitting the problem to be subsequently converted/solved as an integer program by Gurobi?

Thank you.

関連

• Parameters
• Callbacks
• C

0

• 

  Simranjit Kaur

  • Gurobi Staff

  2026年01月12日 00:17 編集済み

  Hi,
  
  Could you please clarify the routine you plan to use to generate and add user cuts to the LP model? For example, if your approach is something like:

  Solve the LP → Run your custom separation routines on the fractional optimal solution to generate cutting planes in a separate process → Manually add those cuts to the LP using the GRBaddconstr function→ Re-solve the LP → Repeat until no more violated cuts are found (or you hit some stopping criterion).

  then no additional parameter settings are needed to ensure that your cuts remain valid for the LP model.

  Please note that the callback function GRBcbcut can only be used to add user cuts to a MIP model. When adding user cuts via callbacks to a MIP model, one should consider setting the PreCrush parameter to 1. This setting disables certain presolve reductions that can otherwise prevent your cut from being applied to the presolved model, which could result in the cut being silently ignored. For more details and an example on using the GRBcbcut function, please have a look at this page of our reference manual. 

  Best regards,
  Simran

  1
• 

  OneCable OneCable

  2026年01月12日 07:18 編集済み

  • 
  • 
  • 

  Hello Simranjit,

  Thank you. That is indeed my workflow.

  I had one additional query. Does that fact that when I stop my own computations after, as you state:

  “Repeat until no more violated cuts are found (or you have hit some stopping criterion)”

  there exists a simplex feasible/optimal basis for the continuous relaxation cause any subsequent issues when I change some of the variables to binary and then submit the problem to Gurobi to solve?

  Perhaps the existence of a feasible simplex basis leads to warmstarging the MIP root node computations? Does this run the risk that some presolve reductions Gurobi could have done had I instead declared the problem upfront as an MIP, will now be incapable of being performed?

  In other words, is there a way I can tell Gurobi that when I convert a continuous variable to a binary/integer variable within my C application, with the intention to solve this problem now as a MIP, that it should treat this as a completely new MIP (as if all of the variables had been upfront specified to be binary/integer) and discard any warm start/parameters I have set before? That is, I expect that at this stage, the sequence of steps Gurobi follows (in terms of presolve, heuristics, etc.) when I solve this problem via the C API, it follows the exact same sequence I would obtain had I solved this on the command line with default settings.

  That is, suppose the IP I am interested in solving is:

  Min cx
  s.t. Ax = b
  x integer, x ≥ 0

  I solve its relaxation and add my own valid inequalities

  Min cx
  s.t. Ax = b
  Cx = d   //my own valid inequalities
  x ≥ 0

  Then, I convert the variables to integer by changing the VType attribute on variables and submit the problem to be solved by Gurobi:

  Min cx
  s.t. Ax = b
  Cx = d
  x integer, x ≥ 0

  All of the above happens within my C Code. I want the last IP (which has Cx = d constraints) to be solved within my code exact as it would have been solved had I submitted this last IP (which has Cx = d constraints) to be solved with default parameters by the gurobi command line interface.

  In this regard, the description of  https://docs.gurobi.com/projects/optimizer/en/current/reference/c/solving.html#c.GRBreset

  seems very similar to exactly what I want to achieve within my C application code.Could you please confirm?

  Thank you.

  0
• 

  Simranjit Kaur

  • Gurobi Staff

  2026年01月12日 23:25

  If there exists a simplex feasible/optimal basis for the continuous relaxation cause any subsequent issues when I change some of the variables to binary and then submit the problem to Gurobi to solve?

  The feasible/optimal basis from the previously solved LP model will not impact the solving of the same model when some continuous variables are made binary. 

  Yes, in general, calling the GRBReset function discards any previously computed solution information for the model.

  The following articles are useful resources to understand when Gurobi will use warm starts when an LP model is modified and solved iteratively, and how start solutions work in a MIP model:

  • Does Gurobi use warmstarts after changing a previously optimized model?
  • How do I use MIP starts?

  Best regards,
  Simran

  1

サインインしてコメントを残してください。