Skip to main content

Questions tagged [cutting-planes]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer

Can a cut be tight across a diagonal in a polytope?

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 ...
Sidharth Ghoshal's user avatar
0 votes
0 answers

Differences between non-convex and convex optimization problem with l0-Norm Regulization

I'm currently in the process of writing my bachelor's thesis and trying to deal with the theory behind the model in this paper Risk-calibrated Super-sparse Linear Integer Model (Berk Ustun and Cynthia ...
user13121's user avatar
5 votes
2 answers

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 ...
Joris Kinable's user avatar
2 votes
1 answer

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 ...
Brannon's user avatar
  • 920
3 votes
0 answers

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 ...
Sune's user avatar
  • 6,657
5 votes
2 answers

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 ...
independentvariable's user avatar
3 votes
0 answers

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 ...
A.Omidi's user avatar
  • 9,068
4 votes
1 answer

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. ...
Duns's user avatar
  • 303
3 votes
1 answer

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 ...
Aisec Nory's user avatar
2 votes
1 answer

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 ...
David Torres's user avatar
2 votes
0 answers

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

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 ...
rasul's user avatar
  • 2,170
3 votes
1 answer

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 ...
JirenOppaik's user avatar
4 votes
1 answer

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 ...
tcokyasar's user avatar
  • 1,249
12 votes
1 answer

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 ...
Jasper's user avatar
  • 221
8 votes
1 answer

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. ...
Slim Shady's user avatar
11 votes
1 answer

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 ...
gornvix's user avatar
  • 331
17 votes
1 answer

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?
Marcus Ritt's user avatar
  • 2,745