13

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.


7

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 the search if the difference between the best integer solution and the best bound is strictly less than 1.


5

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 might be better to just let the master problem identify the relevant cuts (by generating solutions that violate them). That said, if you are using a solver, it may ...


5

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 is said to take superpolynomial time if $T(n)$ is not bounded above by any polynomial. Using little omega notation, it is $\omega (n^c)$ time for all constants ...


4

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 frequently. We don't use them in our solver because the slowdown we experience from the sheer number of constraints that must be added to impose integrality ...


4

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 each $p\in P$ and each $n\in \lbrace 0,\dots, N\rbrace$, introduce variable $t_{p,n}\in [0,1]$. Now add the constraints$$\sum_{n=0}^N t_{p,n} = 1\quad \forall ...


2

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, one of the optional intervals must be selected. And the presence literal of the optional interval implies that the start of the main interval is equal to the ...


2

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: range R=1..3; int sizes[R]=[40,60,70]; int demand[R]=[108,125,100]; range M=1..2; int steelbars[M]=[150,200]; int nbMaxBarOfEach=200; range B=1..nbMaxBarOfEach; // how many shape r in R do we cut ...


2

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 the problem. This is common in e.g. feasibility pumps, where we want to avoid cycling of solutions, or when we want to break symmetry. We can also generate cuts ...


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