# Questions tagged [cutting-planes]

The tag has no usage guidance.

18 questions
Filter by
Sorted by
Tagged with
369 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?
• 2,745
179 views

### Improving cuts from sub-problem with problem-specific hierarchical information

I'm solving an assignment-alike problem with a Logic-based Benders decomposition-alike (LBBD) method. The master problem provides an assignment, which is checked in the sub-problem. Define the set of ...
• 221
163 views

### What to do with cuts (constraints) when a fixation is contrary to a RHS in a ILP / LP relaxation?

I am trying to understand an algorithm in a paper by CrĆ©vits et al. (2012)1 (see algorithm 2, the cuts I'm referring to are from the reduced costs). It uses a series of successive cuts on a linear ...
• 331
314 views

### Objective Integrality Cuts

Consider a mixed integer linear program with an objective function that includes only integer variables. Objective integrality cuts are known as a class of valid inequalities that can be added to ...
• 2,170
325 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. ...
• 107
1k views

### Julia JuMP successive optimization

I am using Julia's JuMP package to solve a cutting-plane method. Namely, I solve a sub-problem, find the most-violated constraint in the master problem, add that to ...
• 4,010
322 views

### Separating violated cover inequalities

Consider a knapsack problem with binary variables and a standard knapsack constraint $\sum_{j\in N}a_jx_j\leq b$. A set $C\subseteq N$ is a cover if $\sum_{j\in C}a_j >b$ If $C\subseteq N$ is a ...
• 3,471
172 views

### Cutting-planes application procedure for a specific problem

Sort of following up with this question. I reformulated another model to make it convex and possibly solve it with some cut generation method. I would like to double-check whether I am doing it ...
• 1,249
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. ...
• 303
248 views

### How to redefine separation procedure to get 0-1 knapsack with odd number of items

So I have a 0-1 knapsack problem: \begin{align}\max&\quad \sum_j c_j x_j\\ \text{s.t.}&\quad \sum_j a_j x_j \leq b\\ &\quad x_j \in \{0,1\}\end{align} but it has an additional requirement ...
• 161
679 views

### Cplex : The cutting stock problem

The problem below aims to minimize the cutting leftovers from each cut : A company manufactures desks for kids gardens and primary schools, colleges and high schools. The leg of these desks all have ...
• 125
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 ...
• 6,657
138 views

### When and where the cutting plane method should be applied?

As the cutting plan algorithm is a method to strengthen the feasible space of the linear programming, specifically in the MILP problems to invoke the integer solutions, it may be a problem-based ...
• 9,068
133 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 ...
• 920
245 views

### A specific case of a resource constrained project scheduling problem with partially renewable resources (RCPSP/$\pi$) - OR-Tools

I've been trying solve a specific case of the resource constrained project scheduling problem with partially renewable resources (RCPSP/$\pi$ in the literature e.g. this paper). These resources are ...
• 178
117 views

### How to implement CPLEX user cuts using CPXaddusercuts in C API?

I am trying to use CPXaddusercuts to add cutting planes, which have not been violated yet but are likely to be violated as we go down the branch & bound tree, to the list (pool) of constraints. As ...
1 vote
Consider a polytope in $\mathbb{R}^n$ inside the unit cube given by $$A\vec{x} \le b \\ 0 \le x_i \le 1$$ And consider one particular row of $A$ that we consider as a cut $A_ix \le b_i$. I am ...