# Tag Info

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,343
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,685
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 ...

### 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 ...
• 31.1k

### 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 ...
• 2,769

### 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 ...
• 31.1k

### 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,359
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 ...
• 31.1k

### 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.3k

### 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
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,254

### 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 ...
• 12.6k
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,809
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,527

### 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 ...
• 31.1k
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,...
• 22.7k

### 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,519

### 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,335

### 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 ...
• 5,893

### 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 ...
• 5,893
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.3k
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 ...
• 10.4k

### 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,809
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. ...
• 31.1k

### 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.3k

### 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 ...
• 291

### 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,685

### 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 ...
• 12.6k
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 ...