# Tag Info

27

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 shortest tour) Heuristic: Algorithms that do not give any worst-case guarantee whatsoever. Finite convergence and runtime are separate from "exactness" ...

26

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 ...

25

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 diagrams scalable, we can use relaxed decision diagrams which allow merging nodes that are not necessarily equivalent. Relaxed decision diagrams provide dual ...

21

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 handle (since I have a license for CPLEX and I'm familiar with it)? If CPLEX can handle it, should I consider a heuristic, metaheuristic or constraint solver to ...

19

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 LKH (Lin-Kernighan-Helsgaun) heuristic described in this paper: K. Helsgaun (2000). "An Effective Implementation of the Lin-Kernighan Traveling Salesman ...

17

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 be defined in a way that is both computationally convenient (moving from one solution to a "neighboring" solution is straightforward and does not ...

15

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 dynamic programming model). For instance, it is the case for the maximum independent set problem and the maximum cut problem. It is also the case for some ...

15

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 have both an upper bound and a lower bound on the optimal objective value, using a method called reduced cost fixing (see e.g. Atamtürk, Nemhauser & ...

15

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 problem (UFLP), the most common Lagrangian approach relaxes the assignment constraints ($\sum_j y_{ij} = 1 \ \forall i$), uses the Lagrangian subproblem to calculate ...

15

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

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 ...

14

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, $r_{i,i}$ corresponds to $b_i$ in the other formulation.) For $i \le j < k$, let binary variable $t_{i,j,k}$ indicate that the bin represented by item $i$ ...

14

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 solution has an objective better than that of x*. Typically, exact methods compute two types of bounds: lower (L) and upper (U) bounds. Optimality is then proven whenever both bounds coincide. In ...

14

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, dualizing it, and then enforcing integrality again on the dual variables. It is already trickier which variables to consider as integer in the dual when you dualize ...

13

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 guarantee).

13

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 vertex exactly once. This problem is NP-complete (see link). If you could determine the longest path efficiently, you could do so for every starting point and ...

13

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 does not have that many possible solutions. Case 1: $C = 1$ This only happens when $y=0$ or $y = x$. Assume that we have some upper bounds $\bar{x}$ and $\bar{y}... 13 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 make planning-level decisions. The online problem is solved as real-time information comes in, and tells us what to do at the low level (as in which vehicle should ... 13 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 combination of the extreme points of the polygon defined by the constraints of the problem. Column generation : once this change of variables has been done, you ... 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&... 12 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 function). The literature about this problem may contain a DP, too. 12 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. In one approach, you create continuous variables for each vehicle representing the time the vehicle begins charging, the time it ends charging, and the time it ... 11 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 software around for this type of problem (just google course scheduling software). It's also very similar to sports scheduling (e.g. how the NFL schedule is ... 10 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$,$w_{a2}=1$,$w_{b1}=100$, and$w_{b2}=2$. In this case matching$\{a2,b1\}$of value$101$is the only stable one but the minimum-weight matching is$\{a1,b2\...

10

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 comments) has polynomial runtime. But the term is often misused to refer to a heuristic that may or may not have such a provable bound. I would have interpreted ...

10

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 duration $w_o$, each bin is a machine that is available for only $c_b$ time units, and $z$ is the makespan. It is also a special case of the bottleneck ...

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 ...

9

As observed by Kevin Dalmeijer, you cannot expect an efficient method unless $\sf{P=NP}$. Since you're asking explicitly for dynamic programming: define $C(s,t,V)$ as the longest path from $s$ to $t$ without visiting the vertices in $V$. Values $C$ satisfy \begin{align*} C(s,t,V)= \begin{cases} \max\limits_{u\in N^{-}(t)\setminus V} C(s,u,V\cup\{t\})...

9

vOptLib: Library of numerical instances for MultiObjective Linear Optimization problems From the site: vOptLib (short for vector optimization library) is a collection problem instances for benchmarking multi-objective solvers. It covers a variety of Multiobjective linear optimization problems (multiobjective combinatorial problems, multiobjective ...

9

I'm looking at the algorithm as it's described in Hochbaum (1982), which works like this: Suppose we have enumerated all $2^n-1$ subsets of the customers. Subset $P_m$ has cost $$C_m = \min_{j\in J} \left(\sum_{i\in P_m} c_{ij} + f_j\right),$$ i.e., the fixed plus transportation cost if we choose the best facility for the set $P_m$ of customers. At each ...

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