00:00:14.360
I would like to begin by sharing a few words about myself. I work as a Ruby on Rails developer at a company called SoftSwiss. We are involved in the IG gambling industry, and I am also a PhD candidate currently working on projects related to drones. Besides that, I am interested in areas like cloud computing, linear programming, financial markets, and of course, everything related to software engineering.
00:00:28.119
Let’s start with the formal definition of mathematical programming. Mathematical programming, or mathematical optimization, is a systematic approach used to optimize the value of an objective function with respect to a set of constraints. We can simplify this by saying that it is an attempt to define our specific problem using mathematical equations along with some key elements such as decision variables, constraints, objective functions, and others, aiming to achieve the best possible solution.
00:01:02.960
To define our problem, we need to utilize several elements. First of all are the parameters, which are the values that remain constant during the program execution. Next, we have decision variables, which are the unknowns we want to determine. Our goal is to find the optimal values for these decision variables, which are subject to constraints. These constraints limit the possible values the decision variables can take, thus establishing the conditions for our optimization problem.
00:01:49.960
When we look at an example, we might define a condition where the sum of two variables must be less than or equal to 10. Our objective is a value that we want to either minimize or maximize. In our example, we are trying to maximize our objective function, which is represented as X1. So, with the constraint that X1 + X2 is less than or equal to 10, we aim to select the solution that provides the highest value for X1, which would yield X1 = 7 and X2 = 3.
00:03:00.519
While some problems may seem straightforward, the strategies behind mathematical programming can be applied in real-life contexts, especially in large corporations. A notable company in this field is Gurobi, a leader in mathematical programming software for linear optimization, collaborating with high-tech firms like Air France. Their strategies have allowed companies like Air France to efficiently create flight schedules, save on fuel costs, and minimize delays. Similarly, mathematical programming is employed by Copenhagen Airport for assigning check-in tasks and optimizing supply chains.
00:03:47.600
There are four primary classes of problems in mathematical programming. The first two classes are linear programming problems. The first type involves only linear variables, meaning we can have decimal values, not limited to integers. While we can introduce integer constraints, it increases complexity. The second type is quadratic programming, which is more advanced and complicated, but we'll primarily focus on linear programming today.
00:05:07.040
This discussion relates to the P versus NP problem in computer science, where 'P' represents problems solvable in polynomial time, and 'NP' refers to problems of higher complexity. Currently, we cannot prove if P and NP are equivalent, but we assume they are not as we lack polynomial solutions for NP problems. Linear programming falls within the P class and is easily solvable. In contrast, mixed integer linear programming, which includes integer variables, unfortunately belongs to NP and can be much harder to solve, often requiring considerable computational resources.
00:06:04.800
How can we implement mathematical programming using Ruby? It requires two main components: a solver, which operates as a black box, providing us with the best solution for predefined problems, and a library to facilitate communication between Ruby and the solver. We can use the GEM library as a wrapper, or even a specialized modeling language, although the latter is quite rare in the Ruby world. We will proceed with GEM in our example.
00:07:22.720
When selecting a solver, we have several classes to consider. Commercial solvers are often faster and require fewer resources to resolve the same issues, but they can be quite expensive. In contrast, we will use an open-source solver to save costs. The HiGHS solver is a suitable option for our needs, although there are slower alternatives like CBC which can handle basic cases effectively.
00:09:17.720
In the Ruby environment, two popular libraries are available: Ruby CBC, which is specifically designed for the CBC solver and restricts the use of other solvers, and 'R', a comprehensive solution for linear programming in Ruby. Approaches such as JRuby or PEL can be used to integrate with commercial libraries or Python libraries widely used in scientific contexts. However, for our current focus, we will leverage 'R' as it aligns with our preferences.
00:10:49.560
The 'R' library is a Ruby DSL designed for linear optimization. It supports multiple solvers, such as CBC and commercial options like Gurobi. The library uses an LP problem format to describe optimization problems, ensuring easy migration to commercial stacks without vendor lock-in. If you need to enhance functionality, adding components to the 'R' library can be completed quickly and efficiently.
00:12:01.880
To define variables in the 'R' library, you must use capital letters followed by proper suffixes indicating their types. For instance, if you want to define integer variables, you would use the corresponding suffix. The goal is to set an objective, which is to either minimize or maximize the defined problem. Constraints are established after specifying the problem type, and we select a solver to find the best solution based on the environment variable settings.
00:14:15.600
I have prepared a simple demo to illustrate this process. In our basic code, we select the appropriate solver, define the log level, and set an objective involving two variables. In this scenario, we find that the sum of the variables must equal 10, with all variables required to be non-negative. We will solve this and check the result.
00:15:07.280
As expected, the result reveals that X2 equals 10 and X1 equals 0, which is accurate as increasing X1 would yield a better objective value faster than increasing X2. However, challenges can arise from incorrect problem definitions. It's possible for a problem to be infeasible due to conflicting constraints or unbounded when not enough constraints are set. We want to avoid such scenarios.
00:16:01.480
For instance, if we impose two conflicting constraints, saying that X1 + X2 must equal both 10 and 5, it is impossible. In this case, we received an 'infeasible' result. On the other hand, if we want to maximize the sum with just two positive constraints, our objective may lead to an unbounded solution set, allowing for infinite increases of X1 and X2.
00:17:31.000
Next, let’s tackle a more complex scenario— the knapsack problem. Here, we have a backpack with a weight capacity of 15 kg and several items that take up space while providing profit. Our goal is to maximize profit without exceeding the weight limit. The decision variables in this case will represent whether an item is selected or not. If an item is not selected, its value is 0; if it is selected, it contributes to both weight and profit.
00:18:26.000
In the Ruby code, we set the variable Z to represent backpack capacity and define parameters including the width of each item and the profit associated with it. We create five decision variables and assign constraints ensuring that the total weight does not exceed the backpack's capacity while aiming to maximize overall profits. Now, let's execute this code to see how it performs.
00:19:34.640
Upon execution, we find that we should take all items except the one weighing 12 kg that provides a profit of $4. The optimal solution results in a total profit of $15 with a weight of 8 kg, demonstrating the effectiveness of this approach.
00:20:51.440
Now, let’s discuss a practical application involving a public transportation system. Our goal is to find the shortest route from point A to point B, focusing solely on minimizing arrival time. We will simplify this process while acknowledging that we have limited data, ignoring vehicle route changes and delays. Real-world systems have already integrated similar approaches, like the app Ygoda in Poland and Google Maps, which provide guidance for public transport routes.
00:21:43.680
We have a simplified graph showing public transport stops (labeled A, B, C, and D) and the lines numbered for identification. The departure times for line number two provide a useful reference for our analysis. Utilizing a real dataset from a Polish city, we discovered a public transport system consisting of 172 stops and 18 lines with over 1,000 daily courses.
00:22:54.400
Moving forward, we can define the set containing the stops and routes, along with parameters that capture arrival times and passenger journey details. Constraints will ensure a logical progression of rides while maximizing efficiency. It is essential to validate that the start of the journey occurs only after arriving at the initial stop.
00:24:06.720
After developing approximately 100 lines of Ruby code parsing the user input for starting and destination stops, we check arrival timing and set constraints to create valid routes. By finding the best route, users can take advantage of the public transport system, and we will display resulting travel information on their console.
00:25:00.960
For example, searching for a route between two stops at 6:50 AM, we load a dataset comprising 5 megabytes of information. The system generates a successful route, departing at 6:52 AM and requiring only two transfers, arriving at 7:26 AM, which is the optimal solution in our modeled approach.
00:26:00.000
We can compare this result with data generated by commercial solutions, which might provide similar recommendations but also showcase discrepancies based on updated, real-time information. Sometimes, commercial applications can suggest faster routes because they use live traffic conditions, while our solution may lack that insight.
00:27:42.760
There are various reasons for these differences. Our simplistic model relies on official timetables without the flexibility to integrate real-time data. Although apps like Ygoda leverage historical and live data, which enhances accuracy, our current implementation does not anticipate changes or available routes effectively.
00:29:31.000
To mitigate these challenges, models must adapt continuously to incorporate live data, creating more reliable results. Nevertheless, executing calculations over extensive datasets can result in longer processing times, especially with larger urban areas.
00:30:09.480
To make constant updates feasible, we could aggregate data, rejection criteria for distant stops within the model to streamline route-finding, and even break our problem down into manageable sub-problems for simpler calculations. For urban planning, combining different mathematical methods may yield better results, although our methodology should be considered with caution.
00:31:27.120
Finally, we should explore alternative solutions that may provide better performance. Graph algorithms, for instance, can be optimal for some tasks within a reasonable execution time. Mathematical programming can still play a significant role when immediate responses aren't required, enabling background calculations to yield optimal solutions over a more extended period.
00:32:44.760
Non-trivial problems often necessitate complex algorithms, but utilizing specialized software for mathematical programming can help eliminate the need for developing intricate algorithms ourselves. That's a brief overview of the topic; I hope you found it insightful. If you have any questions, I'll be glad to answer them. Thank you very much!