Hot answers tagged

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


9

You can model this as a maxmin problem by introducing an auxiliary variable $\theta$: \begin{align} \max&\quad\theta &\\ \text{s.t.}&\quad\theta \leq \sum_{c=1}^C x_{uc}d_{uc} & \forall u=1,\dots,U \end{align} For future reference, if in contrast you had a minmax objective instead of a maxmin objective, you could apply the same trick: \begin{...


6

Maximize an auxiliary variable $z$ subject to the constraints $z\le \sum_{c=1}^C d_{u,c}x_{u,c}\ \forall u$.


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


5

One possibility is to look at idle time (time a driver spends waiting for the next order). If the drivers are on your payroll (as opposed to working on commission, i.e., doing "gig" work), idle time has a direct cost. If the drivers are gig workers, a relatively even distribution of idle time might be perceived as "fairer" and might contribute to driver ...


5

In order to maximize X+Y, you can minimize -(X+Y), and then negate the optimal objective value. The optimal X and Y will also be optimal for maximize X+Y. Similarly, to maximize Sum (LC + MD), you can minimize -Sum (LC + MD), and then negate the optimal objective value.


4

The problem is infeasible: $(c_1,c_2) \Rightarrow x_1=1$ $(c_3,c_4) \Rightarrow x_2+x_3=2$ $(c_1,c_2,c_7) \Rightarrow x_4 + x_5 \le 2$ $(c_5,c_6) \Rightarrow -(x_2+x_3)+0.4(x_4+x_5) \ge 2 \text{ and so } (c_3,c_4,c_5,c_6)\Rightarrow x_4 + x_5 \ge 10$ The last two lines are not consistent. Note that we also obtain a conflict with $(c_8,c_9)$: $(c_8,c_9) \...


4

While these equations have many interpretations in OR (e.g. robust optimization), in this case I like to understand what happens here using a Game Theory perspective. These two equations can be interpreted as a Stackelberg game, sometimes referred two as leader follower games. Consider a two player zero sum game, where player 1 has to pick an element from $X$...


3

Introduce a variable $y_{i,j}$ to represent $$\left|\sum_k k x_{i,j,k}-\sum_k k x_{i,j-1,k}\right|,$$ together with constraints \begin{align} y_{i,j} &\ge \sum_k k x_{i,j,k}-\sum_k k x_{i,j-1,k} &&\text{for all $i$ and $j$} \\ y_{i,j} &\ge -\sum_k k x_{i,j,k}+\sum_k k x_{i,j-1,k} &&\text{for all $i$ and $j$} \end{align} The objective ...


3

Minimizing the sum of all assignments: this is the classical version of the assignment problem. The Hungarian algorithm solves it in polynomial time. Minimizing the maximum of all assignments: this one is known as the linear bottleneck assignment problem. The most obvious way to solve it is to solve a succession a decision problems: is it possible to find ...


2

I got bad news for you: The problem is as long as you care about the inner max being the actual max and not just some local maxima (which might make sense with multiple roll outs for a game theory simulation) you are stuck with calling an global optimizer to just evaluate $x \mapsto \max_{y_\in Y} f(x,y)$ correctly. If $\dim(y)$ is small you might want to ...


1

Maybe you can replace your equality constraint with two inequality $\leq$ and $\ge$ constraints. Also, have a look at this link


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