32 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 ...
  • 3,943
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 ...
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 ...
  • 34.9k
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 ...
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 ...
  • 34.9k
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 ...
  • 3,409
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 ...
  • 34.9k
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. ...
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 ...
  • 34.9k
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 ...
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 ...
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, ...
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 ...
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
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,...
  • 26.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 ...
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 ...
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 ...
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 ...
  • 11.7k
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 ...
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. ...
  • 34.9k
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 ...
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 ...
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.
  • 26.4k
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 ...
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 ...
  • 26.4k

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