5
If the variable is declared integer (and assuming the solver leaves it that way in the presolve stage), there is at least a chance that the solver will branch on it. In some cases this might be a good thing (getting the solver to a feasible solution faster, improving the bound faster) and in some cases this might be a bad thing (distracting the solver from ...
5
Let $y_i$ be a binary variable that equals $1$ if and only if $x$ is in the interval $i \in \{[15,25],[25,35],[35,45],[45,55]\}$. You can express $x$ as a convex combination of the extreme points of these intervals by introducing variables $\lambda_0, \lambda_1,\lambda_2,\lambda_3, \lambda_4 \in \mathbb{R}^+$.
If $f$ denotes your piecewise linear function, ...
5
Unless you turn off the presolve step, CPLEX will eliminate the variables that are locked at zero during presolve. So the answer to your second question is that presolve may take slightly longer (but the difference will be too small to notice) and the actual branch-and-cut phase will not take any longer than if you had omitted the variables yourself. The ...
5
Constraints 1 and 2 ensure that there is an edge going in and out of every node. Constraint 3 works as a subtour elimination and along with the above constraints ensures that there is no subtour and as a result, you must enter and leave the depot.
A simple illustration is to assume there are only 3 nodes. So: $ V = \{0, 1, 2\}$ and $ N = \{1,2\}$. Let's ...
5
If the time for any project fails to be a convex function of the number of employees assigned to the project, I think your best bet is indeed to use a binary variable for each combination of project and employee count. Note that, in your example, completion time is a linear function of head count for the third project and a convex function for the second ...
5
Forum users are invited to post their suggestions for tighter/better formulations of mixed integer linear programming models here. The emphasis is on getting solutions (and closing the gap) efficiently, as opposed to model expressiveness (ease of users to see what is going on in the model).
General
Logical constraints
For "big M" models, smaller ...
4
So we know that MILP instances are independent and that the total throughput is to be maximized. In practice, increasing the number of threads used by a solver to solve a MILP instance could marginally improve the runtime only up to some point. Such optimal number of threads should be checked on a case by case basis. In CPLEX, for instance, the parallelism ...
4
Can anyone think about a better formulation?
Another option is to use binary variables $x_{it}$ that take value $1$ if task $i$ starts at time $t$. You then need two sets of constraints:
one start time per task:
$$
\sum_{t}x_{it} = 1 \quad \forall i
$$
don't overlap tasks:
$$
\sum_{i}\sum_{k, t+1 - d_i \le k \le t}x_{ik} \le 1 \quad \forall t
$$
This ...
4
In Making optimization simple (Python) I gave 2 options:
progress listener / MIP info callback
get solutions one by one
The models:
from docplex.mp.model import Model
from docplex.mp.progress import *
mdl = Model(name='buses')
nbbus40 = mdl.integer_var(name='nbBus40')
nbbus30 = mdl.integer_var(name='nbBus30')
mdl.add_constraint(nbbus40*40 + nbbus30*30 >...
4
It looks like your first constraint should instead be
$$0b_1 + a_1 b_2 + a_2 b_3 - d \le 0$$
With this change, the logical implications are
\begin{align}
b_1 = 1 &\implies 0 \le d \le a_1 \\
b_2 = 1 &\implies a_1 \le d \le a_2 \\
b_3 = 1 &\implies a_2 \le d \le a_3
\end{align}
To avoid ambiguous borders, introduce a small tolerance $\epsilon>...
4
Well, you did not define and detail well the problem, hence, I will first write formally the problem definition based on my understanding of what you have written, and then I will propose an Integer Programming formulation.
Problem definition
Let's first define formally the problem.
Let:
$t$ be the number of tasks to be serviced;
$T = \mathbb{N}_{\leqslant ...
3
In Breadth First Search, nodes are processed by non-decreasing value of their depth, i.e. the next node processed in the unprocessed node with the smallest depth.
In Best First Search, a value is assigned to each unprocessed node. The next node processed is the unprocessed node with the smallest value.
Therefore, Breadth First Search is equivalent to a Best ...
3
One solution is to add an Incumbent callback (not sure whether DOCPLEX support this yet, but certainly Java/C++), and log the solution + time stamp within the the callback.
Another solution which, if my memory service me well, is the following:
Set the MIP integer solution limit to 1 (IntSolLim parameter in Cplex <=12.6).
Invoke solve(). Cplex will ...
2
Your question isn't entirely clear and isn't really an OR question, but I think what you are trying to do is the following:
for j in n:
for k in r:
o += xsum(w[k] *y[k][jj] for jj in n if jj <= j) >= xsum (a[i][k]* x[i][j] for i in p)
2
It is not the best option to regard it as a non-convex QP. A product of a binary variable and a continuous variable is not really bilinear (or non-linear). For example, the nonlinear constraint
$$
z_{ij} \geq x_{ij}y_{ij}
$$
could be replaced with
$$
z_{ij} \geq y_{ij} - y_{\max}(1-x_{ij})\\
z_{ij} \geq y_{\min}x_{ij}
$$
(the RHS of the second line could be $...
2
There are multiple ways to express a finite interval of integers using boolean variables. A different encoding would be the logarithmic one
$$\sum_{i=0}^{\left \lceil{\log_2(10)}\right \rceil } 2^i\tilde{x}_i \text{ subject to } \sum_{i=0}^{\left \lceil{\log_2(10)}\right \rceil } 2^i\tilde{x}_i \leq 10$$
You can come up with many such encodings and in ...
2
I am not familiar with this specific subject but, do you try googling about that? There are many related papers such as:
Developing a model for multi-objective optimization of open channels and labyrinth weirs: Theory and application in Isfahan Irrigation Networks
Optimization of Irrigation Scheduling
Linear Optimization Model for Efficient Use of ...
2
My overall experience is that feeding constraints of the form $\rm objval \geq lb$ is detrimental to MIP solver performance.
The main reason is the following:
MIP solvers rely on branch-and-bound algorithms...
... whose performance depends heavily on branching decisions...
... which are themselves based on how the dual (lower if you're minimizing) bound ...
2
You could cluster 40,000 dropping locations (by grouping them based on location/vehicle type need) to some reasonable number and can try to implement metaheuristics like Simulated annealing, Particle swarm etc. . Though they won't guarantee optimality but can tune accordingly to achieve desired solution quality.
2
As far as I know, solution speed for solvers is typically a sublinear function of the number of threads/cores. This makes sense since parallel processing requires additional effort (CPU cycles) to coordinate threads, and may sometimes be subject to blocking. Based on that, and assuming a reasonably large pool of problems and adequate RAM, I would probably ...
2
If the $y$ function is continuous (meaning $a\cdot 25 + b = a^\prime \cdot 25 + b^\prime$ and similarly at other breakpoints), you can use an SOS2 constraint to model this. Let $p_0, \dots, p_n$ be the breakpoints ($n=4,\,p_0 = 15,\,p_4 =55$ in your example) and $\gamma_0 \dots, \gamma_n$ be the values of the $y$ function at $p_0, \dots, p_n$. Add continuous ...
2
There are different approaches to solve MILP problems since you didn't mention what kind of solver you are using i assume you mean in context of branch and bound solver.
Feasible solutions are found using a feasibility pump which tries to guess a low feasible solution.The feasibility pump could be positively affected by those additional constraints as a part ...
1
I'm not an expert in Vehicle Routing Problems, maybe someone else will have something more relevant to propose.
I think that a good starting point is this article:
"Efficiently solving very large-scale routing problems" (Arnold et al., 2019) DOI PDF
This paper is not exactly about your problem, but about the Capacitated Vehicle Routing Problem (...
1
I'm assuming in what follows that all demands must be met.
R has a very good genetic algorithm package ("GA") that includes support for permutation chromosomes. Assuming $n$ destinations and $m$ vehicles (not vehicle types, but actual vehicles), you can use a GA with each chromosome a permutation of $1, \dots, n + m$. To decode a chromosome, use ...
1
I'm not aware of any solver that can exploit a lower bound to a minimization problem. (An upper bound can be used to prune the search tree, assuming you are using branch-and-bound/branch-and-cut.) CPLEX, for instance, will let you supply the lower bound via the LowerCutoff parameter, but it only uses that information in a maximization problem.
Only top voted, non community-wiki answers of a minimum length are eligible
