Questions tagged [cutting-planes]
The cutting-planes tag has no usage guidance.
13
questions
5
votes
2
answers
464
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,776
3
votes
0
answers
75
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 ...
- 5,744
4
votes
1
answer
116
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
140
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
135
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 ...
- 69
2
votes
0
answers
68
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
2
answers
195
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,110
3
votes
1
answer
337
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 deks all have ...
- 125
4
votes
1
answer
159
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,229
12
votes
1
answer
130
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
220
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
139
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
272
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,665