Skip to main content
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-...
Michael Trick's 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) ...
François Clautiaux's 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 ...
Claudio Contardo's 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, ...
Ivana Ljubic's 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 ...
dxb's user avatar
  • 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 ...
LarrySnyder610's 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} \...
LarrySnyder610's 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] \; \...
Kuifje's user avatar
  • 13.5k
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-...
Alberto Santini's 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 ...
mtanneau's user avatar
  • 4,173
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 ...
RobPratt's user avatar
  • 32.3k
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 ...
Sune's user avatar
  • 6,552
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 ...
RobPratt's user avatar
  • 32.3k
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 ...
EhsanK's user avatar
  • 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 ...
E. Tucker's user avatar
  • 1,317
6 votes

Move circles from initial positions such that they do not overlap and total shift is minimized

Assuming you want to avoid overlapping interiors (for example, concentric circles would not be allowed), you can solve the problem via (nonconvex) nonlinear programming as follows. Let $(\bar{x}_i,\...
RobPratt's user avatar
  • 32.3k
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 ...
prubin's user avatar
  • 39.3k
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$.
TheSimpliFire's user avatar
  • 5,412
5 votes
Accepted

A discrete location problem

This sounds like the Covering Salesman Problem, introduced in 1989.
RobPratt's user avatar
  • 32.3k
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 ...
A.Omidi's user avatar
  • 8,950
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 ...
Sune's user avatar
  • 6,552
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 ...
Sune's user avatar
  • 6,552
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 ...
prubin's user avatar
  • 39.3k
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\!\!\!\!\...
Konstantin's 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 ...
Rob's user avatar
  • 2,110
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 ...
ErlingMOSEK's user avatar
  • 3,166
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 ...
worldsmithhelper's 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) ...
Kuifje's user avatar
  • 13.5k
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 ...
Oguz Toragay's user avatar
  • 8,652
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. ...
Pramesh Kumar's user avatar

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