5
votes
For an ILP relaxed to LP is the LP solution objective always less than the ILP solution?
If the integer linear programming is a minimization problem then whose linear relaxation is a lower bound for the original MILP model, and for the maximization problem it is an upper bound. In the ...
- 8,165
5
votes
Accepted
if else condition with multiple criteria in MIP
Let $\epsilon$ be a small constant positive tolerance, and let $M$ be a constant upper bound on $x_1$. Now impose linear constraints $$\epsilon s_1 \le x_1 \le M s_1.$$
- 29.7k
3
votes
How to properly tackle a big model using weak constraints
How lazy constraints are handled may depend on the solver, but CPLEX turns off dual reductions in the presence of lazy constraints, which could negatively impact performance. So I would probably limit ...
- 37.4k
3
votes
Accepted
Formulation of binary constraint with the least binary variables for linear programming
You want to impose the following two logical constraints:
$$
\begin{align}
\delta_{t-1} = 1 \wedge \delta_t = 0 &\implies \beta_t = 1 \tag{1} \\
\neg (\delta_{t-1} = 1 \wedge \delta_t = 0) &\...
- 1,477
3
votes
Is an insanely high number of feasibility cuts normal while solving a VRP with Benders?
You usually use Benders decomposition when a large number of variables and linking constraints can somehow be removed without significantly affecting the structure of your problem.
In your case, you ...
- 1,549
3
votes
Accepted
Formulation for choosing how many items to manufacture
If you need both $x$ and $y$ in the model, a third option is to enforce
\begin{align}
y_{m,p,s} &\ge x_{m,p,s} \\
y_{m,p,s} &\le \text{PartsPerShift}_p x_{m,p,s}
\end{align}
This modification ...
- 29.7k
2
votes
Accepted
Activating a sequence of the binary variables in a multi-dimensional array
Introduce an ordering $\text{ord}: I \to \{1,\dots,|I|\}$ and impose
$$x_i \le x_j$$
for all $i\in I$ and $j\in I$ such that $\text{ord}_i + 1 = \text{ord}_j$.
An alternative, less efficient, approach ...
- 29.7k
2
votes
Accepted
How to calculate the duration of a task in each shift?
$h_1, h_2, h_3$ mean the duration time in each period, respectively?
Output also including the start time variables?
Ans:
$h_1 = (480 - start) * b_1$
$h_2 = duration - h_1 - h_3$
$h_3 = (finish - 960) ...
- 101
2
votes
Accepted
1
vote
mip - mapping of equality to boolean variable
If I understood correctly, you want to enforce
$$
\begin{align}
e_{1,w} = e_{2,w} \implies b_{w} = 1 \quad \text{for all } w, \tag{1} \\
e_{1,w} \neq e_{2,w} \implies b_{w} = 0 \quad \text{for all } w....
- 1,477
1
vote
How to select intermediate nodes in a network?
Option 1: Run Dijkstra's algorithm first. Then you will have a grid of positive numbers that you can use for additional constraints. E.g. require a positive number to know that a path is available ...
- 837
1
vote
Coefficient Scaling for MIP
In my opinion, these two formulations are exactly the same.
However, coefficience scalling would lead the float number coefficience in the first constraints, and then that would not be the benefit for ...
- 101
1
vote
Cplex seems to terminate early as optimal when starting solution polishing
First of all, I think you have to display the final MIP gap in your terminal, maybe that actually MIP gap is zero.
If not, in my opinion, you have to check several experiments. Using MIP solver solve ...
- 101
1
vote
Does OptaPlanner give equally good results when comparing with commercially available MIP solvers?
It depends on the use case. The right tool for the job.
Generally speaking, in my experience, for Vehicle Routing Problems and many other use cases, when scaling out, a good metaheuristics solver (...
- 4,685
Only top scored, non community-wiki answers of a minimum length are eligible