CODEWITHSUNDEEP
mathematical-optimizationlinear-programmingcplexgurobi
user1030312
user1030312

Reputation:

How to convert a max in the objective function, when we maximizes?

How to rewrite the program

maximize max(2x, 3y)
s.t 0 <= x, y <= 1

So that an LP/MILP can solve it?

My actual objective function is enter image description here

I'm new to LP, and I don't understand well how to use 'binary constraints'.

I'm learning with PuLP and GLPK.
In my production code, I will either use CPLEX or Gurobi.
Those these two support 'maximization of max' out of the box?

Upvotes: 1

Views: 4351

Answers (2)

thor
thor

Reputation: 22530

If the objective was a minimization, you can use an auxiliary variable as follows:

minimize z
s.t. z >= 2x, z >= 3y, 0 <= x, y <= 1

If it's a maximization, below should work, where

M is a sufficiently large number;

u_{1,2}_{1,2} are a set of auxiliary variables that represent a "permutation" that sorts 2x and 3y.

maximize (z_1_2 + z_2_2)
s.t. 
z_1 = 2x
z_2 = 3y

z_1 = z_1_1 + z_1_2
z_2 = z_2_1 + z_2_2

u_1_1 + u_1_2=1
u_2_1 + u_2_2=1
u_1_1 + u_2_1=1
u_1_2 + u_2_2=1

z_1_1 <= M*u_1_1
z_1_2 <= M*u_1_2
z_2_1 <= M*u_2_1
z_2_2 <= M*u_2_2

z_1_1 + z_2_1 <= z_2_1 + z_2_2


0 <= x, y <= 1
u_{1,2}_{1,2} in {0,1}   //u_i_k are binary variables.

min and max of a bunch of numbers, unlike sum, is not a linear form, and I don't think CPLEX or MILP generally has a special form for this. In this particular example, a smaller number of binary auxiliary variables might be enough (instead of u_{1,2}_{1,2}), but in general, a permutation variable like this gives you the order of a sequence of numbers and allows you to pick any of them by rank (in your case the largest item).

Upvotes: 1

tmyklebu
tmyklebu

Reputation: 14215

"Maximising the max" is inherently nonconvex. You will need to use a MIP trick here. And you must be able to get lower and upper bounds on the objects you're taking the max of in order to do so. Any finite bound will do, but sharper bounds will give a tighter relaxation that will probably solve faster and be nicer numerically.

Suppose you've got the following problem, which is marginally more general than the one you gave:

maximize max(3x, 2y)
s.t.  0 <= x <= A, 0 <= y <= B.

Notice that 3x is trivially bounded below by 0 and above by 3A. Similarly, 2y is bounded below by 0 and above by 2B. Now you introduce two binary variables, c_1 and c_2, and you ask that exactly one of them be 1. c_1 corresponds to the choice of 3x from the max and c_2 corresponds to the choice of 2y from the max. Then you write

maximize z_1 + z_2
s.t.  z_1 <= 3A c_1
      z_1 <= 3x
      z_2 <= 2B c_2
      z_2 <= 2y
      c_1 + c_2 = 1
      0 <= x <= A, 0 <= y <= B
      c_1, c_2 binary

The first constraint "turns off" z_1 so that it has zero contribution if the max is attaned by 2y. The second constraint limits z_1 by 3x in the case where the max is attained by 3x.

Upvotes: 2

Related Questions