31 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 ...
user avatar
  • 3,343
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 31.1k
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 ...
user avatar
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 ...
user avatar
  • 31.1k
18 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 ...
user avatar
  • 3,359
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 ...
user avatar
  • 31.1k
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. ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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, ...
user avatar
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
user avatar
15 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 ...
user avatar
  • 31.1k
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,...
user avatar
  • 22.7k
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 ...
user avatar
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 ...
user avatar
  • 1,335
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 ...
user avatar
13 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 10.4k
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 ...
user avatar
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. ...
user avatar
  • 31.1k
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 ...
user avatar
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 ...
user avatar
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$...
user avatar
  • 2,685
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 ...
user avatar
10 votes

What's the name of a finite-capacity bin packing problem trying to minimize the weight of the heaviest bin?

Let $w_o$ denote the weight of object $o$, and let $c_b$ denote the capacity of bin $b$. You can interpret this as a job shop scheduling problem. The correspondence is that each object is a job, with ...
user avatar
  • 22.7k
10 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 ...
user avatar

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