12
In my opinion, @Erwin Kalvelagen's blog is a great resource for learning mathematical modeling.
He posts a variety of tricks and tips, compares different models with one another, different solvers, etc.
What is great about the blog is that its not just textbook theory, its operational research exploration which challenges and/or verifies textbook theory.
...
6
Honestly, there is not that much in general that I am aware of. The best resource (other than the ones you mentioned) that comes to mind is Fischetti's modeling book "Introduction to Mathematical Optimization", which gives a good overview over many standard problems and various formulations.
Otherwise I can recommend some specific ones:
LP tricks ...
6
You want to enforce $X(k) = 0 \implies R(k) = 0$ and $X(k) = 1 \implies R(k) \le G(k)$. You can use indicator constraints for that.
Alternatively, a straightforward big-M formulation yields
\begin{align}
R(k) &\le M_1(k) X(k) \tag1 \\
R(k) - G(k) &\le M_2(k) (1 - X(k)) \tag2 \\
\end{align}
A natural choice for $M_1(k)$ is a small constant upper ...
6
If I understand correctly, the following enforces your desired behavior:
\begin{align}
y_1 &= d_1 \\
y_2 &= d_2 \\
y_3 &= d_3 \\
y_4 &\ge d_1 + d_2 - 1\\
y_5 &\ge d_1 + d_2 + d_3 - 2\\
\end{align}
If you also want to enforce
$y_4 \implies (d_1 \land d_2)$
and
$y_5 \implies (d_1 \land d_2 \land d_3)$,
then include these additional ...
5
Consider the only two possible cases:
If $x_i=0$ for all $i$, then $(1)$ and $(3)$ both reduce to $\sum_j a_j y_j \le b$.
If $x_i=1$ for some $i$, then $(2)$ implies that $x_k=0$ for all other $k \not= i$, and $(1)$ and $(3)$ both reduce to $1+\sum_j a_j y_j \le b$.
Alternatively, you can think of lifting $x_i+\sum_j a_j y_j \le b$ to $\alpha_k x_k + x_i+\...
5
If I understand correctly, you can obtain the desired linear constraints via conjunctive normal form. Explicitly, suppose $f(\bar{x}_1,\dots,\bar{x}_n)=1$, and let $S_0 = \{j\in\{1,\dots,n\}:\bar{x}_j = 0\}$ and $S_1 = \{j\in\{1,\dots,n\}:\bar{x}_j = 1\}$. You want to enforce $$\left[\left(\bigwedge_{j\in S_0} \lnot x_j\right) \bigwedge \left(\bigwedge_{j\...
4
To be clear, you have a set $S$ of nodes of a graph $G=(V,A)$, with $S\subseteq V$, which must be visited. There is a special node $O$, which must be the starting point of a tour. A tour visiting the nodes in $S$ starting from $O$ (but not returning to $O$) at minimum length must be found? If that is the case, I think the easiest way is to compute an all-...
4
By Farkas lemma, infeasibility of $Ax\leq b$ is equivalent to feasibility of $A^Ty = 0, y^Tb < 0, y\geq 0$, or more practically useful $A^Ty=0, y^Tb \leq -1, y\geq 0$.
Unfortunately, this will lead to a bilinear model when you parameterize $b(z)$. It is fairly similar to an application I worked on a decade ago Oops! I cannot do it again:
Testing for ...
4
Although focused on implementing the model in YALMIP instead of CVX (converting the code should be trivial), precisely this case is described in the following tutorial https://yalmip.github.io/modellingif
You basically introduce a binary variable $\delta_i$ for each region, and then add the implications that $\delta_i \rightarrow \{\text{cost} = f_i(x), x \...
4
Rank-one constraints are unfortunately not mixed-integer convex representable, as shown in this paper: https://arxiv.org/abs/1706.05135, although they are quadratically-constrained quadratic representable.
If the problem size is not too large, you can try solving it using Gurobi, either directly (for n<=10) or via branch-and-cut (for say n<=50; see ...
4
You might find OptaPlanner's domain modeling guide (Docs section 20.2) useful.
It's a step by step guide on how to design a good model - and explains why some models are better or worse than others. Here's a few examples of good vs bad models:
3
There's also the Octeract Reformulator repository, where we host a growing collection of scripts to automatically apply reformulations to non-linear problems, e.g.:
from octeract import *
# Linearize bilinear term x*y where x,y binary
# =============================================
# x*y = w
# w <= x
# w <= y
# x + y - 1 <= w
# 0 <= w <= 1
# ...
3
I would also add "Optimization in Engineering" as a reference. It offers a good overview on LPs, MILPs and convex programming, focusing on applications. It is also a good resource in best practises, see for example Chapter 3.3 "Linearizing Nonlinearities Using Binary Variables".
3
Yes, this is correct and is the classical approach from Manne, On the Job-Shop Scheduling Problem (1960).
In some modeling languages, you can also enforce these implications by using indicator constraints:
\begin{align}
y = 0 &\implies t_i + d_i \le t_k \\
y = 1 &\implies t_k + d_k \le t_i \\
\end{align}
3
https://en.m.wikipedia.org/wiki/Diophantine_equation
any milp solver can handle it, but maybe something like mathematica/mable has special algortihms or one can use the algorithm described by the wiki entry
4a) https://en.m.wikipedia.org/wiki/Lattice_problem
4b) is i think polytime, either the problem is unbounded, infeasible or all solutions are optimal.
3
You are not going to be able to add these logs and quadratic terms to the model via simple double-sided big-M constraints, as they generate non-convex use of convex quadratics and logs, and CVX does not support that. The use of the squared log is not possible either. I don't think it supports automatic modelling of nonconvex use of abs operator either.
Most ...
3
If the set $S$ of nodes to be visited is not too large, you can solve $|S|$ shortest path problems with additional constraints imposing a visit to some nodes.
With your example, $|S|=|\{A,C \}|=2$ so it is not too bad. 1/ Find the shortest path from $O$ to $A$, while imposing a visit to node $C$. 2/ Then find the shortest path from $O$ to $C$, while ...
2
you could try constraint programming / scheduling within CPLEX and use noOverlap to model the time matrix.
In OPL that gives
using CP;
execute
{
cp.param.timelimit=10;
}
{string} nodes={"O","A","B","C","D","E","T"};
tuple edge
{
key string o;
key string d;
int time;
}
{edge} ...
2
I think your third constraint should be + 1, not - 1, on the right hand side. As stated, it says you enter destination nodes one time fewer than you exit them. You want to enter one time more.
Fixing that will make the optimal solution feasible, but it will not make the model correct. There still remains the possibility of a solution that is not a contiguous ...
2
I think this can be approached using a constraint generation technique (variant of Benders decomposition), although I have no idea if it would efficient. By reordering the rows of $A$, we can assume that $$b(z)=\left[\begin{array}{c}
\hat{b}\\ c+e-z \end{array}\right]$$where $\hat{b}\in\mathbb{R}^{d-m}$, $c\in \mathbb{R}^m$, $e=(1,\dots,1)^\prime \in \mathbb{...
2
For the case of mixed integer programs, I would recommend the following paper:
Klotz, E., & Newman, A. M. (2013). Practical guidelines for solving difficult mixed integer linear programs. Surveys in Operations Research and Management Science, 18(1-2), 18-32.
As the abstract says:
"Even with state-of-the-art hardware and software, mixed integer ...
2
If the constants are such that the cost function is convex (e.g., $b=0$, $c=-25$, $d=-1775$), you could minimize a variable $z$ subject to
\begin{align}
z &\ge 10p + b \\
z &\ge 15p+c \\
z &\ge 20p^2 -10p +d \\
z &\ge 0
\end{align}
With the above values, the cost function is the maximum of the curves in the figure below:
EDIT:
With the ...
2
It sounds like you want to pack $N$ rectangles with given dimensions $w_i \times h_i$ in a $W \times H$ rectangle, as discussed here. To allow each rectangle to be rotated 90 degrees (with dimensions $h_i \times w_i$), you can introduce a binary variable $r_i$ to indicate whether to rotate rectangle $i$ or not. Then modify the constraints like this:
\begin{...
2
Can't you add a parameter to your model which defines the nature of your variables ?
Something like :
def my_model(model, continuous):
...
if continuous:
model.my_variable = Var(within=NonNegativeReals)
else:
model.my_variable = Var(within=PositiveIntegers)
...
and then model.solve().
I am not so familiar with Pyomo but with PuLP,...
2
You may also use CPOptimizer within CPLEX that contains scheduling high level concepts. And then you can directly use noOverlap constraints.
In
using CP;
dvar interval i size 5;
dvar interval k size 4;
dvar sequence seq in append(i,k);
minimize maxl(endOf(i),endOf(k));
subject to
{
noOverlap(seq);
}
the constraint
noOverlap(seq);
makes sure that i ...
Only top voted, non community-wiki answers of a minimum length are eligible
