33
votes
Accepted
Why is open source operations research software so far behind open source statistics and machine learning software?
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 ...
- 4,068
28
votes
Accepted
Optimization terminology: "Exact" v. "Approximate"
Exact: algorithm will eventually provide a provably optimal solution.
Approximate: algorithm will eventually produce a solution with some guarantees (e.g. a tour being at most twice as long as the ...
- 2,856
25
votes
Accepted
When are Decision Diagrams the right way to model and solve a problem?
Decision diagrams (DDs) are most effective when they can compactly represent a large (perhaps exponential) set of solutions. This is done by merging equivalent states in each layer. To make decision ...
22
votes
Combinatorial Optimization: Metaheuristics, CP, IP -- "versus" or "and"?
Here, in approximate order, are my criteria.
Do I need a provably optimal solution (which rules out metaheuristics, other than to generate an initial feasible solution)?
Is this something CPLEX can ...
- 37.8k
22
votes
Are Metaheuristics and Evolutionary Algorithms the "Gold Standard" for the Traveling Salesman Problem?
The answer to the question is: No.
(Although one can debate what exactly is a "metaheuristic")
The "gold standard" for finding high quality feasible solutions for the TSP is the ...
- 3,168
19
votes
Why is open source operations research software so far behind open source statistics and machine learning software?
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 ...
- 3,459
19
votes
Python vs C++ performance on Discrete Optimization
If you are using a solver (open-source or commercial) to solve a discrete optimization problem, and if the problem is not trivial or extremely easy, chances are very high that the bulk of the ...
- 37.8k
17
votes
Accepted
Why does the design of heuristics require considerable domain knowledge?
The following is largely opinion/conjecture on my part. Many (though not all) heuristics involve neighborhood search. For that type of heuristic to be effective, you need "neighborhood" to ...
- 37.8k
16
votes
Why is open source operations research software so far behind open source statistics and machine learning software?
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. ...
- 11.9k
16
votes
Is Traveling Salesman Problem "Combinatorial Optimization" or "Integer Optimization"?
I'm not sure that the terminology is used consistently enough to give a firm answer. Pretty much everyone would agree (I think) that the TSP is a combinatorial optimization problem. To me, asking ...
- 37.8k
15
votes
When are Decision Diagrams the right way to model and solve a problem?
I am currently working with decision diagrams (DDs). From my experience, DD-based optimization works well for problems on which a recursive formulation can be exploited (i.e., problems that have a ...
- 151
15
votes
Accepted
Variable fixing based on a good feasible solution
As far as I know, it is not possible to fix any variables solely based on a feasible solution without compromising the exactness of your solution method. However, variable fixing is possible when you ...
- 2,305
15
votes
Variable fixing based on a good feasible solution
A similar idea as suggested by @ RolfvanLieshout uses Lagrangian duals instead of LP duals, in a Lagrangian-based branch-and-bound scheme. For example, in the uncapacitated fixed-charge location ...
- 13.1k
15
votes
Accepted
Duality in mixed integer linear programs
It is a difference whether one can dualize (or not) or that a duality theory holds (or not). Formally, you can formulate a dual of any integer program, e.g., by considering the linear relaxation, ...
- 5,909
15
votes
Modeling the Choose function
I am going to assume that $x \in \mathbb{N}$ and $y \in \mathbb{N}$ are variables, and that $C \in \mathbb{N}$ is a constant. In this case, you can benefit from the fact that your equality constraint ...
- 6,063
15
votes
Accepted
Where can I find resources to learn mathematical modelling for real life operation research problems like combinatorial optimization?
you may get many different answers but the one I have used for 20+ years is
Model Building in Mathematical Programming by H.P.Williams
Many models are in the OPL CPLEX examples and some other here
- 3,990
14
votes
Accepted
Bin Packing with Relational Penalization
Here is a simpler symmetry-less formulation based on the one proposed by @RenaudM. For $i \le j$, let binary variable $r_{i,j}$ indicate that the bin represented by item $i$ contains item $j$. (Here,...
- 30.4k
14
votes
Optimization terminology: "Exact" v. "Approximate"
An exact method will (typically within a bounded number of steps) provide a proven optimal solution. This is, a solution x* and a guarantee that no other feasible ...
- 1,549
13
votes
Optimization terminology: "Exact" v. "Approximate"
Exact: Provably optimal
Approximate: offers an upper bound on the gap
I would add heuristics: procedures that, as you described, may or may not provide an optimal solution (with out any proof or ...
- 1,345
13
votes
Are there any efficient algorithms to solve the longest path problem in networks with cycles?
There is no theoretically efficient method, unless P=NP.
The Hamiltonian Path Problem is the problem of determining whether there exists a path in an undirected or directed graph that visits each ...
- 6,063
13
votes
Accepted
What's the current status of the Vehicle Routing Problem in the logistics industry?
The answer to this question is quite complicated. There are two main types of vehicle routing problems, the offline and the online problem.
Solving the offline problem takes longer and is used to ...
- 11.9k
13
votes
Accepted
Branch and Price algorithm is exact?
To answer your question, it is good to have in mind the following concepts:
Dantzig-Wolfe decomposition : in essence, this is a change of variables. The initial variables are expressed as a convex ...
- 12.9k
12
votes
Bin Packing with Relational Penalization
This is very related to the bin packing with conflicts problem (see eg. here), where you model the conflict as "soft" (with a binary variable to indicate violation, with a penalty in the objective ...
- 5,909
12
votes
Accepted
Finding minimum time for vehicle to reach to its destination
You can solve this with a mixed integer linear program. It has some similarities to job shop scheduling (with parallel machines) and multiprocessor scheduling, although it is not identical to either. ...
- 37.8k
12
votes
Combinatorial problem in my daughter’s class
This is a variant of the University Course Scheduling problem (e.g. this one). Interestingly, writing software to solve this was Bill Gates' first gig when he was still a student.
There is a lot of ...
- 11.9k
12
votes
Why is open source operations research software so far behind open source statistics and machine learning software?
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 ...
- 301
12
votes
Valid Inequality Example (Wolsey Example 9.3)
As @Kuifje suggested, an upper bound $x_i \le 1$ was mistakenly omitted. This omission was noted in this errata sheet, and it was corrected in the second edition of the book.
- 30.4k
11
votes
Why is Discrete Optimization "Difficult'?
Comparing with local minima / saddle points of continuous problems is a bit of a red herring. It's like wondering why people in the stone age had it tough to find food, and comparing with “on Sunday ...
- 219
10
votes
Relationship between the Assignment Problem and the Stable Marriage Problem
You don't get a minimum-weight (perfect) matching by giving preference to smaller weights in the stable marriage problem. Consider $\mathcal{I}=\{a,b\}$ and $\mathcal{J}=\{1,2\}$ and weights $w_{a1}=2$...
- 2,705
10
votes
Optimization terminology: "Exact" v. "Approximate"
In addition to the other answers posted already, I'll add that the term approximation algorithm means an algorithm with a provable worst-case error bound that (as @MarcoLubbecke reminded me in the ...
- 13.1k
Only top scored, non community-wiki answers of a minimum length are eligible