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

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


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


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


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


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