New answers tagged combinatorial-optimization
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 ...
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&...
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 ...
25
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 ...
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
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 ...
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.
...
2
I am pretty sure, this is not the best way to tackle such a problem, specifically from the computational complexity point of view, but at least it might be represented as an effort to solve small-scale problems. As you mentioned:
All the vehicles have the same maximum capacity $J$
Each customer gets a single package so that n packages are delivered...
I ...
2
In preliminary tests, a greedy heuristic seems to do rather well for the problem.
The greedy heuristic I tried starts out with each transmitter being a cluster of size 1, and then loops indefinitely. In each pass through the loop, all pairs of clusters are considered for merging. Any merger that would result in a cluster that exceeds the cluster size limit ...
2
This can be formulated as a MIP model using a gaggle of binary variables. First, we introduce some parameters. $\tau(u)$ is the index of the transmitter with highest weight for user $u$. I will charitably assume this is unambiguous (no ties for closest transmitter). $\overline{Q}_u$ is an upper bound on the possible values of $q_u$ for user $u$. $C$ is the ...
3
Say your variables are $x_1,\ldots, x_n$. The first constraint could be modeled as $$\sum_{i=1}^n x_i \leq C.$$ This makes sure that not more than $C$ variables are chosen.
If understood your question correctly the optimal solution may only have non-zero values for variables in the same group and not all variables from the group are mandatory to be selected....
Top 50 recent answers are included