To save content items to your account,
please confirm that you agree to abide by our usage policies.
If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account.
Find out more about saving content to .
To save content items to your Kindle, first ensure no-reply@cambridge.org
is added to your Approved Personal Document E-mail List under your Personal Document Settings
on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part
of your Kindle email address below.
Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations.
‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi.
‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
Shie Mannor, Technion - Israel Institute of Technology, Haifa,Yishay Mansour, Tel-Aviv University,Aviv Tamar, Technion - Israel Institute of Technology, Haifa
This chapter presents an alternative optimization-based approach to solving MDPs through linear programming (LP) formulations. The chapter develops LP formulations for both finite-horizon and discounted infinite-horizon MDPs. The key innovation is representing policies through occupancy measures. The primal LP maximizes return subject to flow constraints, while the dual LP has an elegant interpretation in terms of value functions. The LP approach offers theoretical insights through duality.
Linear programming is an important class of convex problems with constraints, where the objective function is linear, and the problem is almost entirely determined by the linear inequality constraints. Most real-world problems involve constrained resources, such as time, space, money, materials, and labor. There are real tradeoffs in solving such problems, which we express as inequality constraints. Some of the many applications include: resource allocation, workforce scheduling, factory layout, space usage, production scheduling, inventory management, crop planning and irrigation, portfolio optimization, supply chain logistics, fleet routing, and healthcare resource and staff allocation. These examples are all characterized by a relatively simple objective function that is linearly related (e.g., profit or cost), and constrained resources. There is no closed-form solution to a general linear program. However, there are accurate and efficient algorithms that scale to large problems. In this chapter, we define the mathematical ingredients of a linear program, provide examples to illustrate several applications, and discuss solution techniques and extensions.
This chapter provides an introduction to key concepts in optimization with motivating applications. We begin with a categorization of different optimization problems, based on the objective function, to be maximized or minimized, and constraint equations that limit the set of feasible solutions. Next we introduce two major concepts in optimization: convexity and the gradient. Convex problems are essentially solved, at least numerically. Linear programming and quadratic programming are both convex. Nonconvex problems are more challenging. However, there is a shift in optimization, where it is increasingly possible to solve nonconvex problems. The gradient is another fundamental concept, providing information about the geometry of the optimization landscape, and which direction locally improves the solution. We then show how Lagrange multipliers are an intuitive way of handling constraints. We conclude with three major applications: inverse problems, control theory, and machine learning. Throughout, we give examples to illustrate how to formulate an optimization problem and solve it algorithmically.
India’s Supplementary Nutrition Programme (SNP), under the Integrated Child Development Services, provides a Morning Snack and a Hot Cooked Meal to children aged 36–72 months through Anganwadis (day-care centres). This study assessed these meals against SNP standards (2012) and age-specific ICMR recommendations, when standards were unavailable, and explored the use of linear programming (LP) to improve nutrient quality of SNP meals. A cross-sectional survey documented the SNP-meals, ingredients, serving portions and other details, using questionnaires administered to Anganwadi workers and programme officials from purposively selected Anganwadis across 27 States and Union Territories. Nutrient composition was estimated using standard food composition tables, and State-specific food lists and retail prices were incorporated into the LP framework to identify foods that could improve nutrient content of SNP meals. Energy standards were met in 56% of States, while 22% fell more than 20% below recommendations. Protein standards were achieved in 74% of States; however, declined to 52% after adjusting for digestibility. Only 22% of States met the ICMR-based fat requirement. Zinc, iron and folate were largely met, whereas calcium and vitamins A, B6 and B12 were below recommendations in more than half the States. Meals were predominantly cereal-based with limited inclusion of nutrient-dense foods. LP identified foods that reduced nutrient gaps, although many improvements exceeded the per-child cost allocation. Overall, meals showed wide variability, with persistent gaps in fat and key micronutrients. LP provides a structured approach to enhance nutrient provision within the programme setting, although meeting all nutrient targets may require adjustments to cost and procurement strategies.
To optimise school food baskets in Ghana to meet newly proposed food and nutrition targets while considering cultural acceptability and cost.
Design:
This was a modelling study. Data on existing school meal menus were collected from various regions to provide baseline inputs. Linear programming (LP) was used to model school meal baskets that satisfied minimum nutrient and food targets for school meals while meeting cost and acceptability constraints. Five LP models were tested, each varying in budget constraints and acceptability/food-based parameters.
Setting:
Ghana.
Participants:
NA.
Results:
Baseline school food baskets were significantly deficient in energy, protein, Fe, Zn, vitamin A, folate, vitamin B12 and vitamin C compared to food and nutrient standards for school meals in Ghana. Optimisation resulted in school food baskets that met cost, nutrient and food-based/acceptability targets but with substantial deviations from baseline. Achieving nutritional adequacy within cost limits increased reliance on animal-source foods and led to higher environmental impacts, indicating trade-offs between nutrition, affordability and environmental sustainability.
Conclusion:
The study underscores LP’s potential for enhancing school meals in Ghana but highlights the need for increased financial investment for reaching dietary goals. Addressing local realities and cultural preferences is essential for implementing effective, sustainable school meal strategies and improving child health.
This chapter is concerned with the constrained optimization problem which plays an important role in ML as many ML algorithms are essentially to maximize or minimize a given objective funcion with either equality or inequality constraints. Such kind of constrained optimization problems can be reformulated in terms of the Lagrangian function including an extra tern for the constraints weighted by their Lagrange multipliers as well as the original function. The chapter also consider the important duality principle based on which the constrained optimization problem can be addressed as either the primal (original) problem, or the dual problem, which is equivalent to the primal if a set of KKT conditions are satisfied, in the sense that the solution of the dual is the same as that for the primal. The chapter further considers two methods, linear and quadratic programming, of which the latter is the foundation for support vector machine (SVM), an important classification algorithm to be considered in a later chapter.
According to the principles of the European Pillar of Social Rights, everyone should be entitled to an adequate minimum income sufficient for a healthy diet. Studies show that food insecurity remains a concern in Europe, highlighting the need to determine budgets for adequate nutrition, known as Food Reference Budgets. Previous approaches, based on expert-designed food baskets or focus group discussions, are often limited by their normative nature and/or low representativeness.
Design:
To address these problems, this study explores Linear Programming as a novel method to calculate Food Reference Budgets for twenty-six EU member states. To analyse if Linear Programming could be an adequate tool to calculate future Food Reference Budgets, this method was used to design country-specific food baskets that align with consumption habits and healthy diet requirements. The food baskets were then priced at different levels to determine the cost for healthy diets in twenty-six European countries.
Setting:
Germany.
Participants:
The calculations are based on consumption data from the EU Household Budget Survey (EU-HBS) from 2015 (2010 for Malta, Portugal and Slovenia). For Germany, data from the national income and consumption survey was used instead, as German data was not included in the EU-HBS.
Results:
The results show a positive correlation between optimised healthy and current observed diets for most food groups, indicating that country-specific preferences are reflected in the optimised healthy food baskets. Nevertheless, to meet healthy diet requirements, consumption of vegetables, fruit, fish and dairy must increase compared with the current observed diets. At a lower price level, the Food Reference Budgets ranged from 2·38 to 5·71 €/day, depending on the country. With a low-price level (20th percentile), costs for healthy diet accounted for between 5·74 % of income in Luxembourg and 29·00 % in Romania, showing the large differences in affordability between countries.
Conclusion:
Overall, it was concluded that Linear Programming could be a promising approach for determining uniform and comparable European Food Reference Budgets and should be discussed in the context of the EU Commission’s efforts to modernise the European minimum income schemes.
This chapter presents mathematical programming as the science of one-shot decisions. It clarifies important ways analytics scientists implement problem solving by benefiting from tools and ideas in mathematical programming both in scenarios where the world behaves linearly and where it does not. It also introduces integer programming and inverse optimization, showcasing how the main ideas and insights obtained from mathematical programming have been applied to various impactful problems ranging from designing effective diets to allowing the military to improve the efficiency of its operations to make bike sharing systems more accessible.
Beginning with linear programming and ending with neural network training, this chapter features seven applications of the divide-and-concur approach to solving problems with RRR.
Pregnant women are at higher risk of vitamin D deficiency due to increased nutritional requirements and limited dietary sources. Fish is the major source of vitamin D, but its availability varies by region. This study aims to assess the availability of vitamin D-rich fish and develop food-based recommendations (FBR) for pregnant women in East Lombok, Indonesia. This comparative cross-sectional study was conducted in East Lombok, Indonesia, which is part of Action Against Stunting cohort of pregnant women. Twenty-five village markets in the area were scored based on availability of vitamin D-rich fish and number of fish sellers in each market and were categorised into high availability (HD) for the highest quartile and low availability (LD) for the lowest quartile. Quantum Geographic Information System software was used to identify each of respondents’ houses using 2·4 km buffer zones to either HD or LD markets. Dietary intake data were collected from 24-h dietary recalls and linear programming analysis using Optifood was used to identify problem nutrient and dietary inadequacy. No significant difference in vitamin D intake was found between HD and LD areas (P = 0·633). While both groups’ FBR ensure adequacy of Fe, Zn, vitamins A, B1, B2, B3, B6 and B12, Ca remain as dietary inadequacy in the LD group, suggesting that availability play a role in ensuring dietary adequacy. Future studies to develop nutrient-dense foods and improved fish availability mapping which consider non-static position of market (mobile vendor) are recommended.
Get up-to-speed with the fundamentals of how electricity markets are structured and operated with this comprehensive textbook, presenting coverage of key topics in electricity market design, including power system and power market operations, transmission, unit commitment, demand response, and risk management. It includes over 140 practical examples, inspired by real-industry applications, connecting key theoretical concepts to practical scenarios in electricity market design, and features over 100 coding-based examples and exercises, with selected solutions for readers. It further demonstrates how mathematical programming models are implemented in an industry setting. Requiring no experience in power systems or energy economics, this is the ideal introduction to electricity markets for senior undergraduate and graduate students in electrical engineering, economics, and operations research, and a robust introduction to the field for professionals in utilities, energy policy, and energy regulation. Accompanied online by datasets, AMPL code, supporting videos, and full solutions and lecture slides for instructors.
This paper proposes a multi-objective programming method for determining samples of examinees needed for estimating the parameters of a group of items. In the numerical experiments, optimum samples are compared to uniformly and normally distributed samples. The results show that the samples usually recommended in the literature are well suited for estimating the difficulty parameters. Furthermore, they are also adequate for estimating the discrimination parameters in the three-parameter model, but not for the guessing parameters.
An algorithmic approach to test design, using information functions, is presented. The approach uses a special branch of linear programming, i.e. binary programming. In addition, results of some benchmark problems are presented. Within the same framework, it is also possible to formulate the problem of individualized testing.
A maximin model for IRT-based test design is proposed. In the model only the relative shape of the target test information function is specified. It serves as a constraint subject to which a linear programming algorithm maximizes the information in the test. In the practice of test construction, several demands as linear constraints in the model. A worked example of a text construction problem with practical constraints is presented. The paper concludes with a discussion of some alternative models of test construction.
The 1940s saw the reconciliation of mathematical wartime techniques with social scientific theorizing. This chapter examines how the economy was depicted as a huge optimization problem that would soon be solvable by electronic computers. Investigating input–output analysis as it was done at the Harvard Economic Research Project (HERP) under the directorship of Wassily Leontief illustrates the difficulties of making an economic abstraction work in measurement practice. Chapter 3 draws a trajectory to the Conference of Activity Analysis of 1949, where mathematical economists combined techniques of linear programming with what they saw as conventional economics. The move from planning tools to devices for theoretical speculation came along with a shift in modeling philosophies and notions of realism. Focusing entirely on mathematical formalisms and abandoning the concern with measurement brought about the main research object of the economics profession in the subsequent years: The economy as a flexible and efficient system of production in the form of a system of simultaneous equations. This was the economy that provided the primary point of reference for Solow’s model.
A numerical method is proposed for a class of one-dimensional stochastic control problems with unbounded state space. This method solves an infinite-dimensional linear program, equivalent to the original formulation based on a stochastic differential equation, using a finite element approximation. The discretization scheme itself and the necessary assumptions are discussed, and a convergence argument for the method is presented. Its performance is illustrated by examples featuring long-term average and infinite horizon discounted costs, and additional optimization constraints.
Deals with reservoir operation, including rule curves, methods of mathematical programming, optimization of reservoir operations, simulation models, reservoir operation modeling with HEC-ResSim, mass curves, and reservoir siltation.
The approximate maximum and minimum amounts of any phase in a complex mineral mixture can be determined by solving a linear programming problem involving chemical mass balance and X-ray powder diffraction (XRD) data. The chemical information necessary is the bulk composition of the mixture and an estimation of the compositional range of each of the minerals in the mixture. Stoichiometric constraints for the minerals may be used to reduce their compositional variation. If only a partial chemical analysis for the mixture is available, the maximum amounts of the phases may still be estimated; however, some or all of the stoichiometric constraints may not apply. XRD measurements (scaled using an internal standard) may be incorporated into the linear programming problem using concentration-intensity relations between pairs of minerals. Each XRD constraint added to the linear programming problem, in general, reduces the difference between the calculated maximum and minimum amounts of each phase. Because it is necessary to define weights in the objective function of the linear programming problem, the proposed method must be considered a model. For many mixtures, however, the solution is relatively insensitive to the objective function weights.
An example consisting of a mixture of montmorillonite, plagioclase feldspar, quartz, and opal-cristobalite illustrates the linear programming approach. Chemical information alone was used to estimate the mineral abundances. Because quartz and opal-cristobalite are not chemically distinct, it was only possible to determine the sum, quartz + opal-cristobalite, present in the mixture.
The \textit{diameter} of a graph $G$, denoted $\diam G$, is the maximum distance between any two vertices in the graph. The \textit{diameter} of polyhedra is defined as the diameter of their graphs. While the chapter focusses on polytopes, polyhedra also feature in it.There is a connection between diameters of polyhedra and linear programming, and this is partially materialised through the \defn{Hirsch conjectures}, conjectures that relate the diameter of a polyhedra with its dimension and number of facets. We first show that the unbounded and monotonic versions of these conjectures are false (Section 7.2). Early on, Klee and Walkup (1967) realised that problems on the diameter of polyhedra can be reduced to problems on the diameter of simple polyhedra; this and other reductions are the focus of Section 7.3. We also present the counterexample of Santos (2012) for the bounded Hirsch conjecture. We then move to examine lower and upper bounds for the diameter of general polytopes and the diameter of specific polytopes. The final section is devoted to generalisations of polyhedra where diameters may be easier to compute or estimate.
We give a new proof of rationality of stable commutator length (scl) of certain elements in surface groups: those represented by curves that do not fill the surface. Such elements always admit extremal surfaces for scl. These results also hold more generally for non-filling $1$–chains.