Search

Solving Mixed Integer Programming (MIP) problems is critical for numerous applications in digital asset management. Traditional solvers, which rely on techniques like branch-and-bound and branch-and-cut, face computational challenges when dealing with large-scale and complex problem instances. Recent advances in machine learning (ML) have introduced new approaches to enhance these traditional solvers by optimizing key decision-making processes such as branching, cut generation, and heuristic selection. In this paper, we examine hybrid methods that combine ML with classical MIP methodologies, leveraging supervised learning, reinforcement learning, and graph neural networks to improve solver efficiency and scalability. These hybrid methods significantly reduce computational overhead by making smarter decisions during the optimization process, resulting in faster convergence and higher-quality solutions. We also discuss the challenges of generalization and integration of ML models with existing solvers and propose future research directions to further advance this field.

The multi-agent surveillance problem is to find optimal trajectories of multiple agents that patrol a given area as evenly as possible. In this paper, we consider the multi-agent surveillance problem based on travel cost minimization. The surveillance area is given by an undirected graph. The penalty for each agent is introduced to evaluate the surveillance performance. Through a mixed logical dynamical system model, the multiagent surveillance problem is reduced to a mixed integer linear programming (MILP) problem. In model predictive control, trajectories of agents are generated by solving the MILP problem at each discrete time. Furthermore, a condition that the MILP problem is always feasible is derived based on the Chinese postman problem. Finally, the proposed method is demonstrated by a numerical example.

A static-dynamic topology-sizing optimisation method is presented. The solution is based on a sequential Mixed-Integer Linear Programming solution and aims to minimise the mass of a structure subjected to concurrent constraints on static and dynamic response. It is shown that the classical problem of the dynamics of lightweight sandwich structures may be mitigated through core topology and face sheet thickness combinations, retaining the static load carrying capacity while presenting stringent dynamic properties at a low mass penalty. A numerical example, in the form of a load carrying sandwich beam which is excited at different frequencies, is used to demonstrate the method., QC 20240906

This paper presents a novel partially distributed outer approximation algorithm, named PaDOA, for solving a class of structured mixed integer convex programming problems to global optimality. The proposed scheme uses an iterative outer approximation method for coupled mixed integer optimization problems with separable convex objective functions, affine coupling constraints, and compact domain. PaDOA proceeds by alternating between solving large-scale structured mixed-integer linear programming problems and partially decoupled mixed-integer nonlinear programming subproblems that comprise much fewer integer variables. We establish conditions under which PaDOA converges to global minimizers after a finite number of iterations and verify these properties with an application to thermostatically controlled loads and to mixed-integer regression.

This paper presents two novel formulations for scheduling problems, namely order- position hybrid formulation (OPH) and order-disjunctive hybrid formulation (ODH), which extend and combine parts of existing formulation strategies. The first strategy (OPH) is based on sequence position and linear ordering formulations, adding relationships between constraints that allow relaxing some decision variables. The second approach (ODH) is based on linear ordering and disjunctive formulations. In this work, we prove ODH to be the most efficient formulation known so far. The experiments have been carried out with a large set of problems, which consider single machines and identical parallel machines. Computational results show that OPH is better than the rest of the existing formulations for the case of weighted completion objectives, while ODH turns out to be the best approach for most scenarios studied.

The purpose of the project presented in this thesis is to build a post-processing model of an Electric Vehicle Routing Problem (eVRP) and investigate the performance of it. The model was formulated as a Mixed Integer Program (MIP) using a production scheduling framework. It was then implemented in Python, and solved using Gurobi and CBC. The aim of the post-processing was to reduce waiting time in the original schedules. Constraints related to vehicle shifts, time windows for pickups and deliveries, task precedence and limited resource availability were to be respected. Four different electric vehicle fleets were considered when genrating the results for the thesis, each containing a different number of vehicles and tasks. Each fleet was characterized by a set of known input paramteres. The smallest fleet considered includes two vehicles, while the largest fleet included 20 vehicles. The model proved to be successful for the smaller fleet sizes, yet was not able to find solutions within a reasonable amount of time for the largest fleet size., Syftet med projektet som presenteras i den här rapporten var att bygga en efterbearbetningsmodell till en Electric Vehicle Routing Problem (eVRP), samt att undersöka modellens prestanda. Modellen formulerades matematiskt som ett Mixed Integer Program (MIP) genom att använda ett ramverk för schemaläggning av produktionssystem. Modellen implementerades numeriskt i Python, med hjälp av lösarna Gurobi och CBC. Målet med modellens efterarbetsning var att reducera väntetider i de ursprungliga scheman. Begränsningarna relaterade till skifts start- och sluttider, tidsfönster för upphämtning och avlämning, turordning och begränsad tillgång till resurser var tvunget att respekteras. Resultat genererades för fyra olika flottor av elektriskt drivna bilar, var och en med ett visst antal bilar, och ett visst antal uppdrag tillhörande varje bil. Varje flotta karaktäriserades även av ett antal kända inparametrar. Den minsta flottan innehöll två fordon, medan den största flottan innehöll 20 fordon. Modellen visade sig vara lämplig och producerade önskvärda resultat för de mindre flottorna, däremot kunde ingen lösning hittas inom rimlig tid för den största flottan med 20 fordon.

After graduation, physicians receive further training in a medical domain like anesthesiology. There are 57 medical specialties in Germany in total. The high cost pressures of hospitals and the changing view of the medical profession regarding the work-life balance have led to recruitment problems and low employee satisfaction in many places. A promising approach to counter this problem is objective and structured training planning. This research project mainly deals with medical residents’ strategic and tactical-operative training scheduling. In addition to relieving the medical staff currently responsible for the planning process, this research project increases the predictability of structured training. This allows hospitals to increase the quality of their training and, consequently, their attractiveness to other hospitals. In addition, supervisors from different departments can better assess residents’ knowledge and thus keep the level of service, which is particularly important in hospitals, permanently high even when changing residents. From the residents’ point of view, a well-structured training schedule enables a high degree of information. Therefore, residents are no longer surprised by a short-term change of department and have a direct insight into their training progress. A real-world case study evaluates the mathematical formulations and the solution approaches.

Traffic congestion is a significant problem in major metropolitan areas in the United States. According to the Urban Mobility Report, in 2019 commuters on average lost about 54 hours in traffic congestion. To combat this, major infrastructure projects have been undertaken. However, expansion projects cannot keep up with the increase in usage of personal vehicles and thus fail to address the traffic congestion problem. Carpool ridesharing has shown some promise in combatting this traffic congestion problem. In this system, the drivers are regular commuters who take detours to pick up and drop off passengers to decrease their transportation costs. This system increases the efficiency of the transportation system by providing flexible commutes to people, thus reducing the need for each commuter to use their own personal vehicle. The researchers developed three approaches to rideshare routing. The researchers conducted a computational study using a San Francisco taxicab dataset to determine the effectiveness of the three approaches. To show the impact of flexible meeting points, the researchers also conducted experimental simulations with and without walking and performed sensitivity analyses.View the NCST Project Webpage

This thesis addresses route planning of Battery Electric Heavy-Duty Commercial Vehicles to enhance the reliability of electric vehicle transport. Collaborating with Scania, a Swedish truck manufacturing company, the goal is to develop a pipeline that uses open source data from OpenStreetMap and performs a modified Contraction Hierarchy in order to create a graph that can be used as input to a modified Vehicle Routing Problem formulation using Mixed Integer Programming. The input graph is preprocessed to support a Battery Electric Heavy-Duty Commercial Vehicle model in order to more accurately predict energy consumption. The challenges lie in balancing computational efficiency and electric vehicle characteristics. The implemented pipeline demonstrates success but initial tests show that a naive version of the pipeline, not implementing Contraction Hierarchies, can perform better. Several speedups can be made in order to improve the efficiency of the pipeline, the main being in programming in a more efficient programming language than Python. Further testing is needed for larger input graphs to assess performance accurately.

In today's travel and tourism landscape, the role of travel agents has become increasingly complex as they are challenged to explore a variety of potential destinations. More specifically, the complicated task of planning itineraries that truly satisfy travellers puts travel agents in a crucial role, increasing the complexity of itinerary planning. This complexity is compounded not only by the multitude of possible destinations, but also by non-negotiable constraints such as cost and time. To address these challenges, the orienteering problem represents a fundamental mathematical model that provides a theoretical basis for understanding the nuanced difficulties faced by travel agents.This study ventures into a novel iteration of the orienteering problem, with a particular focus on optimizing travel satisfaction based on length of stay. A notable aspect of this variant is the inclusion of time and cost constraints in the route determination process. Using an integer programming model, the satisfaction scores for each location are described by a diminishing returns function linked to length of stay, while the costs associated with each location follow a linear function influenced by the same parameter. The application of this model is in a hypothetical scenario with 32 nodes, with the calculations facilitated by the FilMINT solver. A sensitivity analysis examines time and cost constraints and shows their decisive influence on the optimization of travel routes. The results of this research contribute significantly to a strategic framework and provide travel agencies with the opportunity to create itineraries that not only meet practical limits but, more importantly, increase traveller satisfaction.

En: G. Di Stefano, A. Navarra Editors: Proceedings of the GEOSAFE Workshop on Robust Solutions for Fire Fighting L'Aquila, Italy, July 19-20, 2018., In order to respond the question “Where to locate fuel breaks?”, a peculiar location model is presented involving stochastic mixed integer nonlinear optimization, Bayesian networks and directional statistic inference. From a first simple approximation to the large model, will be shown what motivates follow models and its complexity incorporated. Also, a case study with real data about Corsica region is presented., Depto. de Estadística e Investigación Operativa, Fac. de Ciencias Matemáticas, TRUE, pub

This is a post-peer-review, pre-copyedit version of an article published in Environmental Modeling & Assesment. The final authenticated version is available online at: http://dx.doi.org/10.1007/s10666-018-9642-2, Wildfires have demonstrated their destructive powers in several parts of the world in recent years. In an effort to mitigate the hazard of large catastrophic wildfires, a common practice is to reduce fuel loads in the landscape. This can be achieved through prescribed burning or mechanically. Prioritising areas to treat is a challenge for landscape managers. To help deal with this problem, we present a spatially explicit, multiperiod mixed integer programming model. The model is solved to yield a plan to generate a dynamic landscape mosaic that optimally fragments the hazardous fuel continuum while meeting ecosystem considerations. We demonstrate that such a multiperiod plan for fuel management is superior to a myopic strategy. We also show that a range of habitat quality values can be achieved without compromising the optimal fuel reduction objective. This suggests that fuel management plans should also strive to optimise habitat quality. We illustrate how our model can be used to achieve this even in the special case where a faunal species requires mature habitat that is also hazardous from a wildfire perspective. The challenging computational effort required to solve the model can be overcome with either a rolling horizon approach or lexicographically. Typical Australian heathland landscapes are used to illustrate the model but the approach can be implemented to prioritise treatments in any fire-prone landscape where preserving habitat connectivity is a critical constraint., Unión Europea. Horizonte 2020, Ministerio de Ciencia e Innovación, Comunidad de Madrid, Universidad Complutense de Madrid, Fac. de Ciencias Matemáticas, TRUE, pub

Broadcasting, which is an essential mode of operation in wireless sensor networks (WSNs), dissipates a non-negligible portion of the energy budget of a sensor node. Broadcasting is achieved by the dissemination of broadcast packets (originated at the BS) by a set of relay nodes, which constitute a backbone so that all sensor nodes receive broadcast packets. Utilization of multiple backbones is necessary to achieve balanced energy dissipation of sensor nodes in broadcasting. In this study, we propose two mixed integer programming (MIP) models (i.e., the flow-based model and the node-based model), which minimize the energy dissipation of the highest energy-consuming node for broadcasting by utilizing multiple backbones. Balanced energy minimization and delay minimization objectives are integrated through a goal programming (GP) framework built upon the foundation provided by the scalable node-based model. Performance evaluations based on the optimal solutions of our models reveal that maximum energy dissipation and delay in WSN broadcasting can be significantly reduced, simultaneously, by utilizing multiple backbones (e.g., with two backbones maximum energy dissipation and delay can be, concurrently, reduced by more than 2% and 22%, respectively, in comparison to the single backbone case, likewise, it is also possible to simultaneously reduce maximum energy dissipation and delay more than 8% and 13%, respectively, depending on the priorities assigned to the objectives). Nevertheless, employing more than two backbones does not provide any significant performance improvements. © 2023 Elsevier B.V., Türkiye Bilimsel ve Teknolojik Araştırma Kurumu, TÜBİTAK, Busra Gultekin was supported by TÜBİTAK BİDEB 2210 Scholarship Programme, Turkey .

Wireless Sensor Networks (WSNs) are an enabling technology for both Smart Grid (SG) and Internet of Things (IoT) applications, like many other fields, due to their low cost and ease of installation, as well as the advanced communication capabilities they offer. Self-sustaining SGs, which allow two-way data communication between their components, are proposed as a remedy for the shortcomings of the conventional electrical grid. In this framework, it is critical to design energy efficient communication protocols to achieve a long network lifetime while maintaining the desired coverage level. In this thesis, we consider the scenario where the transmission paths are re-adapted to topology changes as long as the current set of sensors with positive residual energy ensures the required coverage level and connectivity to the base station. To this end, we propose a novel 0-1 mixed integer programming (MIP) model and two alternative 0-1 MIP models that optimize network behavior in unit time decomposition with an emphasis on energy consumption. The study is unique since topology adaptation due to energy depletion is managed within a holistic solution framework based on optimization methods. To this end, we avoid the traditional network lifetime metric, the time until the First Sensor Dies - FSD, and allow the WSN to operate optimally as long as a predetermined coverage level and connectivity to the BS can be maintahed with the remaining sensors. Accordingly, we observe that network lifetime can be increased significantly even after a one-time reorganization. Besided, we also analyzed how the solutions of the proposed models differ in terms of network lifetime and the ensured coverage level. As a side contribution, for the classical one-period problem, we emprically show that maximizing the time until the first sensor dies is equivalent to minimizing the energy consumption of the most energy consuming sensor, which is not necessarily true in the case of any topology change. He, Kablosuz Algılayıcı Ağlar (KAA'lar) düşük maliyetleri ve kurulum kolaylıkları ile birlikte sundukları gelişmiş iletişim yetenekleri sayesinde diğer pek çok alan gibi, hem Akıllı Şebeke (İng. Smart Grid – SG) hem Nesnelerin İnterneti (İng. Internet of Things – IoT) uygulamaları için önemli bir teknoloji olarak görülmektedirler. Bileşenleri arasında iki yönlü veri iletişimine olanak sağlayan, kendi kendini idare edebilen SG'ler geleneksel elektrik şebekesinin eksikliklerine bir çare olarak önerilmektedir. Bu çerçevede, istenen kapsama seviyesini korurken, uzun bir ağ ömrü elde etmek için enerji verimli iletişim protokolleri tasarlamak büyük önem arz etmektedir. Tez kapsamında öncelikle, herhangi bir anda sistemde canlı olarak bulunan sensör kümesi ile gerekli kapsama seviyesi ve baz istasyonuna (BS'ye) bağlantılılık sağlanabildiği sürece iletim yollarının topoloji değişikliklerine yeniden uyarlandığı bir senaryo incelenmektedir. Özgün bir 0-1 karma tamsayılı programlama (İng. Mixed Integer Programming – MIP) modeli önerilmekte ve enerji tüketimi vurgusu ile birlikte birim zaman ayrıştırmasında ağ davranışını optimize eden iki alternatif 0-1 MIP modeli sunulmaktadır. Çalışma, optimizasyon yöntemlerine dayalı bütünsel bir çözüm çerçevesinde, enerji tükenmesi nedeniyle topoloji adaptasyonu içermesi açısından benzersizdir. Geleneksel bir ağ ömrü metriği olan ilk sensör ölünceye kadar geçen süre yerine önceden belirlenmiş kapsama seviyesi ve hayatta olan sensörlerle BS'ye bağlantı sağlanabildiği sürece KAA'nın optimal şekilde çalışmaya devam etmesine izin verilmekte ve tek seferlik bir yeniden düzenlemeden sonra bile ağ ömrünün önemli ölçüde artırılabileceği gözlemlenmektedir. Ayrıca, önerilen modellerin çözümlerinin ağ ömrü ve kapsama seviyesi açısından nasıl farklılık gösterdiği analiz edilmektedir. Bir yan katkı olarak, klasik tek periyotlu problem için; ilk sensör ölene kadar geçen sürenin (İng. First Sensor Dies – FSD) maksimize edilmesinin, en çok enerji harcayan sen

Operating costs are dominant in the hydrogen production of a power-to-hydrogen system. An optimal operational strategy or bidding framework is effective in reducing these costs. However, it is still found that the production cost of hydrogen is high. As the electrolysis unit is characterized by high flexibility, providing ancillary service to the grid becomes a potential pathway for revenue stacking. Recent research has demonstrated the feasibility of providing such a service, but the related economics have not been well evaluated. In this work, we propose a comprehensive operation model to enable participation in the day-head, balancing and reserve markets. Three types of reserves are considered by using different operational constraints. Based on the proposed operation framework, we assess the economic performance of a power-to-hydrogen system in Denmark using plentiful actual market data. The results reveal that providing frequency containment reserve and automatic frequency restoration reserve efficiently raises the operational contribution margins. In parallel, by investing in the cash flows, net present value, and break-even hydrogen prices, we conclude that providing reserves makes the power-to-hydrogen project more profitable in the studied period and region.

Machine learning’s impressive achievements in the last decade have urged many scientific communities to ask if and how the techniques developed in that field to leverage data could be used to advance research in others. The combinatorial optimisation community is one of those, and the area of data-driven combinatorial optimisation has emerged. The motivation of the seminar and its design and development have followed the idea of making researchers both in academia and industry belonging to different communities - from operations research to constraint programming, from artificial intelligence to machine learning - communicate, establish a shared language, and ultimately (try to) set the roadmap for the development of the field.

Partially spatially balanced Latin rectangles are combinatorial structures that are important for experimental design. However, it is computationally challenging to find even small optimally balanced rectangles, where previous work has not been able to prove optimality for any rectangle with a dimension above size 11. Here we introduce a graph-based encoding for the 2 × n case based on finding the minimum-cost clique of size n. This encoding inspires a new mixed-integer programming (MIP) formulation, which finds exact solutions for the 2 × 12 and 2 × 13 cases and provides improved bounds up to n = 20. Compared to three other methods, the new formulation establishes the best lower bound in all cases and establishes the best upper bound in five out of seven cases.

This paper considers the Maximum Selective Tree Problem (MSelTP) as a generalization of the Maximum Induced Tree problem. Given an undirected graph with a partition of its vertex set into clusters, MSelTP aims to choose the maximum number of vertices such that at most one vertex per cluster is selected and the graph induced by the selected vertices is a tree. To the best of our knowledge, MSelTP has not been studied before although several related optimization problems have been investigated in the literature. We propose two mixed integer programming formulations for MSelTP; one based on connectivity constraints, the other based on cycle elimination constraints. In addition, we develop two exact cutting plane procedures to solve the problem to optimality. On graphs with up to 25 clusters, up to 250 vertices, and varying densities, we conduct computational experiments to compare the results of two solution procedures with solving a compact integer programming formulation of MSelTP. Our experiments indicate that the algorithm CPAXnY outperforms the other procedures overall except for graphs with low density and large cluster size, and that the algorithm CPAX yields better results in terms of the average time of instances optimally solved and the overall average time.

We apply the concept of recoverable robustness to periodic timetabling, resulting in the Recoverable Robust Periodic Timetabling Problem (RRPT), which integrates periodic timetabling and delay management. Although the computed timetable is periodic, the model is able to take the aperiodicity of the delays into account. This is an important step in finding a good trade-off between short travel times and delay resistance. We present three equivalent formulations for this problem, differing in the way the timetabling subproblem is handled, and compare them in a first experimental study. We also show that our model yields solutions of high quality.

In this paper, we use a fixed template of slots for the online scheduling of appointments. The template is a link between planning the service capacity at a tactical level and online scheduling at an operational level. We develop a detailed heuristic for the case of drug administration appointments in outpatient chemotherapy. However, the approach can be applied to online scheduling in other application areas as well. The desired scheduling principles are incorporated into the cost coefficients of the objective function of a binary integer program for booking appointments in the template, as requests arrive. The day and time of appointments are decided simultaneously, rather than sequentially, where optimal solutions may be eliminated from the search. The service that we consider in this paper is an example to show the versatility of a fixed template online scheduling model. It requires two types of resource, one of which is exclusively assigned for the whole appointment duration, and the other is shared among multiple appointments after setting up the service. There is high heterogeneity among appointments on a day of this service. The appointments may range from fifteen minutes to more than eight hours. A fixed template gives a pattern for the scheduling of possibly required steps before the service. Instead of maximizing the fill-rate of the template, the objective of our heuristic is to have high performance in multiple indicators pertaining to various stakeholders (patients, nurses, and the clinic). By simulation, we illustrate the performance of the fixed template model for the key indicators., In this paper, we use a fixed template of slots for the online scheduling of appointments. The template is a link between planning the service capacity at a tactical level and online scheduling at an operational level. We develop a detailed heuristic for the case of drug administration appointments in outpatient chemotherapy. However, the approach can be applied to online scheduling in other application areas as well. The desired scheduling principles are incorporated into the cost coefficients of the objective function of a binary integer program for booking appointments in the template, as requests arrive. The day and time of appointments are decided simultaneously, rather than sequentially, where optimal solutions may be eliminated from the search. The service that we consider in this paper is an example to show the versatility of a fixed template online scheduling model. It requires two types of resource, one of which is exclusively assigned for the whole appointment duration, and the other is shared among multiple appointments after setting up the service. There is high heterogeneity among appointments on a day of this service. The appointments may range from fifteen minutes to more than eight hours. A fixed template gives a pattern for the scheduling of possibly required steps before the service. Instead of maximizing the fill-rate of the template, the objective of our heuristic is to have high performance in multiple indicators pertaining to various stakeholders (patients, nurses, and the clinic). By simulation, we illustrate the performance of the fixed template model for the key indicators.

Navigation systems in an Autonomous Vehicles (AV) can be divided into two parts: a path planning block which takes in the environmental data and rules to design a collision-free obstacle and a vehicle control and tracking block which generates actuator inputs for the AV to follow the reference path generated by the path planning block. Each task is fulfilled by a different algorithm with its own performance indices. These algorithms are not usually designed to get the best overall vehicle performance but the best performance of their respective blocks. A planned path that the vehicle cannot follow can therefore be generated and can lead to high tracking error and in some cases collision with obstacles. This can be solved by integrating path planning and vehicle control blocks with the dynamics of the AV. The goal of this graduation project is therefore to develop an integrated planning and vehicle control algorithm for an Autonomous Vehicles (AV). This is done by integrating a novel-Artificial Potential Fields (APF) with Model Predictive Control (MPC) to solve both path planning and vehicle control using a single optimization problem. The addition of the AV and the Obstacle Vehicle (OV) dynamics to the optimization problem as prediction models along with recursive computation can determine accurate inputs to be given to the AV. Unlike traditional APF-based path planning where the minimum potential path is generated as the result of a gradient descent method applied on the available map data and obstacle information, the APF is added as a cost to the objective function of the MPC based optimization problem to find the minimum potential path. By using a receding horizon approach for solving the final optimization problem, the potential field can be updated at each time step to avoid moving obstacles. The dynamics of the vehicle added to the optimization problem include both lateral and longitudinal dynamics and are linearized at each time step at the, Mechanical Engineering | Systems and Control

The platform carrying capacity of urban rail transit stations is limited and overcrowding of the platform will lead to serious safety risks for passengers and trains. It is significant to collaborate on the optimization of passenger flow strategy and skip-stopping scheme to alleviate traffic pressure and ensure platform safety. This study proposes and solves the joint optimization problem of coordinated flow control and skip-stopping scheme considering platform carrying capacity. Firstly, platform demand constraints and platform stranded constraints are designed according to the maximum carrying capacity of the platform to control the number of allowable arrivals ensuring platform safety. Secondly, train arrival variable and train stop variable are introduced to generate train skip-stopping index. Finally, considering the characteristics of passengers' continuous arrival and platform carrying capacity, a mixed integer programming model is established to minimize the number of passengers outside the station and the number of passengers stranded on the platform. Based on empirical data, this study takes Beijing Batong line as a case study and uses the established model to generate flow control strategy and skip-stopping schemes for each station during morning rush hours. Experimental results show that compared to the baseline without implementing the two proposed strategies, the proposed collaborative optimization method can effectively reduce the demand for staying at the platform and increase the number of boarding passengers at downstream stations. Thus, the balance between train capacity and passenger flow demand is maintained while ensuring platform safety. Moreover, the proposed method can also avoid overcrowding at downstream stations., Transport and Planning

In today's travel and tourism landscape, the role of travel agents has become increasingly complex as they are challenged to explore a variety of potential destinations. More specifically, the complicated task of planning itineraries that truly satisfy travellers puts travel agents in a crucial role, increasing the complexity of itinerary planning. This complexity is compounded not only by the multitude of possible destinations, but also by non-negotiable constraints such as cost and time. To address these challenges, the orienteering problem represents a fundamental mathematical model that provides a theoretical basis for understanding the nuanced difficulties faced by travel agents.This study ventures into a novel iteration of the orienteering problem, with a particular focus on optimizing travel satisfaction based on length of stay. A notable aspect of this variant is the inclusion of time and cost constraints in the route determination process. Using an integer programming model, the satisfaction scores for each location are described by a diminishing returns function linked to length of stay, while the costs associated with each location follow a linear function influenced by the same parameter. The application of this model is in a hypothetical scenario with 32 nodes, with the calculations facilitated by the FilMINT solver. A sensitivity analysis examines time and cost constraints and shows their decisive influence on the optimization of travel routes. The results of this research contribute significantly to a strategic framework and provide travel agencies with the opportunity to create itineraries that not only meet practical limits but, more importantly, increase traveller satisfaction.

During the COVID-19 pandemic people living close to the airport got accustomed to less flights, and therefore less noise disturbance. Now the amount of traffic is increasing again and so is the noise disturbance. For this research specifically the optimizing task of distributing of arriving aircraft over the IAF is addressed, as often the shortest transition routes from an IAF towards the runway go over densely populated areas, but flying via another IAF results in longer flying times and thus more CO2 emissions. A tool that is able to quantitatively make a trade-off between noise and emission is required to provide a basis for the distribution of aircraft over the IAF. In this research the feasibility and effects of using an expanded version of the aircraft landing problem to create the IAF Selection Optimization tool is studied, including the effects of different settings for the tool. As a case study Amsterdam Airport Schiphol is used, as it is a busy airport that lies close (11km) to the city center of Amsterdam. In this paper first the methodology of the IAF Selection Optimization tool is explained, and afterwards the working of the tool is discussed by running various scenarios for three different days from 2019 at AAS. For all scenarios an optimal and feasible solution was found by the tool, based on the input variables selected for each scenario. It could therefore be concluded that the IAF Selection Optimization tool provides a means to optimally distribute aircraft based over the IAF based on a quantitative trade-off., Aerospace Engineering

The paper proposes a generative design workflow for three major hospital layout planning steps to satisfy multiplex configurational requirements. The initial step is stacking through clustering functional spaces into floor plans, for which a spectral method is presented. Subsequently, a novel simultaneous process of zoning and routing is proposed as a Mixed-Integer Programming problem-solving task; performed on a quadrilateral mesh whose faces and edges are allocated respectively to the rooms and the corridors. The paper situates the workflow in the context of an Activity-Relations-Chart for a general hospital while demonstrating, explaining, and justifying the generated optimal floor plans. The conversion of the hospital layout problem to a Mixed-Integer Programming problem enables the use of existing Operations Research solvers, allowing for the generation of optimal solutions in a digital design environment. The comprehensive problem formulation for a real-world scenario opens a new avenue for utilization of mathematical programming/optimization in healthcare design., Design Informatics

In the literature of mining optimisation, most classical mine block sequencing or open-pit mine production scheduling problems are applied at strategic and tactical levels, because their objectives are to determine the optimal sequence of mineral blocks across a certain number of fixed time-length periods (measured in weeks, months or years) such that the total revenue is maximised. The application of continuous-time machine scheduling theory to mine equipment timetabling is challenging and rare in the current mining literature. In this study, inspired by microscopic scheduling requirements (measured in hours, minutes and seconds) in the iron ore open-pit mining industry, a new short-term Mine Excavators Timetabling (MET) problem is introduced and defined. The MET simultaneously assigns mine blocks to excavators and decides the sequencing of assigned blocks for each excavator so that the detailed scheduling of starting and completion time for excavation of each block is determined. Different from discrete periods in the classical mining optimisation problems, timing factors in the proposed MET are continuous and precise. The proposed MET aims at minimising the total weighted tardiness (delay cost) and the total weighted movement time (relocation cost) at the operational level. By analysing the key characteristics of excavating operations, the MET problem is transformed into a specific type of continuous-time machine scheduling problem, which is an innovative application to operational-level mining equipment management. Based on extensive computational experiments by mixed integer programming, a dominance-based constructive algorithm and a hybrid Tabu-Search Threshold-Accepting metaheuristic algorithm, theoretical insights and practical benefits are discussed in depth for real-world implementations. In comparison to the exact MIP solver (ILOG-CPLEX), computational experiments indicate that the proposed hybrid metaheuristic can obtain the same optimal solutions of

The energy transition is one of the major challenges of the 21st century, impacting the way energy is generated, conserved and consumed. Energy generation becomes more and more decentralised, intermittency and fluctuations suddenly are becoming topics of interest within day-to-day life and energy system operators are facing many new obstacles never encountered before. In this context, the anticipation for hydrogen as a resource for energy conservation and -management is big. This research focuses on the optimisation of the hydrogen pathway for investment and operational models. The hydrogen pathway as aforementioned is divided over three technologies: hydrogen generation with means of water electrolysis, also known as 'green hydrogen', storage in compression vessels and reconversion of hydrogen into electricity in the form of a fuel cell technology (also known as Power-to-Gas). The research focuses on identifying technical parameters and operational policies of the water electrolysis systems that can be translated into optimisation constraints, assessing the level of detail required to create an accurate optimisation model. A generic model is developed that can be scaled for further research, making different case studies and sizing possible. The research compares the performance of the models in terms of accuracy to the computational burden. The comparison is done for the level of detail and complexity added to the model. After a literature review of technical parameters and operational policies regarding the technologies, two models were created in a mathematical framework. The two models proposed were Linear Programming (LP) and a Mixed-Integer Programming (MIP) Model. On the LP model 6 different sensitivity analysis has been performed, to be precise on Capital Expenditures (CAPEX), efficiency, lifetime, ramping rates, interest rates and finally different time horizons. The outcome of these analyses is that the technology mix can best b, Electrical Engineering | Sustainable Energy Technology

As exploration in space increases through the use of larger telescopes, more sophisticated structures, and physical exploration, the use of autonomous robots will become instrumental to build and maintain the infrastructures required for this exploration. These systems must be autonomous to deal with the infeasibility of teleoperation due signal delay and task complexity. The reality of using robots in the real world without direct human input will require the autonomous systems to have the capability of responding to errors that occur in an assembly scenario on their own. As such, a system must be in place to allow for the sequencing and allocation of tasks to the robotic workforce autonomously, giving the ability to re-plan in real world stochastic environments. This work presents four contributions towards a system allowing for the autonomous sequencing and allocation of tasks for in-space assembly problems. The first contribution is the development of the Stochastic Assembly Problem Definition (SAPD) to articulate all of the features in an assembly problem that are applicable to the task sequencing and allocation. The second contribution is the formulation of a mixed integer program to solve for assembly schedules that are optimal or a quantifiable measurement from optimal. This contribution is expanded through the development of a genetic algorithm formulation to utilize the stochastic information present in the assembly problem. This formulation extends the state-of-the-art techniques in genetic algorithms to allow for the inclusion of new constraints required for the in-space assembly domain. The third contribution addresses how to estimate a robot's ability to complete a task if the robot must be assigned to a task it was previously not expected to work on. This is accomplished through the development of four metrics and analyzed through the use of screw theory kinematics. The final contribution focuses on a set of metrics to guide the selection of a good sc

Workforce scheduling is widely used within most industries. A well-outlined and efficient schedule gives cost savings, such as reduced number of overtime hours, increases overall utilization, and facilitates meeting demands. A large and complex schedule, for example, scheduling of a health care workforce, needs to consider many parameters when constructed; it is essential to account for all critical constraints regarding who can dispense a particular medicine, laws restricting the health care system, etcetera. This thesis evaluates two different methods for implementing a workforce scheduling system for one of Linköping’s most well-known restaurants and bars for students, using mixed integer programming and heuristics. Flamman Pub & Disco recruits new employees prior to every semester. Usually, the workforce consists of around 100 employees, and the vast majority of them work either in the bar or in the kitchen. Historically, the scheduling process has been handled manually using Excel. This does, however, take up much time for the operations manager, something considered frowned upon. Therefore, this thesis suggests an automated scheme for future scheduling processes. Because Flamman is a student organization, they do not hold the capital to invest in expensive licensed optimization software. However, literature studies have shown that heuristics such as large neighborhood search can generate sufficient performance, and therefore the investigation of free-of-charge software using a heuristic approach is conducted. The constructed framework uses a mixed integer programming model, which also lays the cornerstone for the two heuristics: a reverse constructive heuristic and a large neighborhood search. The results retrieved from the analysis prove that a heuristic can be a helpful tool for upcoming recruitment periods. There are, however, recommended areas for improvement regarding the current state of the heuristic.

Nonnegative matrix factorization (NMF) consists in finding two nonnegative matrices whose product is equal to (or approximates) a nonnegative data matrix. NMF is a powerful data analysis tool used to extract meaningful information when the observed data is nonnegative by nature; for example, in text mining, in hyperspectral unmixing, in audio source separation, and in many more applications. The minimum inner dimension of such a factorization is called the nonnegative rank, and computing this quantity is NP-hard in general. Nevertheless, it has several interesting applications; for example, in combinatorial optimization, the extension complexity of a polytope is equal to the nonnegative rank of its slack matrix. Other uses appear in statistics, in information theory, etc. Therefore, there has been interest in determining strong lower and upper bounds to approximate it as closely as possible. In this thesis, we introduce new lower bounds on the nonnegative rank based on some properties of geometric representations of the matrix. First, we introduce a lower bound for slack matrices of convex polytopes, based on a purely geometrical description of the polytope gathering its numbers of faces in each dimension, and on how it changes under projections. In the second part, we introduce a lower bound based on a representation of the matrix as a pair of nested polytopes. Then, we define a framework, based on a series of mixed integer formulations, in which lower bounds can be computed, and we introduce some dynamic methods to get stronger bounds. We compute these bounds on a collection of matrices and show how they can outperform other approaches from the literature., (FSA - Sciences de l'ingénieur) -- UCL, 2022

In major metropolitan areas such as Los Angeles County, ride-sharing systems can help reduce traffic congestion and increase the efficiency of the transportation system. This research project proposes three different solution approaches for solving the ride share routing problem with flexible pickup and drop-off points. The first is a dynamic programming-based route enumeration procedure that can be used to solve small-sized problems; the other two are branch and price-based heuristics for solving large problems. The researchers first provide a mixed integer nonlinear model for routing and pickup and drop-off points selection which they later decompose into a master and subproblem for solving. To validate the performance of their approaches and gather valuable insights about the ridesharing system, the researchers perform numerical experiments on a San Francisco Taxicab dataset. Results show that the approaches are efficient, solving instances with up to 300 nodes within 130 CPU seconds. For these datasets, incorporating flexible meeting points (i.e., pickup and drop-off points) can reduce the total travel time of the rideshare system by 18%. Sensitivity analysis shows that it can also decrease the time passengers wait time for rides by 43%. The methodologies in this study can help transportation planners design more efficient rideshare systems with less waiting, better passenger service, and less travel time.View the NCST Project Webpage

This research develops methods that increase the inventory of space-filling designs (SFDs) for large-scale computer-based experiments. We present a technique enabling researchers to add sequential blocks of design points effectively and efficiently to existing SFDs. We accomplish this through a quadratically constrained mixed-integer program that augments cataloged or computationally expensive designs by optimally permuting and stacking columns of an initial base design to minimize the maximum absolute pairwise correlation among columns in the new extended design. We extend many classes of SFDs to dimensions that are currently not easily obtainable. Adding new design points provides more degrees of freedom for building metamodels and assessing fit. The resulting extended designs have better correlation and space-filling properties than the original base designs and compare well with other types of SFDs created from scratch in the extended design space. In addition, through massive computer-based experimentation, we compare popular software packages for generating SFDs and provide insight into the methods and relationships among design measures of correlation and space-fillingness. These results provide experimenters with a broad understanding of SFD software packages, algorithms, and optimality criteria. Further, we provide a probability-distribution model for the maximum absolute pairwise correlation among columns in the widely used maximin Latin hypercube designs., Lieutenant Colonel, United States Marine Corps, Approved for public release. Distribution is unlimited.

This paper examines the flow synchronization problem between a manufacturing location and multiple destinations. Multiple products can be shipped from the manufacturing location to different locations via multiple transportation modes. These transportation modes may have different transportation lead times. The transportation costs structure of the different transportation modes offer economies of scale and can be represented by general piecewise linear functions. The production system at the manufacturing location is a serial process with a bottleneck stage. At the bottleneck stage, a predetermined production sequence must be maintained as is the case in some process-based industries. We propose a tight mixed integer programming model for integrated planning of production and distribution in the network. We show that by adding simple valid inequalities and special 0-1 variables, major computational improvements can be achieved when solving this problem with commercial solvers such as Cplex. We also propose a sequential solution approach, based on the independent, but synchronized, solutions of the production and distribution sub-problems. Finally, the solution methods proposed are tested experimentally for realistic problems and the advantage of integrated planning over independent but synchronized planning is assessed.

This paper examines a multi-item dynamic production-distribution planning problem between a manufacturing location and a distribution center. Transportation costs between the manufacturing location and the distribution center offer economies of scale and can be represented by general piecewise linear functions. The production system at the manufacturing location is a serial process with a multiple parallel machines bottleneck stage and divergent finishing stages. A predetermined production sequence must be maintained on the bottleneck machines. A tight mixed-integer programming model of the production process is proposed, as well as three different formulations to represent general piecewise linear functions. These formulations are then used to develop three equivalent mathematical programming models of the manufacturer-distributor flow planning problem. Valid inequalities to strengthen these formulations are proposed and the strategy of adding extra 0–1 variables to improve the branching process is examined. Tests are performed to compare the computational efficiency of these models. Finally, it is shown that by adding valid inequalities and extra 0–1 variables, major computational improvements can be achieved.

2022 International Balkan Conference on Communications and Networking, BalkanCom 2022 -- 22 August 2022 through 24 August 2022 -- 183326, This paper evaluates the effect of end-to-end delay on lifetime and the average bit error rate for wireless sensor networks where each sensor node sends its data to sink via directional antennas. Using Mixed Integer Programming, lifetime is optimized for circular network topologies with different numbers of nodes. Using both directional and omnidirectional antennas, different end-to-end delay restrictions are applied to the same sensor network to examine the effect on lifetime and average bit error rate. When delay restriction is relaxed, an increase in lifetime and a decrease in average bit error rate are observed for both antennas. In this case, the directional antenna benefits more from relaxing the delay restriction. In the end, an optimal end-to-end delay was determined which provides sufficient lifetime and bit error rate while taking into account data freshness. © 2022 IEEE.

Everyday, a majority of the people, most probably several times, use the banking applications through online applications or physical ATM (Automated Teller Machine) devices for managing their financial transactions. However, most financial institutions provide static user interfaces regardless of the needs for different customers. Saving even a few seconds for each transaction through more personalized interface design might not only result in higher efficiency, but also result in customer satisfaction and increased market share among the competitors. In ATM Graphical User Interface (GUI) design, transaction completion time is, arguably, one of the most important metrics to quantify customer satisfaction. Optimizing GUI menu structures has been pursued and many heuristic techniques for this purpose are present. However, menu optimization by employing an exact mathematical optimization framework has never been performed in the literature. We cast the ATM menu optimization problem as a Mixed Integer Programming (MIP) framework. All the parameters of the MIP framework are derived from a comprehensive actual ATM menu usage database. We also proposed two heuristic approaches to reduce the computational complexity. Our solution can be accustomed with ergonomic factors and can easily be tailored for optimization of various menu design problems. Performance evaluations of our solutions by using actual ATM data reveal the superior performance of our optimization solution.

30th Signal Processing and Communications Applications Conference, SIU 2022 -- 15 May 2022 through 18 May 2022 -- -- 182415, In this paper, the relationship between network lifetime and delay from source node to sink is analyzed for Wireless Sensor Networks. To examine the effect of delay on lifetime, different delay restrictions are applied to the same sensor network. Number of sensor nodes is increased gradually to study networks of different density. When delay restriction is relaxed, increase in lifetime is observed. In this case, the lifetime of dense networks increases more compared to sparse networks. Likewise, for a particular delay restriction limit, increasing the number of nodes results in a lifetime increase. Lifetime Increase Percentages are examined for detailed behavior of different restrictions. © 2022 IEEE.

The International Timetabling Competition 2019 (ITC 2019) posed a university timetabling problem involving assigning classes to times and rooms for an entire semester while assigning students to required classes. We propose a new mixed integer programming (MIP) formulation of the problem. The MIP formulation takes advantage of different graph structures in conflict graphs to construct a strong formulation of the constraints. In addition, we introduce a reduction algorithm that removes redundancies from the input data. We show that the reduction algorithm, combined with the graph-based MIP formulation, outperforms the MIP formulated by Holm et al. (A MIP formulation of the International Timetabling Competition 2019 problem, 2020) and thus becomes the new state-of-the-art MIP formulation for the ITC 2019. This paper reports the graph-based MIP formulation, which we used during the ITC 2019, and discusses additional approaches that one can use to strengthen the MIP.

Researchers have studied the nurse rostering problem (NRP) for multiple decades. Initially, the formulations were rather primitive including only a few necessary restrictions, but down the road, the formulations have become more complex. Nonetheless, a fraction of the research reaches implementation in practice, and many wards still schedule nurses manually. In this article, we introduce a flexible nurse rostering system that employs mathematical optimization to automatically schedule nurses to shifts. We have developed this system in collaboration with practitioners to fully match their needs. The system consists of a comprehensive mixed integer programming (MIP) model along with a flexible framework. In addition to common constraints from the literature, the mathematical formulation includes three new constraints that further encourage healthy work schedules for each nurse. Additionally, we have reformulated some common constraints from the literature and allow for a complex shift struc-ture that matches the needs of real hospital wards. This flexibility results in increased adaptability for different wards with different needs and is crucial to address the complex nurse rostering problem that practitioners face. We have successfully implemented this system in two wards at two Danish hospitals. We present the MIP model along with computational results for 12 real-world rostering instances. Furthermore, we discuss the practical impact of this system and provide general feedback from the practitioners using it. Overall, the results illustrate the capabilities of the system to tackle diverse nurse rostering instances and produce outstanding results.

In this paper, we use a fixed template of slots for the online scheduling of appointments. The template is a link between planning the service capacity at a tactical level and online scheduling at an operational level. We develop a detailed heuristic for the case of drug administration appointments in outpatient chemotherapy. However, the approach can be applied to online scheduling in other application areas as well. The desired scheduling principles are incorporated into the cost coefficients of the objective function of a binary integer program for booking appointments in the template, as requests arrive. The day and time of appointments are decided simultaneously, rather than sequentially, where optimal solutions may be eliminated from the search. The service that we consider in this paper is an example to show the versatility of a fixed template online scheduling model. It requires two types of resource, one of which is exclusively assigned for the whole appointment duration, and the other is shared among multiple appointments after setting up the service. There is high heterogeneity among appointments on a day of this service. The appointments may range from fifteen minutes to more than eight hours. A fixed template gives a pattern for the scheduling of possibly required steps before the service. Instead of maximizing the fill-rate of the template, the objective of our heuristic is to have high performance in multiple indicators pertaining to various stakeholders (patients, nurses, and the clinic). By simulation, we illustrate the performance of the fixed template model for the key indicators.

When delays in trains occur, train schedules are rescheduled to reduce the impact. Despite many existing studies of automated train rescheduling, this study focuses on automated rescheduling considering a moving block and Automatic Train Operation (ATO). This study enables such automated rescheduling by formalizing this problem as a mixed integer programming (MIP) model. In previous work, the formulation was achieved for unidirectional single-track railway lines. In this paper, we aim to achieve the formulation for bidirectional double-track lines. Specifically, we propose a formulation of constraints about trains’ running terminal stations. To evaluate our automated rescheduling approach, we implemented an MIP model consisting of a combination of the new constraints with the previous MIP model. We demonstrated the feasibility of our approach by applying it to a bidirectional double-track line with eight delay scenarios. We also evaluate the delay reduction and computation overhead of our approach by comparing it with a baseline with these eight scenarios. The results show that the total delay of all trains from our approach reduced from 20% to 30% than one from the baseline. On the other hand, the computation time increased from less than 1 second to a minimum of about 20 seconds and a maximum of about 1600 seconds.

Software defined networks (SDNs) define a programmable network fabric that can be reconfigured to respect global networks properties. Securing against adversaries who try to exploit the network is an objective that conflicts with providing functionality. This paper proposes a two-stage mixed-integer programming framework. The first stage automates routing decisions for the flows to be carried by the network while maximizing readability and ease of use for network engineers. The second stage is meant to quickly respond to security breaches to automatically decide on network counter-measures to block the detected adversary. Both stages are computationally challenging and the security stage leverages large neighborhood search to quickly deliver effective response strategies. The approach is evaluated on synthetic networks of various sizes and shown to be effective for both its functional and security objectives.

The development of autonomous robotic systems is a key component in the expansion of space exploration and the development of infrastructures for in-space applications. An important capability for these robotic systems is the ability to maintain and repair structures in the absence of human input by autonomously generating valid task sequences and task to robot allocations. To this end, a novel stochastic problem formulation paired with a mixed integer programming assembly schedule generator has been developed to articulate the elements, constraints, and state of an assembly project and solve for an optimal assembly schedule. The developed formulations were tested with a set of hardware experiments that included generating an optimal schedule for an assembly and rescheduling during an assembly to plan a repair. This formulation and validation work provides a path forward for future research in the development of an autonomous system capable of building and maintaining in-space infrastructures.

The International Timetabling Competition 2019 (ITC 2019) considers a university course timetabling problem where semester events must be assigned a time and a room while students must be enrolled in classes according to their course registration. Holm et al. (2022) show a graph-based Mixed Integer Programming (MIP) formulation of the ITC 2019 problem. The MIP model uses various graph structures to givea strong formulation. However, the MIP model is still hard to solve for many of the 30 ITC 2019 instances. To generate high-quality solutions, Mikkelsen and Holm (2022) use a parallelized fix-and-optimize matheuristic based on the graph-based MIP model. The matheuristic found the best solutions to 29 of 30 ITC 2019 instances during the competition and was the winning algorithm. Even though the algorithm won the competition superiorly, only five instances are solved to optimality. This technical report aims to research the possibilities of having an exact method for solving the ITC 2019 instances. We do this by investigating the Linear Programming (LP) relaxation of the graph-based MIP model and introducing groups of constraints that might be beneficial to use as cuts. This report will focus on solving the LP relaxation with an iterative cutting plane algorithm. The search for a usable cutting plane algorithm provides two new lower bounds on the ITC 2019 instances.

Logistics has gained great attentions with the prosperous development of e-commerce, which is often seen as the classic optimal vehicle routing problem. Meanwhile, electric vehicle (EV) has been widely used in logistic fleet to curb the emission of green house gases in recent years. Thus, solving the optimization problem of joint routing and charging of multiple EVs is in a urgent need, whose objective function includes charging time, charging cost, EVs travel time, usage fees of EV and revenue from serving customers. This joint problem is formulated as a mixed integer programming (MIP) problem, which, however, is NP-hard due to integer restrictions and bilinear terms from the coupling between routing and charging decisions. The main contribution of this paper lies at proposing an efficient two-stage algorithm that can decompose the original MIP problem into two linear programming (LP) problems, by exploiting the exactness of LP relaxation and eliminating the coupled term. This algorithm can achieve a near-optimal solution in polynomial time. In addition, another variant algorithm is proposed based on the two-stage one, to further improve the quality of solution. Compared with the state-of-the-art algorithm, extensive simulations are implemented to validate the effectiveness of the proposed algorithm.