Questions tagged [cutting-planes]
The cutting-planes tag has no usage guidance.
16
questions
5
votes
2
answers
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 ...
- 3,396
2
votes
1
answer
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 ...
- 892
3
votes
0
answers
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 ...
- 6,362
5
votes
2
answers
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 ...
- 3,980
3
votes
0
answers
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 ...
- 8,505
4
votes
1
answer
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.
...
- 303
3
votes
1
answer
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 ...
- 161
2
votes
1
answer
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 ...
- 168
2
votes
0
answers
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 ...
9
votes
3
answers
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 ...
- 2,140
3
votes
1
answer
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 ...
- 125
4
votes
1
answer
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 ...
- 1,249
12
votes
1
answer
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 ...
- 221
8
votes
1
answer
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.
...
- 107
11
votes
1
answer
158
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
17
votes
1
answer
348
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,705