Hot answers tagged

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

How can I express this max-min in CPLEX?

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} & \...
6 votes

How can I express this max-min in CPLEX?

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

How to model a max-min-max problem?

Introduce binary variables $\lambda_{i,j}$ together with the constraints $$\sum_j \lambda_{i,j} = 1 \quad \forall i. \quad(1)$$ Next, add continuous variables $w_i$ defined by the constraints $$w_i =\...
  • 31.9k
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,756
5 votes
Accepted

Defining and comparing utilization rates for delivery service

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 ...
  • 31.9k
5 votes

How to change a function from Min(F(x)) to -Max(-F(x))?

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 ...
4 votes
Accepted

Continuous minimax with linear objective and constraints

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 ...
  • 2,120
4 votes

The difference between max-min and min-max

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 ...
  • 2,050
3 votes
Accepted

Minimize binary variable's distance with respect to the index values

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} &...
  • 23.1k
3 votes
Accepted

How to determine least time required to complete all tasks?

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 ...
  • 1,866
2 votes
Accepted

Convex-Constrained Nonconvex-Nonconcave Minimax Problem

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

how to implement a constraint with max/min function in pyomo

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

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