New answers tagged

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 ...


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".


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 ...


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. ...


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:


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 ...


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 ...


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}


5

You can formulate this as an instance of the quadratic assignment problem by duplicating the workers and incurring the batching cost only for pairs of duplicate workers. Here's an alternative MIQP formulation that does not double the number of workers. Let binary decision variable $x_{i,j}$ indicate whether job $i$ is assigned to worker $j$. The problem ...


3

Yes, your proposal suffices. But the published second constraint is stronger, yielding a tighter formulation. You can think of it as a lifting obtained by using the first constraint.


4

Introduce a binary variable $\delta_t$ to represent which case it is and $z_t$ to represent the modelled product, and your MILP model of the piecewise-affine dynamics would be ${EP}_t\ =\ \sum_{i=1}^{n}{x_ic_i^t}\ -L_t + z_t\\ {EP}_{t-1}\leq (1-\delta_t)M, -(1-\delta_t)M \leq z_t - s_t{EP}_{t-1}\leq (1-\delta_t)M\\ ~{EP}_{t-1}\geq -\delta_t M, -\delta_tM \...


1

Some modeling languages allow max and then you do not need to use big M. With CPLEX in OPL you can write int nbKids=300; {int} buses={30,40,50}; dvar int+ nbBus[buses]; dvar int maxNbOfBusesGivenSize; minimize maxNbOfBusesGivenSize; subject to { maxNbOfBusesGivenSize==max(i in buses) nbBus[i]; sum(i in buses) i*nbBus[i]>=nbKids; } execute ...


6

You can ask Gurobi to do this for you https://www.gurobi.com/documentation/9.1/refman/preqlinearize.html Whether a linearization leads to better or worse performance is almost impossible to know beforehand. You will simply have to test. Cplex for instance uses an ML-trained classifier to make this decision, indicating that it is hard to come up with any ...


3

You could try fudging the objective function by replacing any zero cost with a cost of $\epsilon > 0$, where $\epsilon$ is chosen small enough not to cause the selection of a suboptimal solution but large enough that $\epsilon * (z-\max_i a_i)$ does not look like rounding error to the solver. Selecting $\epsilon$ is a bit of an art form, but if this works ...


6

If you want $z=\max(a_1,\dots,a_n)$, you can first enforce $z\ge\max(a_1,\dots,a_n)$ via linear constraints: \begin{align} z &\ge a_i &&\text{for all $i$} \tag1 \end{align} If you cannot rely on the objective to also enforce $z\le\max(a_1,\dots,a_n)$, let $M$ be a small constant upper bound on $z$, let $\ell_i$ be a constant lower bound on $a_i$, ...


5

With the natural binary decision variables $x_{s,u}$, $y_{u,g}$, and $z_{s,g}$ you had defined earlier, the problem is to maximize $\sum_u q_u$ subject to \begin{align} q_u &= \frac{\sum_s h_{s,u} x_{s,u}}{\sum_s h_{s,u} (1-x_{s,u})} &&\text{for all $u$} \tag1 \\ \sum_g y_{u,g} &= 1 &&\text{for all $u$} \tag2 \\ \sum_g z_{s,g} &= ...


3

The best way to solve this in general is to reformulate this to an MILP. Although the reformulation itself is easy, it's also incredibly easy to make a mistake/forget to take something into account. Since this is a toy problem, I will provide a solution that will work for any problem that has the structure $xy, y\in\{0,1\}$, including your actual problem. ...


5

You can linearize the constraint by introducing a nonnegative variable $z_i$, replacing $x_i y_i$ with $z_i$, and imposing linear big-M constraints \begin{align}x_\min y_i &\le z_i \le x_\max y_i\tag1\\ (0-x_\max)(1-y_i) &\le z_i - x_i \le (0-x_\min)(1-y_i)\tag2 \end{align} Constraint $(1)$ enforces $y_i=0\implies z_i=0$. Constraint $(2)$ enforces $...


3

This is a tough problem indeed, but I am not sure about the "extremely NP-hard" part :). All problems which are NP-hard are...very hard. This looks like a multi-commodity flow problem, one commodity per depot. It is natural to decompose such a problem as follows. For each customer $v\in V$, for each commodity $k\in K$ we assume that the demand $D_{...


3

Set boolean=True for the matrix variable P, and use the constraints you have proposed.


5

Assuming your index goes from 0 to $n$ you can do $k = \sum_{i = 0}^{n}i \cdot p_i$ where $k$ is the desired index.


5

My interpretation is that you want $y$ to be $i$ if $p_i=1$. You can do that with a simple multiplication $y=c^Tp$ where the constant vector $c$ is given by $c_i=i$.


10

I recommend a third approach, similar to yours but linear: \begin{align} x + 1 - y &\le M_1 z \tag1 \\ y + 1 - x &\le M_2 (1-z) \tag2 \\ \end{align} Constraint $(1)$ enforces $z=0 \implies x + 1 \le y$. Constraint $(2)$ enforces $z=1 \implies y + 1 \le x$. This idea goes back at least to Manne, On the Job-Shop Scheduling Problem (1960). In some ...


3

If I understand the problem correctly, the $y$ variables decide which components of $x$ are non-zero, and the rest is essentially some variant of a least-square problem. There are several ways you can prevent a solution $x^{*}, y^{*}$ from deviating too much from a previous solution $\bar{x}, \bar{y}$. Adding extra constraints Restrict the number of ...


0

You should model this using a set of constraints. Off the cuff you could try this: \begin{equation} \begin{array}{ll} \text{minimize} & \sum_{i} c_ib_i \\ \text{subject to} & a \leq A_i \rightarrow b_i = n_i \end{array} \end{equation} where $A_i$ is meant to be the path allocation and $n_i$ the number of boxes assigned. The $\rightarrow$ constraint ...


3

You can introduce a binary variable $x_k$ and linear constraints \begin{align} \sum_k x_k &\ge N\tag1\\ -t_k+T_k&\le M_k(1-x_k) &&\text{for $k\in K$}\tag2 \end{align} Here, the “big-M” constant $M_k$ is a small upper bound on $-t_k+T_k$. Because $t_k\ge 0$, you can take $M_k=T_k$, and the constraint simplifies to $t_k\ge T_k x_k$. Constraint $...


2

Welcome to OR Stack Exchange. Your question is not clear. You are interested in special points in discrete optimization spaces. But you describe a mixed-variable problem involving both continuous variables $x$ and integer variables $y$. For a given $y$, the theory of calculus of variations applies to the continuous subproblem on $x$. But I don't think you ...


3

Such a problem is difficult to model and solve following a MILP approach, as you observed. Boolean modeling approaches are tedious to write and don't scale well for this kind of problem. Your problem can be modeled compactly by following a list-based modeling approach instead of the classical Boolean modeling approach, as you described in your question. This ...


3

since you deal with scheduling on top of MIP you could try CPOptimizer scheduling. For instance you could start with https://github.com/AlexFleischerParis/howtowithopl/blob/master/tspcpo.mod using CP; int n = ...; range Cities = 1..n; int realCity[i in 1..n+1]=(i<=n)?i:1; // Edges -- sparse set tuple edge {int i; int j;} setof(...


1

You did not define all your symbols, so I am going to infer from the model that $t_{ij}$ is the transition time from item $i$ to item $j$ (a parameter) and $s_i$ is the time that item $i$ is processed (a variable). Assuming that is correct, your objective function looks unlikely to be correct. The sum of the start/end times has no intrinsic meaning. It is ...


2

As pointed out by A.Omidi in the comment above, your problem is a Capacitated Vehicle Routing Problem with Time Windows (CVRPTW). It can be naturally modeled by following a list-based modeling approach. This is a modeling approach offered by LocalSolver, which is different from traditional solvers. Note that LocalSolver is commercial software. Nevertheless, ...


Top 50 recent answers are included