2
$\begingroup$

Any solvers which can be integrated in python where we can quickly solve if we have integer and binary variables alone in our model other than normal solvers for MIP, MILP?

$\endgroup$
6
  • $\begingroup$ Can you elaborate on why you don't want to use a MIP or MILP solver? Those solvers usually perform quite well on general pure integer problems. Are they too heavy-weight for your application? Knowing why you don't want to use them may help in suggesting alternatives. $\endgroup$ Aug 6 at 7:45
  • $\begingroup$ It takes too much solver time to solve for MILP where I have complex constraints and large non-zero elements . I thought if the solvers restricts its algorithm or heuristics to branch and bound only for integers, it might perform better. Correct me if I'm wrong. $\endgroup$
    – Deepan
    Aug 6 at 7:57
  • $\begingroup$ Unless you find a solver that is dedicated to your problem type, I would guess that your best option is to go with an existing (potentially commercial) MIP or MILP solver. Maybe it makes sense to discuss your problem or problem formulation rather than looking for a somewhat generic solver alternative. $\endgroup$ Aug 6 at 8:13
  • $\begingroup$ One instance is in the following link where i posted my code, if you can, please check it: or.stackexchange.com/questions/6699/… $\endgroup$
    – Deepan
    Aug 6 at 8:45
  • $\begingroup$ And I agree that it will differ with problem specific and model, the way you formulate it. Lets say if we know that all my variables in my model will be integer or binary and at optimality, all constraints non zero elements, objective value, everything will be integer or binary alone, but MIP/MILP solvers will check for larger solution space even if I can declare my variables are integers or binary, but In a feasible solution, my non zero elements and objective function may take fractional value based on my complexity of the constraints which wont be optimal. $\endgroup$
    – Deepan
    Aug 6 at 8:53
4
$\begingroup$

For binary only there are the following classes of solvers:

  • SAT Solvers and MaxSat for optimization
  • Pseudo Boolean Programming or Pseudo Boolean optimization

For integer valued there are the following approaches:

  • Constraint Programming
  • Rephrasing as Boolean Problem provided the search space is finite
  • SMT solvers and Optimization modulo theory

As well as local solvers which might be able to solve both.

As for whether such software is callable from Python:

  • SAT solvers: yes, for example Lingeling
  • Pseudo Boolean solvers: no, as far as i know, but you can generate a problem file a solver like RoundingSAT could work on and read it's output files.
  • Contraint programming: yes, see Python constraint
  • SMT solvers, yes see Z3Py
  • Local solvers, yes see LocalSolver

All those solvers use different proof systems from MILP solvers, so it is possible that they solve certain formulations of certain problems better than MILP solvers. However there is no single approach that dominates MILP on every task.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.