# Tag Info

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 ... 9 You can activate variable Y[j,t] when O[j,t] is active (O[j,t] \; \Longrightarrow \; Y[j,t]) with:$$ O[j,t] \le Y[j,t] \tag{1} $$And then make sure Y[j,t] remains active (Y[j,t] \; \Longrightarrow \; Y[j,t+1]):$$ Y[j,t] \le Y[j,t+1] \tag{2a} I suppose there is some cost on variables Y[j,t] ? If so, this cost should preclude the solver from ... 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 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 Without loss of generality take m=2. Thenx_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

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.

4

I am not a search engine, if you would search for "dynamic facility location problem" you would for example find this book for free. Chapter 15 covers multiple formulations from the literature and describes them.

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

You can add a constraint that says the number of vulnerable people assigned to a facility is at least a specified fraction of the total number of vulnerable people (where the fraction is set to 1 if you want to ensure all vulnerable people are assigned, or something less than 1 indicating your tolerance for leaving vulnerable people unassigned). If you use a ...

3

Following is a possible way of its implementation: First, you define a function that takes an OD matrix, solves the GUROBI model, and returns the optimal locations. FUNCTION OPTIMAL_LOCATION(OD): // This part will prepare the gurobi model and change the parameters related to OD matrix // Solve the model and return locations END FUNCTION ...

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

To impose the distance restriction, use a sparse index set of $(i,j)$ pairs rather than the full Cartesian product $I \times J$. Also, you might consider omitting constraint $(2)$, which will naturally be satisfied unless the penalty for unmet demand is too small to encourage opening any facilities, and constraint $(5)$, which is logically implied by $(3)$ ...

1

One way to try is to have lower assignment cost (assuming a minimization objective) to vulnerable people compared to non-vulnerable for a given facility.

1

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

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