I am wondering if it is possible to optimize for higher average values with an MIP solver like Gurobi

Specifically I have the following problem that I am interested in solving

alt text

subject to some linear constraints.

One way of solving it would be to solving it in different steps by assuming a threshold for which we want the objective to be higher than that. i.e

alt text

but I am wondering if there is any easier way of solving it (perhaps Gurobi can solve it directly with some tricks?)


asked 25 Nov '13, 17:52

Igor%20Pangal's gravatar image

Igor Pangal
accept rate: 0%

edited 11 Dec '13, 08:09

fbahr's gravatar image

fbahr ♦

Are there integer variables present? If so, are they binary?

(25 Nov '13, 19:16) Austin Buchanan

yes x_i is a binary variable and w_i is just a constant number for each x_i

(25 Nov '13, 20:03) Igor Pangal

You can linearize the fractional 0-1 program, thereby turning it into a standard MIP. For example, use the approach proposed by Wu:

Introduce new variables \( y=\frac{1}{\sum_{i} x_i}\) and \( z_i = y x_i\). Make this your formulation (after including binary restrictions on x variables and add all your other constraints).

maximize \( \sum_{i} w_i z_i \)

\(z_i \le U x_i \)

\(z_i \ge L x_i \)

\(z_i \le y - L (1-x_i) \)

\(z_i \ge y - U (1-x_i) \)

\( \sum_{i} z_i =1\)

\( L \le y \le U\)

\( z_i \ge 0\)

where \( L=\frac{1}{n}\),\(U =1\), and n is the number of 0-1 variables.

The new, weird-looking constraints are introduced to linearize the quadratic terms \( y x_i\).


answered 25 Nov '13, 20:42

Austin%20Buchanan's gravatar image

Austin Buchanan
accept rate: 42%

edited 25 Nov '13, 20:49

This is right, my previous answer was wrong.

(25 Nov '13, 20:50) Iain Dunning
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 25 Nov '13, 17:52

Seen: 1,599 times

Last updated: 11 Dec '13, 08:09

OR-Exchange! Your site for questions, answers, and announcements about operations research.