Applied Computing and Informatics

Mohan D., Ghosh D.

In automated machining centers, a job is processed by having multiple cutting tools work on it in a pre-determined sequence. The total time to process such jobs is the sum of the machining time required by the cutting tools, and the non-machining time, required for other activities. The machining time on the job is fixed, and so such machining centers can be made more effective by reducing non-machining times. A significant portion of the non-machining time in machining centers is due to indexing, which is the operation by which tools kept in slots in tool changers are brought to the location from which the tool arm can pick them up and replace them after use. Tool changers can be visualized as disks with slots along their circumference in which tools are kept. Optimal positioning of tools in the slots can significantly speed up non-machining time. This optimization problem, called the tool indexing problem, is studied in this chapter. Specifically, a version of the problem in which only one copy of a tool can be present in the tool changer is studied here. The tool indexing problem is computationally difficult, and the chapter presents local search and tabu search algorithms to obtain good quality solutions to the problem. Two innovative bookkeeping techniques that were used to reduce the search time by two orders of magnitude have been proposed here. Computational results on benchmark tool indexing instances show that the algorithms proposed here are competitive when compared with the state-of-the-art heuristic algorithms for this problem. It is shown that some of the algorithms proposed here are both faster and generate better quality solutions for many of the benchmark instances.

Mohd Mujahid Khan, Vipin B.

The chapter introduces supply chain contracts involving nonlinear optimization in the stochastic demand setting. A literature review on prospect theory in supply chain context and theoretical results on the traditional supply chain are provided. This chapter analyzes the performance of a supply chain that includes a behavioral retailer in the context of a revenue-sharing contract using a decision-theoretic framework. We investigate the framework of prospect theory with a nonlinear stochastic reference point to model the retailer’s behavior. We derive the optimal behavioral retailer option under the revenue-sharing contract. The analysis demonstrates that the behavioral supply chain’s revenue-sharing contract can coordinate the supply chain. The chapter concludes with managerial implications and future research initiatives.

Baiou M., Barahona F., Goncalves J.

Subgradient methods have a long history of applications in Optimization. They are known for producing fast approximate solutions in cases where more exact methods are prohibitive to use. The Volume algorithm (VA) is a subgradient method, it was developed to deal with large-scale linear programs that were too difficult for traditional algorithms. Its main advantage is that it produces approximate primal solutions as well as dual solutions. It has also shown fast convergence in practice. Here we review this method and present experiments in three different areas, which demonstrate its good performance and wide applicability. First we deal with training neural networks. We show that replacing the widely used Stochastic Gradient Descent method with the VA leads to very good results. Then we study bus routing in a medium size city. Here we tackle a linear programming relaxation that is too large to be treated with traditional linear programming algorithms. Here the VA gives tight lower bounds, and the approximate primal solution is used as the starting point for several heuristics that produce the final routing. Finally we turn our attention to the p-median problem for restructuring semistructured data. We apply the VA to the linear programming relaxation, and we decompose it in a simple way so it can be treated in parallel. We use a parallel implementation combined with a heuristic. This heuristic starts with the approximate primal solution and derives an integer solution. We show experiments with large instances coming from semistructured databases. For the majority of these cases the gap from optimality was less than 1%.

Bacci T., Frangioni A., Gentile C.

Exactly solving hard optimization problems, in particular those mixing both nonlinear components and combinatorial ones, crucially requires the ability to derive tight bounds on the optimal value, which are obtained via relaxations. A fundamental trade-off exists between the tightness of the bound, which is important to avoid the explosion of the number of nodes in branch-and-bound (B&B) approaches and better drive the heuristics and the branching decisions, and the cost of the solution of the continuous relaxation. This is in particular true because “strong” relaxations (providing tight bounds) are also very often “large” ones, i.e., with a very large—often exponential—number of variables and/or constraints. Navigating this trade-off is crucial to develop overall efficient solution algorithms, especially since apparently minor aspects may have a disproportionate large impacts depending on the fine details of the computational environment in which the algorithm is implemented. This chapter provides an extensive illustration of this process using as test bed the Unit Commitment problem in electrical power production. In particular we will review several Mixed-Integer NonLinear formulations of (some of the most common variants of) the problem, with different trade-offs between size and “tightness”, as well as algorithms for the efficient solutions of single-unit versions of the problem that motivate Lagrangian approaches. We will then compare the different variants, mostly in terms of their running time versus the quality of the provided bound, in the context of a state-of-the-art software implementation, highlighting the several nontrivial choices that have to be navigated in order to choose the best approach for each given application.

Yadav A., Chakroborty P.

Most optimization problems one encounters in reference books such as this can be, and are generally, formulated as mathematical programming (MP) problems. For some problems, the modeling requires deep insights into mathematical programming techniques or the way the variables of the problems interact with one another. Such exercises, however, involved at the end, yield mathematical programming formulations that have well defined methods for their solution. These solution methods may themselves be complex and require a good understanding of calculus as well as numerical techniques. Often these methods are computationally expensive and in itself requires go-around tools. However, there are some optimization problems that arise in engineering that cannot be formulated as mathematical programming problems. Often these require external procedure-based declarations to evaluate the system performances or define interactions between various subparts of the problem. Such problems are often solved using optimization metaheuristics like genetic algorithms that are structurally quite versatile and typically require information on only system performance to drive the optimization process. In this chapter the simple everyday problem of efficient urban mobility is introduced as an example that poses unique difficulties when modeled as an optimization problem. The question that is sought to be answered is whether a combination of one-way and two-way roads can be obtained such that an urban area provides the least travel time to its users. This chapter presents a formulation as well as a genetic algorithm-based solution methodology for the problem.

Baytur B., Özceylan E., Koç Ç., Erdoğan G.

This chapter focuses on the distribution plan of a large-scale distributor of care and cleaning products to its customers located in the eastern and south eastern regions of Turkey. The distribution network consists of three depots and 502 customers. The vehicle fleet consists of homogeneous vehicles. The problem is to determine which depot should serve which customers including the routing decisions, which is an instance of the well-known Multi-Depot Vehicle Routing Problem (MDVRP). The authors use a cluster-first, route-second approach to solve the model. To do so, we first use the capacitated p-median formulation for clustering and assignment of customers to each depot. Next, we use a single-depot VRP to solve the routing problem for each depot and its cluster of customers. For this, a Guided Local Search metaheuristic is implemented and Google-OR-Tool is utilized as a solver. Real data of the company including demands, vehicle capacities, exact coordinates of depots and customers is utilized. Detailed computational experiments and their results are presented.

Kumar Vatsa A., Chandra S.

Mixed-integer nonlinear programming problems (MINLPs) are frequently observed in the real world. These problems generally require more computational effort than their counterpart mixed-integer linear programming problems (MILPs). The solvers and solution technique improvements in the last few decades have enabled us to solve MINLPs of practical sizes. This chapter presents various techniques that can be used to solve MINLPs. We divide this chapter into approximation algorithms and exact algorithms. We discuss two approximation algorithms in detail: piece-wise linearization and linearization based on the McCormick envelope. These methods can be used to obtain feasible solutions with a guarantee on bound on a wide variety of problems, including non-convex problems, which are notoriously difficult to solve with an exact method. Next, we present the exact solution methods, which are guaranteed to give an optimal solution if the algorithms are allowed to run indefinitely. These methods, such as outer approximation and generalized Benders decomposition can be applied to problems where relaxation of integrality constraint makes the problem a convex optimization problem. Some non-convex problems can be convexified using the transformation of non-convex functions. These transformations might be computationally expensive but ensure an exact solution as a trade-off. With toy examples, we demonstrate the use of exact and approximation methods on MINLPs. We also provide a real-world case study for the location-allocation of shared wastewater treatment plants and show how different methods can be used to solve that problem.

Bhatnagar A., Bolia N.B.

This chapter studies the facility location problem and demonstrates its application through a real-life case of school consolidation. India has a large number of schools primarily established under the Sarva Shiksha Abhiyan, a flagship programme of the Government of India to promote accessibility. A large number of schools (including many small size schools) have been established to enhance accessibility, but it is difficult to provide good teaching and infrastructural resources in all schools. In recent years, the focus has shifted toward improving the quality of education delivery. Hence, there is a need to merge small schools to have better facilities at the expense of accessibility. However, accessibility cannot be compromised as it may create issues related to safe commutes to school and eventually lead to dropouts in some cases. Dropouts would violate the government's aim of universalization of education. The process of merging small schools and assigning students to new (alternate) schools is known as school consolidation. The school consolidation problem is formulated as an integer linear program to minimize the number of schools in operation and the total student disruption considering the accessibility and capacity requirements. Thus, the problem has multiple objectives and is solved using lexicographic ordering in two stages along with the ε-constraint method. The models have been demonstrated in a case study of Belgaum district in Karnataka, India. The number of schools closed and the average additional travel distance varies with the spatial distribution of schools and their enrollment. The results indicate an average additional travel between 200 and 700 m in the first stage of the model and 150 m to 350 m in the second stage of the model for different blocks in the district.

Jayaswal S., Sinha A.

Bilevel optimization is a difficult class of optimization problems, which contains an inner optimization problem as a constraint in an outer optimization problem. Such optimization problems are commonly referred to as Stackelberg games in the area of game theory, where a hierarchical interaction between a leader and a follower is modeled. This chapter presents several examples of bilevel optimization problems arising in various contexts, e.g., the product line selection problem and the shortest-path interdiction problem. Depending on the context of the problem, the leader and the follower may have the same objective function but with conflicting objectives (max-min in the shortest-path interdiction), or may have different objective functions (as in the product line selection problem). Under this hierarchical setting, the leader tries to optimize their own decision by taking into account the rational response of the follower. Bilevel optimization problems are NP-hard even in the simplest case in which the problems of the leader and the follower are both linear programs. This chapter discusses classical solution approaches that are based on the reformulation of the bilevel problem into a single-level problem. It also discusses several alternate single-level reformulations for the application problems considered in this chapter.

Smith J.C., Curry R.M.

We provide a tutorial treatment of basic techniques for modeling scheduling optimization problems as mixed-integer linear programs, presented for readers having at least a limited background in linear programming formulations and algorithms for solving mathematical optimization problems. Although the scope of scheduling applications is far too broad to cover with a single chapter, many scheduling formulations employ a common set of modeling strategies that can be directly used, modified, or combined to formulate novel scheduling problems. We briefly cover these fundamental scheduling principles and illustrate how they can be adapted to model several modern applications arising in the field of scheduling optimization. These applications include optimizing radar pulse interleaving, identifying schedules that are robust to changes in data, and scheduling path flows in a dynamic flow optimization problem.

Elyasi M., Khameneh R.T., Ekici A., Özener O.Ö.

In medical treatments, patients may need a particular blood product to continue their treatment process. The only source for all blood products is blood donation. In order to extract any product from donated blood, there is a specific time limit after donation occurs. One of the blood products is platelet, which is a vital element in cancer therapies, organ transplant procedures, and different surgical operations. Platelet production is the most time-sensitive process among all other blood products. Donated blood should be processed in blood processing centers within six hours after donation; otherwise, the donated blood will not be appropriate for platelet production. Therefore, blood collection vehicles should pick up and carry the donated blood into the blood processing center in a proper period to save blood products from perishing. Because of the perishability of donated blood and the accumulative nature of blood donation, the scheduling of blood collection vehicles to collect the maximum number of blood units for platelet production is a complicated routing problem. In this study, two metaheuristic methods, namely the hybrid flower pollination algorithm (HFPA) and simulated annealing (SA), are implemented to solve a variant of the maximum blood collection problem (MBCP). The effectiveness of the proposed algorithms through exhaustive computational studies is investigated. The proposed algorithms show an average improvement of around 4% and 6% in the objective function value over the benchmark algorithm.

Dutta J.

This is a survey on linear programming. However, this is not a survey of a single approach to linear programming, but rather of two distinct approaches: the simplex method and interior point methods based on the log-barrier technique. These two topics are in fact extremely vast, and a survey such as this can only provide a glimpse of the huge edifice known as linear programming. Our approach here is unconventional since instead of viewing linear programming as a stand-alone subject, we examine it through the lens of convex programming. This allows us additional insights that are not part of the traditional discourse of linear programming. The approach to the simplex method given in this survey is credited to Manfred Padberg. The freshness of his approach is that it is tableau-free and has a non-linear programming flavor of using a rank-one update of a basic feasible matrix if it is not optimal. We also provide a very simple proof of the strong duality theorem for linear programming due to J. E. Martinez-Legaz. In this chapter we have an extensive discussion on the KKT conditions for linear programming problems with detailed proofs. The convex programming approach will be readily apparent in the discussion of the interior point methods. The chapter also contains the author’s personal experience of learning linear programming, beginning with an aversion to the tableau approach and progressing to a profound appreciation for the Padberg and interior point methods.

Hamid F.

There exist numerous textbooks on optimization techniques; however, the objective of this book is to establish a connection between the theoretical underpinnings of optimization techniques and their pragmatic application in complex real-world scenarios. Therefore, it is neither a book that overly emphasizes abstract mathematical theory nor a textbook illustrating how to solve small mathematical programming problems manually. Rather, it strives to equip readers with the understanding and skills necessary to model and solve practical mathematical programming problems. The chapters combine modeling with an introduction to state-of-the-art optimization techniques to solve a real-life problem. The book imparts an understanding of how theory and practice converge when confronted with the choice of an appropriate algorithm, and the question of how to improve a formulation, or how to use a commercial mixed-integer programming solver effectively. It serves as a comprehensive guide that navigates the intricate interplay between theoretical foundations and real-world applications in the realm of optimization.

Patil A., Sohoni M.G.

Over the past several decades, the airline industry has widely used sophisticated large-scale optimization models and algorithms to improve operational efficiency, increase revenue, and improve profitability. This chapter discusses one such large-scale optimization technique called Delayed Column Generation. The approach is commonly used to solve instances of several challenging optimization models involving strategic business and operational processes. For example, the classical aircraft rotation set partitioning optimization model is routinely solved using delayed column generation. This chapter delves into the details of the delayed column generation and branch-and-price computational procedures. To illustrate their applicability in real-world airline models, we describe a simple application to the aircraft rotation model. Additionally, we provide a few references to articles describing other applications in the airline industry.

Balakrishnan A., Mirchandani P.

Since personnel and equipment costs constitute a large portion of the operating expenses for most organizations, judiciously using these resources to perform the organization’s activities is important to ensure cost-effective operations. This paper addresses a class of resource management problems that entail assigning resources to perform a given set of ordered tasks while meeting policies and restrictions governing the deployment of these resources. We consider two particular kinds of restrictions, called span limits and work content restrictions, that specify upper and lower limits on pairwise and cumulative metrics based on the tasks assigned to each resource. We refer to this problem as the Resource Assignment with Deployment Restrictions (RADR) problem. We discuss several alternative ways to model the problem as a network-based integer program, and contrast these models in terms of the tightness of their linear programming relaxations and model size. This discussion serves to highlight the benefits of developing extended formulations and embedding constraints within the network representation, underscoring the importance of using strong formulations to effectively solve integer programs such as the RADR problems. We also outline three additional strategies—problem reduction, tightening the model with valid inequalities and coefficient lifting, and optimization-based heuristics—to further accelerate solution procedures for the RADR problem. Results from a prior study confirm the computational benefits of incorporating these strategies jointly in the solution method.