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.
- 30.5k
11
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 ...
- 4,068
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 ...
- 2,305
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 ...
- 37.9k
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 ...
- 2,098
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 ...
- 37.9k
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 ...
- 11.9k
3
votes
Julia JuMP successive optimization
I am not familiar with Julia, but you can search for callback and lazycut which allows you ...
- 712
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 ...
- 37.9k
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 ...
- 1,208
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 ...
- 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 ...
- 6,352
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 ...
- 4,068
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:
...
- 4,000
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, ...
- 2,597
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 ...
- 11.9k
Only top scored, non community-wiki answers of a minimum length are eligible