-4
$\begingroup$

I have an LP problem (linear objective with eq and ineq constraints) in binary variables.

Except for the objective, all the coefficients are integer, mostly in {-1,0,1}. Maybe the objective coeff could be discretized.

I usually use an MI solver (gurobi). Since it solves a moderate problem in my case under a second, I suspect that it may have a special structure that permits employing a different specialized method that will be faster. Can you suggest other methods to solve my problem?

More details in a duplicate question:

https://math.stackexchange.com/questions/4504572/methods-for-binary-linear-programming/4505035

@worldsmithhelper suggests (in the comments) to test a problem on all solvers using

https://neos-server.org/neos/solvers/index.html

I'm considering automating it. I'm using yalmip, which can export the following formats:

https://yalmip.github.io/tags/#export-and-import

This can be wrapped in an XML and sent via a python client (in a loop for each solver):

https://neos-guide.org/users-guide/neos-interfaces/#xml

Improve this question
$\endgroup$
11
  • 4
    $\begingroup$ Link only questions don't self-document and can't be easily refined. Please post an actual question. $\endgroup$ Commented Aug 4, 2022 at 1:12
  • $\begingroup$ I must say that as a new user who first post a question on this board, down-voting my question along with an incoherent explanation isn't too friendly. $\endgroup$ Commented Aug 4, 2022 at 8:18
  • $\begingroup$ @Zoher: I can certainly see that. Try to keep in mind that this isn't commentary on you, it's commentary on the question _as currently stated _. StackExchange has great answers because we work hard to have great questions. $\endgroup$ Commented Aug 4, 2022 at 15:45
  • 1
    $\begingroup$ @Zoher: To make a better question for OR you need to include the text of the question on this site. A link to your question is not enough. It also helps (I peeked at the link) if your question contains question marks to make it really clear what you're asking. $\endgroup$ Commented Aug 4, 2022 at 15:48
  • 1
    $\begingroup$ You are saying that I'm not stupid, it's just my questions; thanks, I feel better now :) I edited my question to include a question mark. $\endgroup$ Commented Aug 4, 2022 at 20:38

1 Answer 1

Reset to default
1
$\begingroup$

Your problem can be classified as a 0-1 integer linear program. Problems in this class are NP-hard in general, even when the coefficients are all integers and there is no objective function.

There are specific subclasses that are easier to solve. For example, integral linear programs can be solved in continuous variables and will still produce a 0-1 solution. The most common way of proving that a polytope is integral is through total unimodularity.

Without further information, using a mixed-integer programming solver seems like your best bet. It is not surprising that small instances are solvable while larger ones are not: in general you would expect the solution time of NP-hard problems to increase exponentially. Your polytope is probably not integral: if it was the solver would detect that after solving the root relaxation in node 0 and terminate quickly.

If you share more information about the problem structure, we may be able to provide more help.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It was more of a general, theoretical question. I'm not sure about my problem structure (although I can share a specific instance of it in a .mps), and I'd like to through everything at it. More details of what I referred to are in the link to the math forum. $\endgroup$ Commented Aug 12, 2022 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.