Maximizing the average value as an MIP problem

 3 1 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 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 but I am wondering if there is any easier way of solving it (perhaps Gurobi can solve it directly with some tricks?) Thanks asked 25 Nov '13, 17:52 Igor Pangal 147●2●10 accept rate: 0% fbahr ♦ 4.6k●7●16 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

One Answer:
 6 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 Buchanan 1.3k●3●13 accept rate: 42% This is right, my previous answer was wrong. (25 Nov '13, 20:50) Iain Dunning
Your answer
 toggle preview community wiki

Follow this question

By Email:

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

By RSS:

Answers

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

Tags:

×231
×71
×22

Asked: 25 Nov '13, 17:52

Seen: 1,430 times

Last updated: 11 Dec '13, 08:09

Related questions

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