New answers tagged

2

Based on the comments, the rent for facility $j\in \lbrace 1,\dots,m \rbrace$ would be $0.1\cdot R \cdot \sum_{i=1}^n d_i x_{ij}$ where $d_i$ is the demand for customer $i$ and $R$ is the rent per square foot. If the rent per square foot varies from facility to facility, just change $R$ to $R_j$. Sum those expressions over $j$ and add the sum to the ...


4

The problem you are proposing is closely related to the Maximum Cut with Limited Unbalance which generalizes both the Maximum Bisection problem and the Maximum Cut problem. The problem is defined as follows. Given vertex set $V$ of cardinality $n$ and edge set $E$, where each edge $(i, j)$ has an integer weight $w_{ij}$, and given a constant $B$, with $0 \...


5

If you have a Max-Cut solver (or even a generic MILP solver) you can dualize the cardinality constraint and apply Dantzig-Wolfe decomposition or Lagrangian relaxation. Explicitly, let binary decision variable $x_i$ indicate whether $i\in A$. The problem is to maximize $$\sum_{(i,j) \in E} (x_i(1-x_j)+x_j(1-x_i))=\sum_{(i,j) \in E} (x_i+x_j-2x_i x_j) \tag0$$...


5

There are a number of metaheuristics that can be applied to this problem. One of them is a genetic algorithm. I'll assume that the vertices are denoted by the integers $1,\dots,N$ with $N=|V|$. To implement a GA, you can define a "chromosome" (solution) to be a permutation of the integers . The fitness of a chromosome is the size of the cut set (or ...


3

Heuristics are "rules of thumb" that in some cases try to estimate some quantity without explicitly computing it. The better the estimate, the better the algorithmic performance, so good heuristics are important. Domain knowledge can help to improve estimates by understanding what is possible or reasonable. Take A* search, for example, which can be ...


6

tl;dr– Having relevant knowledge can help folks come up with better techniques, including heuristic techniques. Relevant knowledge can be useful in problem-solving. Heuristic techniques are those that're somehow fuzzy/approximate/unreliable. The term "heuristic" is basically a disclaimer, qualifying that a technique isn't ideal. Relevant ...


1

Genetic algorithm is a lot wider family of algorithm that is a lot more tuneable. It kinda depends on your problem space whether TABU search is sensible but i would recommend implementing tabu search which basically a variation of random search.


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


Top 50 recent answers are included