2
$\begingroup$

I am currently doing a coursera course on optimization. They are using minizinc and they modeled a problem where the decision is a choice of things --> a set. We all know this is a knapsack and it its modeled with binary vars.

They declared a set var. What is this? is this common? Or does the solver somehow convert this into a knapsack?

enter image description here

enter image description here

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

This is a constraint programming (CP) model. The "vocabulary" of MIP solvers is fairly standard. They all recognize real, integer and binary variables, linear equality and inequality constraints, maybe some quadratic stuff and maybe indicator constraints. CP languages and solvers are much less standardized. Apparently MiniZinc has a construct for variables whose values are subsets of a given set of integers. Older versions of IBM's CP Optimizer seemed to have something similar ("IloIntSetVar"), but I think it has been removed.

As to how the solver implements it, that might vary from solver to solver. It could be converted internally into binary variables for each vocabulary element (1 if the element is selected for the set).

Improve this answer
$\endgroup$
2
  • $\begingroup$ I never heard of this in my university and I had plenty of courses about OR/Optimization. Why is that? $\endgroup$
    – Eddiee
    Jan 20, 2022 at 12:16
  • 1
    $\begingroup$ Good question. Constraint programming is an outgrowth of "SAT solvers", which are logic solvers developed in the computer science community to decide whether complicated logic conditions can be satisfied (I think). The move from computer science to OR/optimization is relatively recent. Instructors tend to teach what they were taught, and textbook authors tend to write about what they were taught, so it will take a while for CP to become a "mainstream" OR topic. The same is true for "decision diagrams", another development in computer science recently making its way into OR. $\endgroup$
    – prubin ♦
    Jan 20, 2022 at 17:00

Your Answer

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

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