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-...
user avatar
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) ...
user avatar
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 ...
user avatar
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, ...
user avatar
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 ...
user avatar
  • 1,759
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 ...
user avatar
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} \...
user avatar
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] \; \...
user avatar
  • 10.2k
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-...
user avatar
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 ...
user avatar
  • 3,283
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 ...
user avatar
  • 22.2k
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 ...
user avatar
  • 5,377
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 ...
user avatar
  • 5,661
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 ...
user avatar
  • 1,307
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 ...
user avatar
  • 29.7k
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$.
user avatar
  • 5,185
5 votes
Accepted

A discrete location problem

This sounds like the Covering Salesman Problem, introduced in 1989.
user avatar
  • 22.2k
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 ...
user avatar
  • 5,833
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 ...
user avatar
  • 5,377
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 ...
user avatar
  • 29.7k
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\!\!\!\!\...
user avatar
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 ...
user avatar
  • 2,052
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 ...
user avatar
  • 2,451
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 ...
user avatar
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) ...
user avatar
  • 10.2k
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 ...
user avatar
  • 8,290
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. ...
user avatar
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 ...
user avatar
  • 22.2k
3 votes
Accepted

Capacitated Facility Location problem with a dynamic set up cost

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 ...
user avatar
  • 29.7k
2 votes

How to design and scale sales territory?

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 ...
user avatar
  • 29.7k

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