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

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.


answered 23 Sep '15, 19:47

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

I suggest you using column generation approach.


answered 25 Sep '15, 19:10

Duc%20Minh%20Vu's gravatar image

Duc Minh Vu
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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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: 22 Sep '15, 17:52

Seen: 864 times

Last updated: 25 Sep '15, 19:10

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