Solving a max min Problem in Gurobi

[andreas L]

Hello everyone,
I have the following setting.

I have a minimization problem
z(b)=min c^t
Ax <= b
x>=0

and I want to solve the maximizationproblem
max z(b)
Db<=d
z(b)= the minimization problem from above

Does anyone have an idea how to write this problem in gurobi with python? I do not want to have a full solution, but tipps, where to find it, or some examples would be helpfully.
Nice regards,
Andreas

[Tobias Achterberg]

Just to make sure I understand your problem: you have decision variables x and b, data A,
D, and d, and you want to find a vector b such that Db <= d and the objective value of the
linear program

(LP) z(b) = min {c*x : Ax <= b, x >= 0}

is maximized. Is this correct? Thus, the b variables are the first-level decisions, and
then the values of the x variables follow from b by means of a simple LP solve. You want
to select a right hand side vector d within the polyhedron Db <= d that is the "worst
possible" for the second level (LP) problem.

In general, such problems are called "bilevel optimization problems". They are pretty hard
to solve, and there are a bunch of papers dealing with this. I think that there is also
software around.

There are certainly some special cases that are easy to solve (reduce to a single level
optimization problem), but I don't know right now whether your problem falls into this
lucky area. This polyhedral restriction of the coefficients of (LP) reminds me of robust
optimization where you want to find a solution x that is good for all possible
instantiations of the data (b in this case), provided that the data is within some
reasonable set. Typical sets are boxes, circles, elipsoids, or polyhedra.


Regards,

Tobias

[andreas L]

Your assumptions about my given problem are very good.
I have the big problem

min{ c*x : Ax <= b for every b in U} <- fat modell |U| -> 1000 scenarios
I do not want to do the standart robust method by assuming the worst scenario. Assuming the worst scenario is in my application to expensiv.
So I want to solve the fat modell by a cutting plane method. The idea of this method comes from the L shaped Method. The scenarios are actual in elipsoids or boxes. The worst case scenario means in my application, that I buy energy and I do not use wind energy. So my understanding of robustness is the possibility to send the windpower in every scenario by gurarantee, that I have bought enough energy to mind the worst case and not that the network holds for the worst case. Worst case in my application means, that the scenario comes from the surface of my ellipsoid.
The subproblem consists of a min cost flow problem with additional variables to guarantee the validity of the constraints. The aim is the minimization of the additional variables ( all of them have positiv objectiv coeffizients) . But the greater aim is to find the scenario with the highest value of the minimizations.  I hope, this explanation is better.
Nice regards,
Andreas

[Sagnik BasuMallik]

Hi Andreas, did you find a way out to solve the bilevel problems using Gurobi?