Dear AI/Neural Network community,

I have a problem from combinatorial optimization and want to try to solve it with a neural network. The problem is roughly as follows:

I have a sorted list of objects with some attributes, think of a schedule of dishes for hospital meals for one week. These items have to be sorted in an optimal way respecting some limitations, like - a certain parameter may not have the same value in two items that follow one another (like "no two rice dishes directly after each other", i.e. the parameter "kind of dish" may not have the value "15" (rice dish) in two subsequent dishes) - there is a number indicating a light priority measure how soon in the list the item should appear (think of an urgency value according to some ingredients that may spoil over a few days) - there are items in the list that have to be in the correct order (item A should be before item B)

None of these requirements is absolute, but in sum (of penalty points) we want to achieve "the" minimum of this function, or at least a good candidate.

At the moment we are building a penalty function of these aspects (more requirements might come at a future time) and building a gradient optimization approach around it. (we define a neighborhood of one ordering of items by: "ordering B is in the neighborhood of ordering A if we get B by exchanging two items in A" and look for the best improvement in this neighborhood.)

Is there a way to perform this optimization with a neural network? If so (which I hope!), I would most likely give as input the relevant variables for each of the items in the list that has to be sorted. But what shape does the output layer take?

How can I train the algorithm if I do not know exact solutions due to the problem size? I have the penalty function as a given, and maybe some locally optimal solutions from above algorithm, if absolutely necessary. Is feedback by the penalty function somehow enough?

How do I handle different problem sizes (like in some weeks Saturdays also have to be served)? Zero Padding in the input layer?

I am not sure how easy or difficult this problem is, but would be very happy if you could give me some pointers (maybe terms I can google that I did not think of in this context). My background: Mathematician with some background in optimization, but almost no knowhow in AI/NN - although very keen to learn more! I have seen and tried to understand a few of the examples for DL4J.


Pointer Networks are an architecture designed to resolve this type of combinatorial problem where the answer is often a permutation of the inputs, and it doesn't make sense to use any fixed size architecture. It has been used to solve combinatorial optimization problems such as TSP.

The key is that rather than using a fixed size output, which is incompatible with the variable number of dishes which may be served, the network should instead "point" back to one of the input dishes to say "this one comes next"

| cite | improve this answer | |
  • $\begingroup$ I have read about LSTMs and sequence to sequence learning, which seems similar to this, but was a bit intimidated by the difficulty. Thank you for the hint to this paper and concept of Pointer Networks, which I will look into more deeply. On a first short reading of the article it sounds quite fitting (especially the TSP part). $\endgroup$ – Michael Hofmann Feb 1 '19 at 20:12

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