# Tag Info

26

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

24

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

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

14

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

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

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

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

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

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

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

9

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

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

9

Your problem is equivalent to finding a maximum weighted independent set in a hypergraph, where each item is a vertex and every forbidden set is an hyperedge over the elements in the set. This is a hard problem, not just NP-hard (since it is a generalisation of the NP-hard weighted independent set problem), but also NP-hard to approximate within a constant ...

9

You can model your problem by defining separate variables for each traveling salesman. Below I will use 'vehicle' instead of 'traveling salesman', which is more common in this setting. Defining separate variables Let $n$ be the number of customers and let $m \le n$ be the number of vehicles. For each vehicle $k = 1, \dots, m$, define the variables x_{ij}^k ...

9

Being a good or bad approach will depend on several factors, for example: the size of the instances time available to find a solution (this tends to be an important matter in vehicle routing applications) computing power what level of solution quality qualifies as good enough See this work by Yu, Nagarajan and Shen on the minimum makespan VRP with ...

9

You can solve the problem via integer linear programming as follows. For each size $s\in\{3,4,5\}$, let $n_s$ be the number of blocks of size $s$ to place. For each cell $(i,j)$ and each size $s \in \{3,4,5\}$, let binary variable $x_{i,j,s}$ indicate whether $(i,j)$ is the top left corner of a block of size $s$. For each cell $(i,j)$, let $B_{i,j}$ be the ...

8

If you are just looking for a formulation here is one (not particularly good due to symmetries, I'll rework it if I can think of something better in this regard). Let $K$ be an arbitrary upper bound on the minimum number of bins needed. Let $a_{i,k} \in [0,1]$ be a binary variable representing the assignment of object $x_i$ to bin $k$. Let $b_{i,j,k} \in [... 8 As other answers have already noted, this problem is NP-hard. That, however, is not the end of the story. The longest path problem has some positive algorithmic results in the context of parametrized algorithms. The main idea is that even though the problem may be NP-hard in general, we can consider a parameter of the input$k\$ and try to develop ...

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