19

This is going to be a hand-waving argument: perhaps this has been formalized in the literature someplace. I think the issue is that the linear relaxation is in some sense more compatible with the p-median objective than the p-center problem. Consider the following example (circles are customers; stars are facilities) For the left hand customers, the ...


19

I can see two reasons why branch-and-bound based solvers can have a hard time solving these problems: the linear relaxation may be bad (as stated above); these models have typically (exponentially) many optimal solutions, since the cost only depends on a single variable $y_{ij}$. Thus, you can move one customer to many centers without changing the cost of a ...


11

I will give you a little more insight based on my latest experience solving minimax (or maximin) integer programs. Sorry I will be a bit self-citing here. Indeed, the main reason that can explain the poor behavior of commercial solvers for solving those types of problems is the strong dependence on a single (or a very few) variable for the solution. In p-...


11

You may have a look at our recent work based on Benders decomposition, for the discrete Maximum Coverage Facility Location problem. It works very well if the number of facilities is relatively small, but the number of customers can run in millions… J.F. Cordeau, F. Furini, I. Ljubic: Benders Decomposition for Very Large Scale Partial Set Covering and ...


11

I think I've found an instance with four nodes and $p = 2$ via brute force (a lot of randomized instances). I've attached my Python script as well. I relaxed the Daskin and Maass (2015) formulation and assumed $I = J$. Nodes: $I = J = \{1, 2, 3, 4\}$ Demands: $d = (75, 34, 40, 40)$ Costs (or distances): $$ c = \begin{bmatrix} 0 & 39 & ...


9

It sounds like you are describing either the set covering location problem (SCLP) (Wikipedia entry; canonical citation) or the maximal coverage location problem (MCLP) (Wikipedia entry; canonical citation). The SCLP minimizes the number of facilities subject to a constraint that every demand node is covered; the MCLP maximizes the number of covered demands ...


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


8

An idea could be to evaluate what is the smallest number of straight lines required to cover your locations. You would expect that aligned points are covered with much fewer straight lines than non-aligned points. Moreover, this metric would work for any type of alignment, not just the one that follows the lattice. This paper (Covering a set of points with ...


7

If I understand correctly, you are given a set of demand nodes, and you want to locate a finite number of facilities, anywhere in the plane, so as to minimize the sum of distances between each demand node and its assigned facility? Beyond the literature on facility location problems, you may find some useful tools in clustering methods (e.g., the K-means ...


7

Formulating as one big problem requires more memory, some way to recognize that the problem decomposes into disjoint subproblems, and some way to then solve the subproblems independently. At least one commercial solver (SAS) looks for such structure after presolve and suggests using the decomposition algorithm in that case. The decomposition algorithm ...


6

You may find this paper (On the Complexity of Min-Max Optimization Problems and their Approximation interesting. Also, only looking at the $p$-median and $p$-center examples you shared, I can say that the constraints of $p$-center problem (or its space), is equivalent to solving a $p$-median problem where $h_i = 1$. So, $p$-center is solving a series of $p$...


6

This is interesting. Perhaps you could find the linear transformation to the lattice that has the minimum deviation from integrality. This would "standardize" your grid in some sense. That might look something like the following (haven't tried it): Sets: ($M$: locations; $N$: dimension of data) Variables: ($a$: transformation multipliers, $y$: projected ...


5

First off, you notion of "far" is unavoidably subjective, so I don't think you are going to find a totally objective approach. Your solution 1 really looks at whether customers are far from their assigned facilities, not far from other customers. If you are going to go that route, you might consider basing it on distance to the nearest possible facility ($\...


5

Note that $\phi$ is a function of $q$ so $d\phi(q)$ is interpreted as w.r.t. $\phi(q)$, which is the same as $d\phi$. This is just shorthand for $\phi'(q)\,dq$.


5

This sounds like the Covering Salesman Problem, introduced in 1989.


4

Without loss of generality take $m=2$. Then $$x_i \leq y\implies\sum_{i=1}^m x_i \leq my$$ is proven by direct summation as in the OP. On the other hand $$ \sum_{i=1}^m x_i \leq my\quad\not\!\!\!\!\implies x_i \leq y $$ is proven by carefully choosing a counterexample. I shall take $x_1 = y+\frac{\epsilon}{2}> y , x_2 = y-\epsilon$. The FL constraint is ...


4

The type of location problems you are looking for are planar location problems where the Weber problem and the multi-Weber problems are among the most well known (and simplest). Drezner gives a nice overview of the problem and a solution procedure called "Weizfeld's procedure". For the multi-Weber problem theres a simple and rather famous heuristic ...


4

Cost matrixes are discussed in the book: "Assignment Problems" by Rainer Burkard, Mauro Dell'Amico, Silvano Martello (on pages 73, and 200, etc.). Yes, some parts would be unconnected (most likely) in such a large problem. Seperation and calculation of the cost matrixes is only the start of the problem. Solving using traditional methods, for so ...


4

The Fermat-Weber problem can be formulated as a conic quadratic problem (aka. SOCP). These problems can be solved in polynomial complexity using an interior-point method. See the Mosek modelling cookbook for information about conic optimization. You can use Mosek to solve those problems.


3

Although it seems to be late to answer this question (as you need to submit a project until Friday), the following papers can be helpful in determining a solution approach to the multi-facility decision-making framework: In the paper1, the authors applied mixed integer goal programming in determining the facility location, route and flow of different ...


3

It sounds like you want to pack $N$ rectangles with given dimensions $w_i \times h_i$ in a $W \times H$ rectangle, as discussed here. To allow each rectangle to be rotated 90 degrees (with dimensions $h_i \times w_i$), you can introduce a binary variable $r_i$ to indicate whether to rotate rectangle $i$ or not. Then modify the constraints like this: \begin{...


2

An approach sometimes used in other contexts is to start with an "optimal" assignment. If the number of sales people increases by one or two, solve a separate model (say a MIP model) that selectively reallocates some territories to the new sales people with constraints on how many they get, how much territory their clientele span, and how many clients each ...


2

I agree with @prubin's suggestions. I would also add that there are already facility location models that try to do things similar to what you are describing. For example, "coverage"-based models (set covering location problem, maximal coverage location problem) define a customer as "covered" if it is within some radius of an open facility. It's not quite ...


2

Before I dive into the proposed solutions, let's first define the set $T = \mathbb{N}^{*}_{\leqslant m}$, where $m \in \mathbb{N}^{*}$ is the available periods' number, since you did not define the set $T$. Now, let's analyze your problems. From what I understood, we have two remaining requirements: If a given age group $a \in A$ is serviced in a given ...


1

I think one way to accomplish what you want is to pass your solution as a MIP Start to gurobi. If it's feasible, gurobi will report the objective value of that solution. Here is Gurobi's documentation on MIP Start. From the link: When you run the example, the MIP solver reports that the start produced a feasible initial solution: User MIP start produced ...


1

In the real situation, usually, this is not important how you could define the input matrices either by float numbers or binary numbers. The most important thing is that these matrices most show the applicable factors of the facility such as, material flow, the distance between the departments or whose related cost/time. If you have a binary matrix for input ...


1

If all the cuts you generate have an impact (i.e., you don't generate cuts that are rendered redundant by other cuts), then at least some of the reason that adding a bunch of cuts at once is faster than adding one at a time is that you update the node LP after each cut is added in the first case, and only after all the cuts are added in the second case. So ...


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