Answers.Body: <p>Your question is still nearly perfectly unclear, but let's make a few guesses in order to make some progress.</p>
  
  <p>The biggest mystery are your time slices:</p>
  
  <ul>
  <li>How many of them you need? With more granular time, you get more unknowns and more constraints and the complexity grows quickly.</li>
  <li>When someone gets a car, they probably use it to travel somewhere, so it may be necessary to assign the driver to the car for multiple subsequent slices <em>depending in the distance</em>. That's something completely missing from your description (so I'll ignore it).</li>
  </ul>
  
  <hr>
  
  <p>As already said, you need a cost function, i.e., something to minimize. Even before that, you need to define your variables. Let's say, you need <em>binary</em> variables</p>
  
  <pre><code>x[t, c, e] 
  </code></pre>
  
  <p>such that <code>x[t, c, e] = 1</code> when at time slice <code>t</code> the car <code>c</code> is assigned to the employee <code>e</code> (otherwise, it's zero). Now, we can specify some constraints</p>
  
  <ul>
  <li><code>x[t, c, e] = 0</code> for each <code>t</code>, when the employee <code>e</code> can't drive the car <code>c</code></li>
  <li>for each <code>t</code> and <code>c</code>, the sum of <code>x[t, c, e]</code> over all <code>e</code> is at most one (as no employee can use two cars at the same time)</li>
  <li>for each <code>t</code> and <code>e</code>, the sum of <code>x[t, c, e]</code> over all <code>c</code> is at most one (as no car can be use twice at the same time)</li>
  </ul>
  
  <p>I may have missed some constraints, but that's no big deal; I hope you've got the idea.</p>
  
  <hr>
  
  <p>Your cost function will be a sum of a few terms.</p>
  
  <ul>
  <li>What you wrote about priorities is unclear to me, too, but you can define a weight <code>w[c, e]</code> (or maybe just <code>w[c]</code>), so let the sum of <code>w[c, e] * x[t, c, e]</code> over all <code>t</code>, <code>c</code> and <code>e</code> be the term describing these priorities.</li>
  <li>Let <code>u[e]</code> be the cost of giving the employee <code>e</code> no car. The expression <code>y[t, e] = 1 - sum over all c of x[t, c, e]</code> equals to one, when the employee <code>e</code> has no car at time slice <code>t</code>. Now, the corresponding cost term can be expressed as the sum of <code>u[e] * y[t, e]</code> over all <code>e</code> and <code>t</code>.</li>
  </ul>
  
  <p>Again, there may be more of this.</p>
  
  <hr>
  
  <p>What I described so far is a <a href="https://en.wikipedia.org/wiki/Integer_programming" rel="nofollow noreferrer">integer linear programming</a> formulation of your problem. Convert my text into ILP generating code, get an ILP solver, feed it and run it....</p>
  
  <p>When you problem is small, you may even get the optimum. Otherwise, you'll get <em>some</em> solution (this is guaranteed) and a bound on the optimum, so you can know how far you <em>might</em> improve.</p>
  
  <p>That's more than any heuristic solver (e.g., simulated annealing) can offer. OTOH arriving at a good solution may be faster using some heuristic solver. But that's all irrelevant until you get a clear problem definition.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-24T01:01:29.883Z
Answers.LastActivityDate: 2020-01-24T01:01:29.883Z
Answers.UserDisplayName: maaartinus
Answers.Body: <p>I think there are different ways to solve the problem you presented:
  1) It could be seen as classical resource optimization problem that can be solved via Linear Programming setup (highly suggested taking a look, not everything needs ML). You can find some resources <a href="http://home.ubalt.edu/ntsbarsh/opre640a/partVIII.htm" rel="nofollow noreferrer">here</a> and quick intro to LP <a href="http://home.ubalt.edu/ntsbarsh/opre640a/partVIII.htm#rlp" rel="nofollow noreferrer">here</a></p>
  
  <blockquote>
    <p>Linear Programming (LP) is a mathematical procedure for determining optimal allocation of scarce resources. LP is a procedure that has found practical application in almost all facets of business, from advertising to production planning. Transportation, distribution, and aggregate production planning problems are the most typical objects of LP analysis. In the petroleum industry, for example a data processing manager at a large oil company recently estimated that from 5 to 10 percent of the firm's computer time was devoted to the processing of LP and LP-like models.</p>
  </blockquote>
  
  <p>2) Setup as ML problem using Deep Q-learning Network (might be overkill), at least it comes to my mind as easier setup (potentially). There are probably tons of ways to set your problem and environment. With DQN you would build an simulated environment for your problem where you create an list (or dictionary) of cars with the license requirement, a list for employees and their license, another one for schedule which could simply state 0 = no meeting at that time, 1 = meeting at that time (assuming not all employees need a car at all hours, if that is not true, then you can even remove the schedule requirement). </p>
  
  <p>So DQN is all about action -> reward optimization. You feed in a state, that could be a series of variables, and it spins our an array of actions with their respective scoring. For state columns, you could use cars availability (like one column per vehicle), while actions could be a 2-dimensional array of weather each employee might take a specific car. You could leave in the environment simulator the logic check of weather an employee has the correct license. I.e. if the model sends an employee to the wrong licensed car, then you can return a negative value as penalty as reward. For correct assignment, reward could be reward assigned to each employee (fixed or variable) minus cost of car. </p>
  
  <p>Once trained, at any given state sent to the model, it should output a 2D matrix showing the score of each employee taking each vehicle. For each vehicle, you could select the employee that would get max score, so just numpy slicing and dicing at that point. Again this is a quick idea after 10 minutes of thoughts, so take with little pinch of salt. Also there are many DQN flavors (target-Q, dueling-Q, experience replay, rainbow DQN etc.)</p>
  
  <p>3) Use the DQN structure above but simply it into a Q-learning problem. The actions set could be the same, but state could simply by period of your schedule (1,2,3,4,5...). You leave most logic to the simulated environment, like availability of cars at each period state (like at each state, based on actions return, you can dynamically set which cars will be available for next one). Make sure you set reward and penalty correctly. Create a good balance of exploration vs exploiting, maybe using epsilon-greedy policy and let it run.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-24T17:05:17.613Z
Answers.LastActivityDate: 2020-01-24T17:13:21.730Z
Answers.LastEditDate: 2020-01-24T17:13:21.730Z
Answers.UserDisplayName: wyrml4
Body: <p>I having trouble finding some starting points for solving an occupancy  problem which seems like a good candidate for ai.</p>
  
  <p>Assume the following situation:
  In a company I have n cars and m employees. Not every employee can drive any car (f. e. a special driving license is required). A car can only be used by one employee at a specific point in time.</p>
  
  <p>There is a plan which states which employee must be somewhere within some time (therefor they must use a car, so the car is blocked for that amount of time).</p>
  
  <p>The goal is to find a near optimal occupancy of the cars according to that plan.</p>
  
  <p>This problem is easy to specify, but I'm stumped as to which methods to implement.</p>
  
  <p>As it can be represented by a graph I think the right way to solve such a problem is using searching techniques, but a problem here is that I don't know the goal state (and there is no efficient way to compute it - thats the task I want the ai to do...). Neither finding the goal state is in fact part of the problem.</p>
  
  <p>So my question is: What ai techniques could be used to solve such a problem ?</p>
  
  <p>Edit: Some clarification:</p>
  
  <p>Assmume we have two sets - one of the employees (E) and one of cars (C). |C| &lt; |E| is most likely true.
  Each car has an assigned priority which corresponds to the costs of using it (for example using a Ferrari costs more than using a Dacia, therefore a Dacia has a higher priority (ex. 1) compred to the Ferrari (ex. 10))).
  Assume further that having employees which are not using a car at a specific time slice are a bad thing - they cost an individual penalty (you want the employeed to be at the customer and sell things etc.).<br>
  The goal is to find the occupation of employees and cars which has a low total cost. </p>
  
  <p>One Example: If you assign an employee to a car at a specific time slice  it may turn out that another employee gets no car within that time slice.
  This can be either because </p>
  
  <ul>
  <li>a car is free, but he has no license for it   </li>
  <li>because a car is free, but the costs of using this car would be higher than having the employee staing at the head quater </li>
  <li>because no car is free anymore</li>
  </ul>
  
  <p>Of cause it could be better in terms of costs to change the occupation and give that employee which got no car in this solution a car and therefore having another employee getting no car or not using all cars or ...</p>
  
  <p>Note: There is no need to find an exact optimal solution (=lowest total cost of all possible occupations), as this would require checking out all possible occupations of the exponential solution space.
  Insetad finding a more or less good approximation of a near-optimal low total cost is sufficent.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-01-16T19:23:21.597Z
Comments.Text: What are you optimizing? Are some cars more expensive to drive than others? Otherwise I would think any allocation that worked would be as good as any other allocation.
Comments.UserDisplayName: George White
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-01-16T19:55:10.403Z
Comments.Text: Same question as Welker. Other than having enough cars to meet maximum demand (which is a simple matter of finding the time in the plan when the most employees are out, and counting them), there does not appear to be any optimisation to do yet. Is some detail missing?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-01-17T08:03:47.017Z
Comments.Text: @GeorgeWhite I added some clarification. I hope it is more clear now.
Comments.UserDisplayName: Welker
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-01-20T09:48:21.353Z
Comments.Text: I do not think adding a bounty will help here. The question is still poorly specified. I suggest trying to forumate the problem mathematically. It will either be clearer to readers what you are asking, or more likely here I think it will expose where the incomplete/woolly thinking is occurring and we can base answers around resolving that
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-01-20T13:04:07.017Z
Comments.Text: The first step would be to specify the cost function you are trying to optimize. If you cannot assess the quality of a solution, you are not going to find a good solution.
Comments.UserDisplayName: BlindKungFuMaster
Tags: <algorithm><optimization><problem-solving><graph-theory>
Title: Solving a planning if finding the goal state is part of the problem
UserDisplayName: Welker
ThreadText: # Solving a planning if finding the goal state is part of the problem
  
  (Asked by: username_0 on 2020-01-16)
  
  I having trouble finding some starting points for solving an occupancy problem which seems like a good candidate for ai.
  
  Assume the following situation:
  In a company I have n cars and m employees. Not every employee can drive any car (f. e. a special driving license is required). A car can only be used by one employee at a specific point in time.
  
  There is a plan which states which employee must be somewhere within some time (therefor they must use a car, so the car is blocked for that amount of time).
  
  The goal is to find a near optimal occupancy of the cars according to that plan.
  
  This problem is easy to specify, but I'm stumped as to which methods to implement.
  
  As it can be represented by a graph I think the right way to solve such a problem is using searching techniques, but a problem here is that I don't know the goal state (and there is no efficient way to compute it - thats the task I want the ai to do...). Neither finding the goal state is in fact part of the problem.
  
  So my question is: What ai techniques could be used to solve such a problem ?
  
  Edit: Some clarification:
  
  Assmume we have two sets - one of the employees (E) and one of cars (C). |C| < |E| is most likely true.
  Each car has an assigned priority which corresponds to the costs of using it (for example using a Ferrari costs more than using a Dacia, therefore a Dacia has a higher priority (ex. 1) compred to the Ferrari (ex. 10))).
  Assume further that having employees which are not using a car at a specific time slice are a bad thing - they cost an individual penalty (you want the employeed to be at the customer and sell things etc.).  
  The goal is to find the occupation of employees and cars which has a low total cost.
  
  One Example: If you assign an employee to a car at a specific time slice it may turn out that another employee gets no car within that time slice.
  This can be either because
  
  * a car is free, but he has no license for it
  * because a car is free, but the costs of using this car would be higher than having the employee staing at the head quater
  * because no car is free anymore
  
  Of cause it could be better in terms of costs to change the occupation and give that employee which got no car in this solution a car and therefore having another employee getting no car or not using all cars or ...
  
  Note: There is no need to find an exact optimal solution (=lowest total cost of all possible occupations), as this would require checking out all possible occupations of the exponential solution space.
  Insetad finding a more or less good approximation of a near-optimal low total cost is sufficent.
  
  **Tags:** algorithm, optimization, problem-solving, graph-theory
  
  > **Comments:**
  > **username_1**: What are you optimizing? Are some cars more expensive to drive than others? Otherwise I would think any allocation that worked would be as good as any other allocation.  
  > **username_2**: Same question as username_0. Other than having enough cars to meet maximum demand (which is a simple matter of finding the time in the plan when the most employees are out, and counting them), there does not appear to be any optimisation to do yet. Is some detail missing?  
  > **username_0**: @username_1 I added some clarification. I hope it is more clear now.  
  > **username_2**: I do not think adding a bounty will help here. The question is still poorly specified. I suggest trying to forumate the problem mathematically. It will either be clearer to readers what you are asking, or more likely here I think it will expose where the incomplete/woolly thinking is occurring and we can base answers around resolving that  
  > **username_3**: The first step would be to specify the cost function you are trying to optimize. If you cannot assess the quality of a solution, you are not going to find a good solution.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_4 on 2020-01-24. Score: 1
  
  Your question is still nearly perfectly unclear, but let's make a few guesses in order to make some progress.
  
  The biggest mystery are your time slices:
  
  * How many of them you need? With more granular time, you get more unknowns and more constraints and the complexity grows quickly.
  * When someone gets a car, they probably use it to travel somewhere, so it may be necessary to assign the driver to the car for multiple subsequent slices *depending in the distance*. That's something completely missing from your description (so I'll ignore it).
  
  ---
  
  As already said, you need a cost function, i.e., something to minimize. Even before that, you need to define your variables. Let's say, you need *binary* variables
  
  ```
  x[t, c, e] 
  
  ```
  
  such that `x[t, c, e] = 1` when at time slice `t` the car `c` is assigned to the employee `e` (otherwise, it's zero). Now, we can specify some constraints
  
  * `x[t, c, e] = 0` for each `t`, when the employee `e` can't drive the car `c`
  * for each `t` and `c`, the sum of `x[t, c, e]` over all `e` is at most one (as no employee can use two cars at the same time)
  * for each `t` and `e`, the sum of `x[t, c, e]` over all `c` is at most one (as no car can be use twice at the same time)
  
  I may have missed some constraints, but that's no big deal; I hope you've got the idea.
  
  ---
  
  Your cost function will be a sum of a few terms.
  
  * What you wrote about priorities is unclear to me, too, but you can define a weight `w[c, e]` (or maybe just `w[c]`), so let the sum of `w[c, e] * x[t, c, e]` over all `t`, `c` and `e` be the term describing these priorities.
  * Let `u[e]` be the cost of giving the employee `e` no car. The expression `y[t, e] = 1 - sum over all c of x[t, c, e]` equals to one, when the employee `e` has no car at time slice `t`. Now, the corresponding cost term can be expressed as the sum of `u[e] * y[t, e]` over all `e` and `t`.
  
  Again, there may be more of this.
  
  ---
  
  What I described so far is a [integer linear programming](https://en.wikipedia.org/wiki/Integer_programming) formulation of your problem. Convert my text into ILP generating code, get an ILP solver, feed it and run it....
  
  When you problem is small, you may even get the optimum. Otherwise, you'll get *some* solution (this is guaranteed) and a bound on the optimum, so you can know how far you *might* improve.
  
  That's more than any heuristic solver (e.g., simulated annealing) can offer. OTOH arriving at a good solution may be faster using some heuristic solver. But that's all irrelevant until you get a clear problem definition.
  
  
  ---
  
  ### Answer by username_5 on 2020-01-24. Score: 1
  
  I think there are different ways to solve the problem you presented:
  1) It could be seen as classical resource optimization problem that can be solved via Linear Programming setup (highly suggested taking a look, not everything needs ML). You can find some resources [here](http://home.ubalt.edu/ntsbarsh/opre640a/partVIII.htm) and quick intro to LP [here](http://home.ubalt.edu/ntsbarsh/opre640a/partVIII.htm#rlp)
  
  > Linear Programming (LP) is a mathematical procedure for determining optimal allocation of scarce resources. LP is a procedure that has found practical application in almost all facets of business, from advertising to production planning. Transportation, distribution, and aggregate production planning problems are the most typical objects of LP analysis. In the petroleum industry, for example a data processing manager at a large oil company recently estimated that from 5 to 10 percent of the firm's computer time was devoted to the processing of LP and LP-like models.
  
  2) Setup as ML problem using Deep Q-learning Network (might be overkill), at least it comes to my mind as easier setup (potentially). There are probably tons of ways to set your problem and environment. With DQN you would build an simulated environment for your problem where you create an list (or dictionary) of cars with the license requirement, a list for employees and their license, another one for schedule which could simply state 0 = no meeting at that time, 1 = meeting at that time (assuming not all employees need a car at all hours, if that is not true, then you can even remove the schedule requirement).
  
  So DQN is all about action -> reward optimization. You feed in a state, that could be a series of variables, and it spins our an array of actions with their respective scoring. For state columns, you could use cars availability (like one column per vehicle), while actions could be a 2-dimensional array of weather each employee might take a specific car. You could leave in the environment simulator the logic check of weather an employee has the correct license. I.e. if the model sends an employee to the wrong licensed car, then you can return a negative value as penalty as reward. For correct assignment, reward could be reward assigned to each employee (fixed or variable) minus cost of car.
  
  Once trained, at any given state sent to the model, it should output a 2D matrix showing the score of each employee taking each vehicle. For each vehicle, you could select the employee that would get max score, so just numpy slicing and dicing at that point. Again this is a quick idea after 10 minutes of thoughts, so take with little pinch of salt. Also there are many DQN flavors (target-Q, dueling-Q, experience replay, rainbow DQN etc.)
  
  3) Use the DQN structure above but simply it into a Q-learning problem. The actions set could be the same, but state could simply by period of your schedule (1,2,3,4,5...). You leave most logic to the simulated environment, like availability of cars at each period state (like at each state, based on actions return, you can dynamically set which cars will be available for next one). Make sure you set reward and penalty correctly. Create a good balance of exploration vs exploiting, maybe using epsilon-greedy policy and let it run.
  
  
  ---
  
  