New answers tagged

4

joni's answer is correct. However, this formulation will not allow you to find an optimal solution for anything more than 10-12 teams, even without any additional typical sports scheduling constraints. If you aren't using a commercial solver, the limit is even lower. There is an excellent book about round robin scheduling by Dirk Briskorn. It is a must-read ...


5

If I understood you correctly, you could do it like this (assuming that $n$ is even and $m = n-1$) First, add the binary variables $$ \begin{align} h_{is} &= \begin{cases} 1, &\text{if team $i$ plays at home in round $s$ and $s-1$}, \\ 0, &\text{otherwise}, \end{cases} \\\\ % a_{is} &= \begin{cases} 1, &\text{if team $i$ plays away in ...


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


1

Is the following model correct? Consider $\delta_i$ as binary variables, whereas $x_i$ and $y_1$ are continuous. \begin{equation} x_1 = a \delta_1 + y_1 \end{equation} For the first if statement: \begin{equation} \begin{matrix} c - M(1 - \delta_2) \leq x_2 \leq c + M\delta_2\\ d - M(1 - \delta_3) \leq x_3 \leq d + M\delta_3\\ \delta_2 + \delta_3 \geq2\...


5

Introduce four binary variables indicating which region you are in and the function value. $$\begin{align} \delta_1 &\rightarrow x_2\geq c, ~x_3\geq d, ~x_1 = a\\ \delta_2 &\rightarrow x_2\geq c, ~0\leq x_3 \leq d, ~x_1 = bx_3\\ \delta_3 &\rightarrow x_2\leq c, ~x_1 = 0\\ \delta_4 &\rightarrow x_3\leq 0, ~x_1 = 0 \end{align} $$ You are in ...


8

Again, you need to introduce binaries: $\delta_t$ takes values $1$ if and only if the device is switched off at time $t$ $\alpha_t$ is the binary associated with variable $x_t$ $\beta_t$ is the binary associated with variable $y_t$ The condition can be written in conjunctive normal form as follows: $$ (\alpha_{t-1}\wedge \lnot \alpha_{t} \wedge \lnot \...


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


5

You can model this as follows. Let $y(t)\in \{0,1\}$ be a binary variable that is activated if the heating device is switched off at time $t\in \{1,...,288\}$ (and was active at time $t-1$). This variable is activated every time $x(t-1)=1$ and $x(t)=0$: $$ x(t-1) \le x(t) + y(t)\quad \forall t=1,...,288 $$ So if $x(t-1)=1$, either $x(t)$ also takes value $1$ ...


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


1

I don't think weeding "outliers" will get you to a fair comparison, given that some stores have larger sales than others. A somewhat crude alternative is to compute two average sales per period figures for every store, one for a time period before the marketing campaign and the other for the time period containing the marketing campaign. Then ...


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


5

You want to enforce $$x_I=\max(x_P-C,0).$$ See https://math.stackexchange.com/a/4086955/683666, where the various big-M values are specified explicitly. More generally, see Linearizing a Max Function in the constraint - not working to linearize the max of $n$ linear functions.


4

You can model it by adding a binary variable $b$ and the following four constraints. $$ \begin{align} x_I &\geq x_P - C & x_I &\geq 0\\ x_I &\leq x_P - C + Mb & x_I &\leq M(1-b) \end{align} $$ where $M$ is a big constant. Note that if $x_P > C$, $b$ can't be $1$ as otherwise $0\geq x_I > 0$, which would lead to infeasibility. ...


3

Assuming $x_p$ is a continuous variable, you could use the following big-M inequalities: \begin{align} C - M_2(1- y) &\le x_p \le C-1 + M_1 y \\ x_p - C - M_4(1-y) &\le x_I \le x_p - C + M_3(1-y) \\ 0 & \le x_I \le M_5y \\ y &\in \{0,1\} \end{align} So if $y=0$, $x_P \le C-1$, or by contrapositive, if $x_P \ge C$, $y=1$. And if $y=1$, then $...


3

In addition to @LocalSolver's answer, I believe you can solve your problem relatively easily with the or-tools routing library (free and open source). At its core, this library solves a TSP, over which you can add constraints with a resource based logic. For example, the load on a vehicle is a resource, this resource is incremented when visiting a node, and ...


1

@RobPratt's answer is obviously the correct answer to this question and is also more general than this one, however, I think this answer can supplement it as it is specific to the OP's case and it also gives a simple thought process to arrive at the result. The way I think about it is, that you would like to have less than two facilities open from each set $...


4

Welcome to OR.SE. It is not easy to enter into your problem and your model. You have modeled your problem in MILP, with each edge represented as a 0-1 variable. There are different possible formulations. All will be tedious to implement, even more if you have many constraints to implement. To make it easier and more scalable, we suggest you follow a ...


3

Here's a way to formulate a more generic constraint that you can then apply to your situation. Suppose you have constant $b$ and binary variables $y_r$ and $z$ and want to enforce $$\sum_{r\in R} y_r \ge b \implies z=1$$ The contrapositive is $$z = 0 \implies \sum_{r\in R} y_r \le b - 1$$ You can enforce this via an indicator constraint or by using the ...


Top 50 recent answers are included