# Questions tagged [cutting-planes]

The tag has no usage guidance.

16 questions
Filter by
Sorted by
Tagged with
255 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 ...
108 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 ...
55 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 ...
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 ...
126 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 ...
127 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. ...
215 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 ...
221 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 ...
99 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 ...
305 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 ...
607 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 ...
168 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 ...
170 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 ...
295 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. ...