Skip to main content
13 votes
Accepted

Why isn't $x_2+x_3+x_4\le 2$ a cutting plane?

It is a cutting plane, but it is implied by $x_2+x_4\le 1$ and $x_3\le 1$ so not very useful.
RobPratt's user avatar
  • 32.7k
12 votes

Julia JuMP successive optimization

Your question has a two-part answer: how JuMP handles successive solves, and how the solvers handle successive solves. How JuMP handles successive solves Recall that JuMP is a modeling layer, not an ...
mtanneau's user avatar
  • 4,183
7 votes

Objective Integrality Cuts

I am not familiar with objective integrality cuts, but I know that CPLEX has the option to set the parameter absolute objective difference cutoff. If you set this parameter to 1, CPLEX will terminate ...
Rolf van Lieshout's user avatar
5 votes

Improving cuts from sub-problem with problem-specific hierarchical information

The implied cuts may not be worth adding. Depending on how the solution process goes (solving the master to "optimality" each time before solving the subproblem, versus a "one tree" approach), it ...
prubin's user avatar
  • 39.5k
5 votes
Accepted

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? Yes Definitions: "Superpolynomial time An algorithm ...
Rob's user avatar
  • 2,120
4 votes
Accepted

Cutting-planes application procedure for a specific problem

If $|P|$ is not too large, you could try an integer programming formulation. Fix an integer $N>1$ (which will control the granularity of the approximation) and let $\Delta=\frac{H^+ - H^-}{N}$. For ...
prubin's user avatar
  • 39.5k
4 votes

Objective Integrality Cuts

AFAIK Lindo have implemented objective integrality cuts, but I don't know the details of the implementation. It's always a trade-off that depends on what type of problems a solver's users solve more ...
Nikos Kazazakis's user avatar
3 votes

Julia JuMP successive optimization

I am not familiar with Julia, but you can search for callback and lazycut which allows you ...
Penghui Guo's user avatar
3 votes

Exploiting ordering to removing infeasible solutions in MILP

Depending on the solver used, you may be able to prioritize the $x$ variables so that variables with higher indices are branched on before variables with lower indices (and elements of $x$ are ...
prubin's user avatar
  • 39.5k
3 votes

How to redefine separation procedure to get 0-1 knapsack with odd number of items

Unfortunately, I also do not know how to embed 0-1-knapsack specific inequalities with the odd number solution requirement. However, I know how to generate cuts that will reduce the search space ...
Matheus Diógenes Andrade's user avatar
3 votes

Separating violated cover inequalities

A partial answer to part (ii) of your question (this was too long for a comment so I'm including it as an answer). Note that the following assumes a minimal cover. The sequence independent lifting ...
tc1729's user avatar
  • 131
3 votes
Accepted

Separating violated cover inequalities

As a heuristic for finding a minimal violated cover inequality, you can solve your min-knapsack problem to find a cover $C$. Then, you may note that all objective function coefficients of the ...
Sune's user avatar
  • 6,562
2 votes
Accepted

general approach to iterating extreme rays of solution cone

The cone you are describing is often referred to as a basis cone (for instance, in Sec 2.3 of this paper, where the concept is used to derive cuts too). Note that you have such a cone for every ...
mtanneau's user avatar
  • 4,183
2 votes
Accepted

Cplex : The cutting stock problem

I think you have some errors when you wrote Cutting method and falls using 2m -200cm- steel bar The model is small enough for a naïve model without pattern: ...
Alex Fleischer's user avatar
2 votes
Accepted

A specific case of a resource constrained project scheduling problem with partially renewable resources (RCPSP/$\pi$) - OR-Tools

To have resources being released at given time points, you have two options. Have one optional interval per time interval. This interval always ends at the end of the interval. For a given demand, ...
Laurent Perron's user avatar
2 votes

What to do with cuts (constraints) when a fixation is contrary to a RHS in a ILP / LP relaxation?

There are two main reasons to add cuts. First, to tighten the relaxation, i.e., make the domain smaller whilst preserving the global solution. Second, to kick a known (or predicted) solution out of ...
Nikos Kazazakis's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible