Skip to main content

Questions tagged [branch-and-cut]

Questions on algorithms that combine branch-and-bound search and the generation of cutting planes.

Filter by
Sorted by
Tagged with
2 votes
2 answers
85 views

Optimizing calls to a separation problem in branch and cut

I have a MIP in which I am able to generate cuts at intermediate relaxation solutions using the context class. These cuts are derived from a separation problem. However, after adding them, the code ...
tr244's user avatar
  • 21
1 vote
0 answers
76 views

CPLEX gets stuck in "Performing restart"

During solving my problem using generic lazy cuts (in Benders decomposition fashion), the solver gets stuck logging out "Performing restart 2" for several hours (while the time limit is 30 ...
Amir Hossein Hosseini's user avatar
1 vote
1 answer
47 views

custom branch and bound on cplex or GAMS

Does anyone have an idea how to create a custom B&B on CPLEX or GAMS? In my work, I need to add custom cuts on integer solutions in certain conditions by adding only one branch. Also, I need to ...
BADJARA Mohamed el Amine's user avatar
6 votes
2 answers
269 views

Cover cuts for knapsack constraint with integer variables

It is known for knapsack type constraint $\sum_{i \in N} a_i x_i \leq b , x \in \{0,1\}$, we can generate the so called cover cuts that have the sum of coefficient in a set C greater than b. The cover ...
CHE's user avatar
  • 113
6 votes
1 answer
351 views

Valid Inequality Example (Wolsey Example 9.3)

I was following Wolsey Example 9.3: Let $X = \{(x,y) \in (R^{m}_+,B^1) : \sum_{i=1}^m x_i \leq my\}$. Now consider the valid inequality $x_i \leq y$ and show that it is facet defining. My question is ...
Joshua's user avatar
  • 61
2 votes
1 answer
128 views

general approach to iterating extreme rays of solution cone

Suppose I'm at an optimal solution of an LP relaxation in a MILP branch-and-bound descent. I want to add an additional cut of my own devices. To compute this cut I need the extreme rays of the cone ...
Brannon's user avatar
  • 900
3 votes
0 answers
56 views

Separating two LP solutions at the same time

In a cutting plane algorithm for integer linear programming problems you would usually use an LP solver to get an extreme point of the polyhedron corresponding to the LP relaxation. Let's call that ...
Sune's user avatar
  • 6,647
3 votes
1 answer
251 views

Solution for a TSP with Branch and Cut for Gurobi in Java?

We have a group project and our job is to create an algorithm for solving a TSP with Branch and Cut. (Use of lazy constraints.) We tried around but don´t know what is the best way to start. We get the ...
Philip's user avatar
  • 31
2 votes
3 answers
190 views

Warm starting ideas for iteratively solving a model with a few additional constraints

I'm trying to solve a MILP model iteratively, and at each iteration a few constraints are added to the problem that cut off the previous optimal solution. I'm trying to figure out ways to implement a ...
jackson's user avatar
  • 29
4 votes
1 answer
131 views

Exploiting ordering to removing infeasible solutions in MILP

I kindly ask for some ideas or references to exploit ordering in MILPs. In particular, there are resources $ r = [r_1, r_2, ..., r_K] $ such that $r_{i} \leq r_{i+1} $. These are input to the problem. ...
Duns's user avatar
  • 303
5 votes
1 answer
936 views

CPLEX gives different solutions of MILP every run

I am solving a mixed-integer (binary) linear problem using CPLEX as a solver (branch-and-bound method). But I encountered the following issue. Each run I get a different solution at a different node ...
errenmike1806's user avatar
6 votes
1 answer
159 views

Naturally branch-and-cuttable problems with high didactic value

I am willing to bet that the problem most often used to teach students about branch-and-cut is the Travelling Salesman Problem (TSP). It has a number of nice characteristics which make it appropriate ...
Alberto Santini's user avatar
2 votes
2 answers
314 views

Branch and bound method for solving non-convex integer non-linear multi-objective optimization problem?

Following are the characteristics of my problem: Objective function: two non-linear functions and one linear function Decision variable: two integer variables ($X_1$ and $X_2$) Constraint: three (two ...
vp_050's user avatar
  • 179
3 votes
1 answer
364 views

Implementation of Local Branching

I've been recently reading some papers where the authors use local branching specifically in Benders Decomposition (see for reference). Although I understand up to some extend how the algorithm works, ...
whitepanda's user avatar
2 votes
2 answers
930 views

How to use tight upper and lower bounds to get to the optimal value via branch and bound?

I have algorithms that get me a tight upper (UB) and lower (LB) bound to a maximization binary integer program (a routing problem). My formulation is non-compact and requires the addition of sub-tour ...
SHUVABRATA CHAKRABORTY's user avatar
0 votes
0 answers
202 views

Branch and Cut algorithm

Could someone please explain what is the point of this added cut? Also how was it deduced? Could someone please give some examples of this sort? As I've been searching for such examples but did not ...
Slim Shady's user avatar
8 votes
1 answer
320 views

Why isn't $x_2+x_3+x_4\le 2$ a cutting plane?

In my textbook, to generate cutting planes, they tell you to proceed as follows: A procedure for generating cutting planes: Select a ($\le$) constraint that has only nonnegative coefficients. ...
Slim Shady's user avatar
17 votes
1 answer
358 views

Was there something specific that caused graph cuts to lose popularity in the last 5 years?

Almost every graph-cut paper I look at seems to have exactly the same pattern of monotonic growth in citations and then monotonic decline starting around 5 years ago: For privacy I've cut the all ...
Nike Dattani's user avatar
  • 1,278
7 votes
1 answer
350 views

Program can't stop when using callback of usercut in CPLEX to solve a branch-and-cut problem

When I tried to use Java to call CPLEX and use callback functions to solve a VRP problem with branch-and-cut, some problems emerged. I took out the subtour elimination constraint from the original ...
xin koala's user avatar
9 votes
1 answer
335 views

Rules of thumb for using classic methods (e.g. branch and bound) vs. meta-heuristics (G.A, S.A, etc..) for non-convex problems?

Are there any rules of thumb for when to use classical methods like branch and bound, branch and cut, etc...for non-convex problems, vs using meta-heuristic methods like genetic algorithms, ...
Skander H.'s user avatar
  • 2,139
12 votes
3 answers
6k views

Performance of a branch and bound algorithm VS branch-cut-heuristics

I was trying to solve a moderate scheduling model using an open-source solver. I did two different ways. A) using pure branch and bound algorithm (disable all options). B) using the default setting ...
A.Omidi's user avatar
  • 8,960
17 votes
1 answer
368 views

Family of hard instances for Gomory's cutting plane algorithm

Is there a variant of integer programs for which Gomory's cutting plane algorithm demonstrably takes a superpolynomial number of iterations?
Marcus Ritt's user avatar
  • 2,725
16 votes
2 answers
700 views

Branching rules in commercial MIP solvers

I am working on a branch-and-cut algorithm, and I have spent quite some effort into improving the branching decisions that are made by commercial solvers, such as CPLEX and Gurobi. However, it was ...
Albert Schrotenboer's user avatar
12 votes
2 answers
787 views

When does Gurobi add cuts from callback

A while ago I used Gurobi and I added user cuts from within a callback. However, I got the feeling that my user cuts were not directly added to the model. Is it right that Gurobi can decide to ...
Michiel uit het Broek's user avatar