Questions tagged [cutting-planes]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
user avatar
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 ...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
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 ...
user avatar
  • 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?
user avatar
  • 2,665