0
$\begingroup$

I'm looking for an approach to solve a problem consisting of maximizing an objective function over a set of discrete elements, while respecting a set of constraints.

To illustrate my point, I'll try to come up with an example.

A bag contains several items with the following attributes:

  • Value (Int)
  • Size (Int)
  • Material (Enum)
  • Origin (Enum)

As an example, we can imagine a bag consisting of the following items:

value     size     material    origin
    4        1         wood        FR
    4        2        stone        US
    3        3         gold        JP
    2        2         wood        FR
  ...      ...          ...       ...

The goal is to maximize the total Value, while at the same time respecting a set of constraints. An example set of constraints would be:

total size < 80
between 20 and 35 items in total
at least five elements with origin FR
at least two elements with material wood OR at least two elements with material stone
strictly less elements with material gold than elements of material stone
no more than 5 elements with size > 10

Below are some approaches I've thought about, and the reason why I can't use them directly:

  • (Integer) Linear Programming: here we're not dealing with the full space of Integers, but instead only with the values found in the bag (and tied to the other properties for each item)
  • Stochastic Constraint Satisfaction: it would be easy to stochastically come up with a selection of Items which respects the constraints, but here we're not looking for any solution, instead we're looking for the solution which yields the highest total Value, which would need us to exhaustively list all possible satisfying solutions before picking the one with highest value (which may be a very inefficient approach)
  • SMT solver: I think it could be the way to go, but so far I can't see how to model the link between the constraints, the objective function and the bag of elements

Can you think of an approach to solve this kind of problems?

$\endgroup$
  • $\begingroup$ Since you considered linear programming, why did integer linear programming not make the list? $\endgroup$ – harold Nov 25 '17 at 20:32
  • $\begingroup$ @harold I was implying integer linear programming — sorry for the confusion in my formulation — see edit $\endgroup$ – Jivan Nov 25 '17 at 20:44
  • 1
    $\begingroup$ I don't understand why you rejected integer linear programming. Perhaps spend a bit more time learning about ILP and how it can be used to model such problems. I suggest you spend some quality time with integer-programming, and a good tutorial or textbook on ILP. $\endgroup$ – D.W. Nov 26 '17 at 0:02
1
$\begingroup$

I don't see any problem with modeling this as an integer linear program, for example:

maximize V.x
st:
1) s.x < 80
2) 20 <= e.x <= 35
3) FR.x >= 5
4a) Wood.x + 2 - 2W >= 2
4b) Stone.x + 2W >= 2
5) Gold.x - Stone.x < 0
6) Size10p.x <= 5
x[i] ∈ {0, 1}
W ∈ {0, 1}

Where . is the dot product, x is a binary vector indicating which items to take, e is the vector of all-ones, FR is a boolean vector where an element is 1 iff the corresponding item is from France, Wood is a boolean vector that indicates that the material wood, etc. Size10p indicates that the item has a size higher than 10.

I've made all the left-hand sides of dot products the constant vector, so you can easily see that there are no sneaky quadratic constraints.

Most of the constraints are obvious, but constraint 4 is a bit trickier. It involves a disjunction, and uses an extra binary variable to choose which "side" of the disjunction to take. The other half is then trivially satisfied, by either adding 2 and not also subtracting 2 (W = 0, not taking the wood-side of the disjunction) or by just adding 2 (W = 1, taking the wood-side).

here we're not dealing with the full space of Integers, but instead only with the values found in the bag

This is usually not a problem, since you can binarize constraints of the form v ∈ some enum to v1 = [v == item1], v2 = [v == item2] etc combined with v1 + v2 + ... = 1. But I did not even need that here, the decision is just "do I take this item or not", and things such as "item has property 'Gold'" are just constant booleans.

More tricks are available in other answers, for example Express boolean logic operations in zero-one integer linear programming (ILP).

$\endgroup$
  • $\begingroup$ That's very interesting. To be honest I wasn't aware that you could do all this with integer linear programming. I'll have to work a bit on the elements you expose, but it feels like you're pretty confident in the outcome and in the method. So I'll just accept your answer as it is now. $\endgroup$ – Jivan Nov 25 '17 at 21:45

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.