Interested in Constraints Programming & Optimization, have some basic questions

I apologize in advance for how likely stupid this is going to come off, but I have a few questions and was hoping someone might be kind enough to offer some insight.

I became interested in Logic/Constraints programming some months ago, and have since spent time looking at tooling in the area. I don’t have any education or math background, so I found that a majority of the libraries were unapproachable because of how math-driven the API’s were.

JuMP is different, the DSL for expressing constraints and objectives feels much more logic-oriented than math-oriented.

I don’t have any background in Julia, so I tried to start with a simple problem:

"Given a list of food items, and a desired calorie + protein goal, return all possible combinations of food items you could eat to meet that goal"

I went through a number of the JuMP examples to get a feel for it, but then realized I wasn’t sure how to model the problem.

The questions I have are:

  • Why are variables represented as single-input arrays in JuMP models? For example, a Food struct has calories, protein, carbs, fat, but in the examples, each of these values seem like they get pulled apart into individual arrays .

From the cannery example:

function example_cannery(; verbose = true)
    plants = ["Seattle", "San-Diego"]
    markets = ["New-York", "Chicago", "Topeka"]

    # Capacity and demand in cases.
    capacity = [350, 600]
    demand = [300, 300, 300]

    # Distance in thousand miles.
    distance = [2.5 1.7 1.8; 2.5 1.8 1.4]

Instead of the format that makes more sense, which is something like:

food = [
  Food(name = "Pizza", cals = 300, protein = 12),
  Food(name = "Chicken", cals = 100, protein = 40),
]

This way you can do food.name, food.calories, etc, instead of food_names[i], food_cals[i] which is harder to follow.

  • What if you don’t have an @objective, and you just want any values that meet your constraints? Would you just create an artificial/fake objective and example the constraint values after the solve?

  • How do solvers differ from combinatorial approaches, like the one below? I assume they have some advanced logic in them that makes them more effect at searching for values, and this approach breaks down at larger data sizes?

This was how I was able to do it naively:

Is this better representable/more scalable with constraints? If so, what might the right approach look like?

If you just want a list of the feasible combinations, rather the finding a single best combination, then I don’t think JuMP will be helpful.

On the other hand, it looks like you already solved the problem with DataFrames and Query. Why would you call that way naive? Maybe it could be improved by not storing all combinations, but generating & filtering them lazily?

Because it’s brute-force by generating (I think it’s called a “power set?”, I don’t know any maths) all the combinations and just iterating through them and applying predicates.

I assumed that Constraints + Optimizers had better time-complexity or efficiency than this, it sort of feels like solving a sudoku by manually checking every combination.

My goal was to work up to a variation of a scheduling + optimization problem for a real-world example I have, for implementation in business. And also just because I find the concept of solving problems declaratively via constraints interesting. This just seemed like an easier place to start, but I still wasn’t able to quite figure out how to model it.

I can recommend this course for a foundation on Constraint Programming and Mathematical Programming, https://www.coursera.org/learn/discrete-optimization/

If your personal interest is Constraint Programming, this is a nice blog about building one in Julia, https://opensourc.es/blog/constraint-solver-1

I actually sent an email to the opensourc.es guy thanking him for his articles the other day, found his blog while doing research and it’s incredible!

I will have a look at the Coursera course, thank you.

I’m new to Julia, but if I were setting up such a problem, I would consider storing parameters and variables in dictionaries, rather than arrays, to make it easier to follow.
The problem you are describing is enumerating all feasible solutions to…you could call it an integer diet problem.
The following may solve your problem, if you are willing to set up SCIP, which does constraint programming:
https://scip.zib.de/doc-3.2.1/html/COUNTER.php#COLLECTALLFEASEBLES
Typically in Math Programming/Optimization people use a fake objective like you suggest if they are solving a “feasibility problem”, i.e. just looking for one feasible solution. If you wanted to get a bunch of different solutions along a Pareto frontier, you could vary the objective systematically and solve many times. But there is not going to be an easy way to get all feasible solutions with any kind of Integer Programming (“IP”) approach (e.g. branch and bound). The whole point of IP algorithms is to avoid the explicit enumeration of the exponentially large set of feasible solutions, by efficiently pruning suboptimal solutions.
If you relaxed the integrality constraints (allow fractional hamburgers), the closest thing you would do would be “vertex enumeration” over the feasible polytope of the standard diet problem. I don’t think people use math programming solvers for this either.

1 Like