I am actually constructing engineer application based on pseudo-boolean optimization. I want to ask what is the current status (how many variables, interaction parameters) the solver generally solve up to date and what is the best software for it. Thank you.

asked 21 Oct '14, 19:55

Chivalry's gravatar image

accept rate: 0%

When you say pseudo-boolean optimization, do you mean your objective function looks like this? My first approach would be to linearize and use a commercial MIP solver (disclaimer: I have no experience solving pseudo-boolean optimization problems).

You might look at this survey from 2002. Also look at which papers cite it for more recent findings and computational results.

As far as what size problems can be solved, my guess is that YMMV depending on what instances you're looking at. I bet I can find 500-variable instances that cannot be solved by current techniques, but these instances are artificial and probably not what you'd encounter in practice.


answered 21 Oct '14, 23:16

Austin%20Buchanan's gravatar image

Austin Buchanan
accept rate: 42%

edited 21 Oct '14, 23:19

I did the same thing using MIP.... maybe due to lack of knowledge, instances with 30~40 variables is already rather slow....

(21 Oct '14, 23:35) Chivalry

hmmm, that's pretty bad--worse than I expected. How big are the multlinear terms? And how many variables (binary vs. continuous) do you have in the linearization?

(21 Oct '14, 23:51) Austin Buchanan
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: 21 Oct '14, 19:55

Seen: 788 times

Last updated: 21 Oct '14, 23:56

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