# Tag Info

26

As someone who uses a lot of commercial/open-source OR software and incidentally tried coding my own solver, the underlying question is that of continued funding and support. As mentioned in another answer, LP/MIP solvers have been around for over 30 years (fun fact: technically, solving LPs and MIPs pre-dates software itself). This means continued ...

15

Disclaimer: although I work for Gurobi, the views in this post are entirely my own. I believe there are a few reasons for this trend: First of all, the industries were "born" in different times. Bob Bixby founded CPLEX in 1988 (or thereabouts), while PyTorch was first released in 2016. This also means though that these two industries are in ...

13

Update: Since you updated your question might as well chip in, since I've worked with COIN-OR software a lot at the code level. In my experience, a lot of the open-source optimisation codebases (e.g. CBC) succeed in being amazing solvers, but fail in being great open-source projects. The heart of any successful open-source project (and by "successful&...

11

Here are two ideas: Minimize $\max_g T_g$. This will naturally even out the productivities of each group. To do this you can minimize a variable $z$ and add the constraint $z \ge T_g \; \forall g$. Add constraints $T_{min} \le T_g \le T_{max}$ where $T_{min}$ and $T_{max}$ are lower and upper bounds on $T_g$, respectively. You will have to determine a "...

10

Disclaimer: I do work for Fico/Xpress, one of the leading commercial optimization solver developers, but this is my own personal opinion. I agree 100% with the comment about where the value is: the model or the algorithms. In ML the value is in the data/mode/computing power, in OR it is more in the algorithms. About cultural differences: if you are an ...

10

There are a number of decisions CPLEX makes that can be affected by "randomness". In some cases, CPLEX is actually using a random number generator to make decisions (such as breaking ties). In other cases, solutions can change when the order of entry of variables or constraints is changed, or when the model is read from a .lp file in one case and a ...

8

Since $W$ is a binary variable, it follows that $$\sum_k \delta_k \le W \le 1$$ And so you are in the presence of a clique constraint. @RobPratt shows how to strengthen the second group of constraints in this case, yielding the first constraint. A simple example : take $\delta_k = 0.9$ for every $k$. It is easy to see that such a solution is valid with the ...

7

It is possible (but a bit tricky) to write a mixed-integer linear program for this problem. If you are willing to accept a good but not guaranteed optimal solution, though, the GA is easily modified to handle it. The key is to use a chromosome of 10 real values, where the sixth through tenth are rounded down to the next lower integer and used to index a ...

7

This is similar to the well known Zebra Puzzle. You can solve it using integer programming techniques as follows: Define binary variables $x_{p,n}^h$ that take value $1$ if and only if player $p\in \{Bill,...,Tony\}$ has nickname $n \in \{Slats,...,Tree\}$ and height $h \in \{6,...,6'6 \}$. So $x_{p,n}^h=1$ if and only if combination $(p,n,h)$ is valid. ...

7

Something like: \begin{align} & c_i \le x_i + M(1-y_i)\\ & c_i \le My_i \end{align} $M$ can be interpreted as an upperbound on $c_i$. If you don't like the big-$M$'s, consider using indicator constraints. See the comments below for some improvements on this!

6

By request, here's the SAS code I used for three different objectives (the first two are commented out with /* and */ delimiters): proc optmodel; num numMachines = 21; num groupSize = 3; set MACHINES = 1..numMachines; set GROUPS = 1..numMachines/groupSize; call streaminit(1); num p {MACHINES} = rand('INTEGER',0,10); print p; var X {...

6

This is a well-known problem with existing heuristics: https://en.wikipedia.org/wiki/Multiway_number_partitioning Edit: For partitioning into groups of limited sizes (eg. $S_{max} \le M/G+1$) see https://en.wikipedia.org/wiki/Balanced_number_partitioning and in the special case of partitioning into groups of $S \le 3$ see: https://en.wikipedia.org/wiki/...

6

For your first question, let binary decision variable $y_{i,g}$ indicate whether variable $x_i$ is assigned to group $g$, and let variable $z_g$ represent the common value of variables in group $g$. You want to enforce: \begin{align} \sum_g y_{i,g} &= 1 &&\text{for all $i$} \tag1 \\ \sum_g y_{i,g} z_g &= x_i &&\text{for all $i$} \...

5

Minimize the greatest $T_g$: \begin{align}\min&\quad T_\text{max}\\&\quad T_g \le T_\text{max} \qquad \forall g\end{align} The drawback is that it will minimize $T_g$, and maybe it is not what you want As @RobPratt suggested in the comments, minimize the difference between the greatest and the smallest $T_g$: \begin{align}\min&\quad T_\text{...

5

The two denominators are equal to $1$, so just omit the denominators, yielding a linear constraint.

5

This problem can be elegantly formulated through Constraint Programming (CP). This problem does not have an objective function: it's a Constraint Satisfaction Problem, not a Constraint Optimization Problem. CP would be a natural choice for this problem, since CP, similar to how humans would solve this problem, relies on a technique called 'inference'. In CP, ...

4

Let $\overline{P}$ be the average (mean) productivity of all machines. The average productivity of a group will be $S\overline{P}$. Let $y_g$ be nonnegative variables defined by the constraints $$y_g \ge T_g - S\overline{P}$$ and $$y_g \ge S\overline{P} - T_g$$ for all $g$. In the solution, $y_g$ will be $\vert T_g - S\overline{P}\vert$. You can minimize $\... 4 IMHO, whether the vehicle arrives before$a_i$and waits there or takes a break a block away and then shows up right on time is a matter of execution rather than something that should be explicitly enforced in the optimization model. Just tell the driver not to loiter at the node. 4 I assume that$y$is constrained to the interval$[0,1]$. (You did not state this explicitly.) Let's assume that you have selected values$r_i$such that$0=r_1 < r_2 < \dots < r_n = 1.$If your solver supports SOS2 constraints, you can make$w_1, \dots, w_n$nonnegative variables with the constraint$\sum_i w_i = 1$and declare$\lbrace w_1,\dots,...

4

Adding the last constraint is required to guarantee that only one of the $r_i$ values is selected for $y$. However, you need an additional constraint to make the relationship between $y$, its piecewise linearisation variables and the remaining of the problem constraints (especially $y=f(x)$), such as: $$y = \sum_{i=1}^{n} r_i \times w_i$$

4

You can solve this using a constraint satisfaction/constraint programming (CP) solver (and possibly modeling language). In R, you might use the rminizinc package package, which links to the open-source MiniZinc language, which comes with a number of solvers. CP models (which can be optimization models but are often just constraint satisfaction models) can be ...

3

It seems to me like there are three worlds in OR: users of commercial MIP/LP solvers like Cplex or Gurobi users of free / open-source MIP/LP solvers users of other type of solvers - constraint solvers, sat solvers ... I'm in third group since I focus on constraint solvers, and help choco solver and or-tools solvers to be better. Without source codes it ...

3

So the routing library does not use a MIP solver to solve TSP/VRP... problems. So the assumptions of lazy callbacks is just false. The question of goal programming is not that clear. You should look at the routing API. The linear solver wrapper do support callbacks for Gurobi and SCIP, but if you plan on using Gurobi, you should stick to the gurobi API My ...

3

You can check out the MINOTAUR codebase, it's pretty well written and designed for people to create their own algorithms. Last time I checked (a few years ago), it wasn't very well documented, but the code itself is very readable and very well designed. The fastest way to get started is to check out their examples of how to create new algorithms (e.g. this ...

3

Depending on the solver used, you may be able to prioritize the $x$ variables so that variables with higher indices are branched on before variables with lower indices (and elements of $x$ are branched on before any other integer variables). You may also be able to instruct the solver, after branching on $x_i$, to prioritize the child with $x_i=1$ over the ...

3

Without the entire problem description it is hard to provide a complete answer, but you will probably need a variable $x_t \in \mathbb{N}$ for the number of operators hired at time period $t$. With these variables, and taking into account the fact that once an operator is hired, he is hired for the entire time period, the extra cost at a given time $t$ ...

2

Have you tried considering it as a waiting_time_cost? Take a look at this work by Cordeau et al. http://www.bernabe.dorronsoro.es/vrp/data/articles/VRPTW.pdf On page 23, on the Time- and Load-Dependent Costs section, the authors explain how waiting_time / linear waiting cost can be taken into account. They also cite the work of Desaulniers, Lavigne, and ...

1

While I agree with @RobPratt on this one, the following tweak to your model should work. Add a variable $z_i$ representing the combination of service time at $i$ and time spent loitering (somewhere) after serving location $i$. Change your first constraint to $$w_{ik} + z_{i} + t_{ij} - w_{jk} \leq (1 - x_{ijk})M_{ij}$$ and add the constraint w_{ik} + z_{i} ...

Only top voted, non community-wiki answers of a minimum length are eligible