19
votes
Why are integer minimax problems hard?
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-...
- 2,362
19
votes
Accepted
Why are integer minimax problems hard?
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) ...
11
votes
Why are integer minimax problems hard?
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 ...
- 1,549
11
votes
Linear facility location problem for large size problems (police station)
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, ...
- 111
11
votes
Accepted
Symmetric undirected $p$-median instance with fractional LP solution?
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 ...
- 1,799
9
votes
Linear facility location problem for large size problems (police station)
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 ...
- 13.1k
9
votes
Algorithmic gap for Hochbaum's (greedy) algorithm for (metric) uncapacitated facility location
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} \...
- 13.1k
9
votes
Accepted
How to enforce a relation between two variables
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] \; \...
- 12.9k
8
votes
How to quantify the "griddiness" of a set of points?
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-...
- 2,073
7
votes
Facility Location Problem over Continuous Space
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 ...
- 4,068
7
votes
partitioning hub assignment models
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 ...
- 30.5k
7
votes
The significance of infeasibility for a Capacitated Facility Location Problem
Given that your problem has binary assignment variables (the &$x_{ij}$ variables) it is not a capacitated facility location problem (CFLP) , it is a single source CFLP (SSCFLP). The decision ...
- 6,352
7
votes
Accepted
Writing a constraint of an integer programming in a linear form
Introduce a binary decision variable $y_j$ to represent the product $t_j x_j$. The usual linearization would use three linear constraints to enforce this relationship. But here, because $T\ge 0$, we ...
- 30.5k
6
votes
Why are integer minimax problems hard?
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 ...
- 5,864
6
votes
How to quantify the "griddiness" of a set of points?
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 ...
- 1,317
5
votes
Accepted
Adding robustness to the objective function of the facility location problem
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 ...
- 37.9k
5
votes
Accepted
Mobile Sensor Placement for Optimal Coverage
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,342
5
votes
Accepted
A discrete location problem
This sounds like the Covering Salesman Problem, introduced in 1989.
- 30.5k
5
votes
Accepted
The significance of infeasibility for a Capacitated Facility Location Problem
I think what you have faced with infeasibility came from the problem data. I tried to run the problem with the formulation you mentioned by some of the random data and the problem is being solved ...
- 8,450
5
votes
Modelling a Capacitated Facility Location Problem in such a way that a few candidate locations are always selected
I assume that you have some sort of "solver" for solving a capacitated facility location problem, which you want to utilize.
If you need a specific facility, say facility $\tilde{i}$, to be ...
- 6,352
4
votes
Accepted
Facility Location Problem over Continuous Space
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 ...
- 6,352
4
votes
Accepted
Prioritizing a special group in Facility Location problem
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 ...
- 37.9k
4
votes
Accepted
Strict inclusion for facility location formula and aggregate facility location formula
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\!\!\!\!\...
- 306
4
votes
Accepted
partitioning hub assignment models
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 ...
- 2,098
4
votes
What is the state of the art on the Weber problem?
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 ...
- 3,046
4
votes
What is dynamic facility location problem ans how to formulate the same? Please help
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 ...
- 3,975
4
votes
Designing a multi-commodity network flow optimizer
Question 1
You could simply use the priority function as the cost function on the arcs. This way, it is for example cheaper to ship a commodity to $D_1$ from $W_2$ ($1$ unit of cost per unit of flow) ...
- 12.9k
3
votes
Using Spatial Multi Criteria Analysis for simultaneously locating various facilities?
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 ...
- 8,622
3
votes
A tricky Bi-Level Location Problem using VISUM
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.
...
- 411
3
votes
Accepted
How to interpret no-overlap constraints with rotation as a mixed integer programming
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 ...
- 30.5k
Only top scored, non community-wiki answers of a minimum length are eligible