Is there a solver that is capable of solving a linear program, that has a quadratic objective function....where this program is made up of 800,000,000 binary variables and less than 50 constraints. My guess is that about 10,000 of the binary variable will be non-zero in the optimal solution.

asked 22 Sep '15, 17:52

Redshorts's gravatar image

Redshorts
112
accept rate: 0%

edited 22 Sep '15, 17:53


The value of each binary variable in a typical solver is a 64-bit double precision number. I estimate that 8e8 variables will take up about 6 GB of RAM just to hold their values -- without any constraints, without the objective function, without any other structures the solver might create. Zeros still consume the full eight bytes per variable.

That's the root node. If the problem doesn't solve at the root, start adding nodes to the tree. I'm not sure how much data is stored at each node, but my guess is that it's enough to make this a non-starter.

link

answered 23 Sep '15, 19:47

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

I suggest you using column generation approach.

link

answered 25 Sep '15, 19:10

Duc%20Minh%20Vu's gravatar image

Duc Minh Vu
21115
accept rate: 0%

Your answer
toggle preview

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
×36
×14

Asked: 22 Sep '15, 17:52

Seen: 637 times

Last updated: 25 Sep '15, 19:10

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