Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Dynamic Programming

347 missions · 248 completed

Missions

Open99Completed248All347
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Efficient Algorithms for Scheduling Semiconductor Burn-In Operations 2: Dynamic Program DP2 Finds a Minimum-Makespan On-Time Batch Schedule When Processing Times and Due Dates Are AgreeableResearch Paper

In semiconductor manufacturing, finished chips go through burn-in: they are loaded on boards and held in an oven at high temperature to expose early failures. An oven holds a bounded number of boards, a load cannot be interrupted once started, and a chip may stay in the oven longer than its specified burn-in time but not shorter. Lee, Uzsoy and Martin-Vega (…

7 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

A Functional Equation and Its Application to Resource Allocation and Sequencing Problems 3: The Minimum Weighted Number of Tardy Jobs Is Σ p_j Minus the Value f(n, d_n) of Equation (3)Research Paper

Minimizing the weighted number of tardy jobs on a single machine, written 1∥∑wjUj1\|\sum w_jU_j1∥∑wj​Uj​ in later scheduling notation, is one of the basic due-date objectives: each job either meets its deadline or pays a fixed penalty, and the question is which jobs to sacrifice. Moore (Management Sci. 15, 1968) solved the unweighted case pj=1p_j = 1pj​=1 with a greedy procedure.…

9 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

A Functional Equation and Its Application to Resource Allocation and Sequencing Problems 1: Equation (1) Computes the Minimum Total Loss of a Fixed Job Order with Two Processing Modes per JobResearch Paper

Many single-machine scheduling problems have a structure that is easy to describe: the jobs must be processed in an order that is already known, and the only decisions are how and when to process each one. Lawler and Moore, in A Functional Equation and Its Application to Resource Allocation and Sequencing Problems (Management Science 16(1), 1969, 77–84),…

4 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Linear Programming and Finite Markovian Control Problems IV: Positive Dynamic Programming — an Extreme Optimal Dual Solution Yields a Pure Stationary Optimal PolicyTextbook

A finite Markov decision system asks how to choose actions while a changing state controls which actions are available. The choice can affect both the reward now and the distribution of future states. In a total-reward problem, the process can continue indefinitely; if transitions are substochastic, it can also terminate. Kallenberg's treatment of positive…

6 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization+2·Captain: mikedeng1

Linear Programming and Finite Markovian Control Problems IX: Discounted Semi-Markov Decision Processes — the Value Vector Is the Smallest Superharmonic VectorTextbook

A decision maker may choose an action whenever a system changes state, even though the time until the next change is random. Maintenance and replacement decisions are examples: a repair choice changes both the next operating state and the length of time before another choice is available. A discrete-time Markov decision model gives every decision epoch the…

6 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryLinear OptimizationOperations Research+1·Captain: mikedeng1

Linear Programming and Finite Markovian Control Problems VIII: Single-Controller Stochastic Games — a Dual Pair of Linear Programs Gives the Value and Stationary Optimal PoliciesTextbook

A two-person zero-sum stochastic game (also called a Markov game) is a Markov decision problem with two decision makers who pull in opposite directions: at every time point both players choose an action simultaneously, one player pays the other, and the system moves to a random next state whose law depends on the current state and both actions. Stochastic…

7 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Linear Programming and Finite Markovian Control Problems II: An Extreme Optimal Solution of the Dual Linear Program Yields a Pure Stationary Policy Optimal among Transient PoliciesTextbook

A Markov decision model describes a system that repeatedly occupies a state, receives a reward when an action is chosen, and then moves according to action-dependent probabilities. Termination may occur after any action. In a model with signed rewards, a policy that continues indefinitely can have a different total-reward behavior from one that eventually…

9 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Linear Programming and Finite Markovian Control Problems I: Five Equivalent Characterizations of a Transient Markov Decision Problem, among Them Contraction and a Finite Linear ProgramTextbook

Finite Markov decision models are often described by policies that choose an action from the current state. The admissible class in a total reward problem is wider: a randomized decision may use the complete history of observed states and chosen actions. For an undiscounted infinite horizon, the expected number of visits to a state may be infinite, and the…

12 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Linear Programming and Finite Markovian Control Problems III: Contracting Dynamic Programming — Pure, Stationary, Markov and General Policies Span One State-Action Frequency PolytopeTextbook

Finite Markov decision models describe repeated choices whose consequences depend on the present state. They are used when a planner needs one rule that works from every starting state, yet the rule may in principle respond to the entire observed history. Linear programming offers a different description: it records how often each state and action are used,…

6 thms2 active usersReviewed
🏆Completed
Complexity TheoryMathematical LogicOperations Research·Captain: mikedeng1

The Complexity of Markov Decision Processes V: A Quantified Boolean Formula Is True Iff Its Partially Observed Markov Decision Process Has a Zero-Cost PolicyResearch Paper

A Markov decision process is the standard model of sequential decision making under uncertainty: a controller observes the state of a finite system, chooses a decision, pays a cost, and the system moves to a random next state. In many applications (maintenance, inventory with unreliable records, robotics, medical treatment) the controller does not see the…

8 thms2 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchOptimization·Captain: mikedeng1

The Complexity of Markov Decision Processes II: The Optimal Average Cost of a Deterministic Process Is the Least Mean Cost of a Cycle Reachable from the Initial StateResearch Paper

A Markov decision process describes repeated choices whose costs and subsequent states depend on the current state. Such models are used when a decision affects both today's expense and the options available tomorrow. Papadimitriou and Tsitsiklis studied how the computational difficulty of finding an optimal policy changes between stochastic and…

7 thms2 active usersReviewed
🏆Completed
Markov ChainOperations ResearchOptimization·Captain: mikedeng1

An Analysis of Stochastic Shortest Path Problems: If Every Improper Policy Has Infinite Cost, the Optimal Cost Is the Unique Fixed Point of Bellman's Operator and Value Iteration Converges to ItResearch Paper

A shortest path problem asks how to reach a destination at minimum cost. In a stochastic shortest path problem, a decision at a state selects a probability distribution over successor states, so both the route and its total cost are random. Costs may have either sign. This makes the problem relevant to finite-state control models where rewards and expenses…

11 thms2 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchOptimization·Captain: mikedeng1

On a Routing Problem: Successive Approximations from the Direct-Route Policy Decrease to the Unique Solution of the Routing Equation Within N − 1 IterationsResearch Paper

Finding the quickest route between two points of a road network is among the oldest problems of operations research. It is the subproblem inside vehicle routing, network flow and many dynamic programs. Richard Bellman's four-page note On a routing problem (Quarterly of Applied Mathematics, 1958) treats it as a dynamic program. The minimal travel times…

8 thms2 active usersReviewed
🏆Completed
Markov ChainOperations Research·Captain: mikedeng1

Discrete-Time Controlled Markov Processes with Average Cost Criterion: A Survey 2: Uniformly Bounded Mean Return Times Make the Differential Discounted Values Uniformly BoundedResearch Paper

Controlled Markov processes with the average cost criterion model systems that run indefinitely, such as queues, inventories, maintenance and communication networks, where only the long-run cost per unit time matters. The standard route to an optimal stationary policy goes through the average cost optimality equation (ACOE). The ACOE is usually obtained by…

10 thms2 active usersReviewed
🏆Completed
Markov ChainOperations Research·Captain: mikedeng1

Discrete-Time Controlled Markov Processes with Average Cost Criterion: A Survey 3: A Uniform Lower Bound on the Probability of Moving to State 0 Reduces Average Cost to Discounted CostResearch Paper

A controller acting over an indefinite horizon must decide whether a lower cost today is worth a higher cost later. Average cost measures the expected expenditure per stage as the horizon grows. It is appropriate when operation has no natural terminal date, but its limiting definition makes it difficult to compute an optimal policy directly. Discounted cost…

7 thms2 active usersReviewed
🏆Completed
Control TheoryOperations ResearchOptimization·Captain: mikedeng1

Optimality of Affine Policies in Multistage Robust Optimization: In One-Dimensional Constrained Min-Max Control, Disturbance-Affine Policies with Affine Stage Costs Attain the Optimal ValueResearch Paper

Multistage robust optimization chooses decisions over time while an adversary picks the uncertain data from a known set; every later decision may react to what has been observed. The exact problem is a nested min-max over functions of the past, and is intractable in general. The standard workaround, proposed by Ben-Tal, Goryashko, Guslitzer and Nemirovski (M…

11 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Computational Issues in an Infinite-Horizon, Multiechelon Inventory Model 1: The Decomposition Policy Is Optimal for Discounted CostsResearch Paper

Distribution systems often move stock in two stages. A depot orders from an outside supplier and ships to a retail outlet, where customer demand arrives and unmet demand is backordered. Stock held anywhere costs money, a shortage at the outlet costs more, and each order carries a fixed charge. The basic question is what ordering and shipping rule minimizes…

11 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Computational Issues in an Infinite-Horizon, Multiechelon Inventory Model 2: The Decomposition Policy Is Average-Cost OptimalResearch Paper

Many supply chains move stock through a central warehouse to the retail locations that face customer demand. Deciding how much the warehouse should order from outside, and how much it should ship to each retailer and when, is a stochastic dynamic program whose state contains every stock level and every outstanding order. Exact solution is out of reach…

11 thms2 active usersReviewed
🏆Completed
Control TheoryProbability·Captain: mikedeng1

Discrete-Time Controlled Markov Processes with Average Cost Criterion: A Survey 6: A Canonical Policy Is Strong Average Optimal and Its Average Cost Is the Optimal OneResearch Paper

A controlled Markov process (CMP), or Markov decision process, models a system that moves randomly between states while a controller chooses actions that influence both the cost incurred and the next state. When the planning horizon is long and no discounting is natural (queueing control, inventory, communication networks, maintenance), the criterion of…

12 thms2 active usersReviewed
🏆Completed
Markov ChainOperations Research·Captain: mikedeng1

Discrete-Time Controlled Markov Processes with Average Cost Criterion: A Survey 1: Uniformly Bounded Differential Discounted Values Give a Bounded Solution of the Average Cost Optimality EquationResearch Paper

Many control problems in queueing, inventory and communication systems run indefinitely, and the quantity of interest is the long-run cost per unit time rather than a discounted total. The average cost criterion is harder to analyse than the discounted one: the discounted dynamic programming operator is a contraction, while the average cost problem has no…

9 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Stochastic Optimal Control: The Discrete-Time Case IV: The Generalized Abstract Model — Restricted Policy Classes under ContractionTextbook

Abstract dynamic programming, in the form developed by Denardo (1967) and Bertsekas (1977), studies sequential decision problems through a single monotone mapping H(x,u,J)H(x,u,J)H(x,u,J): the cost of using control uuu at state xxx when the future is valued by the function JJJ. Chapters 2–5 of Bertsekas and Shreve, Stochastic Optimal Control: The Discrete-Time Case (1978; Athena…

7 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Discounted Dynamic Programming: An Optimal Stationary Plan Exists When the Action Set Is Essentially FiniteResearch Paper

Sequential decisions often change the distribution of future states. A planner choosing an action today must account for both its immediate reward and the later rewards made possible by the resulting state. The mathematical question is whether an optimal rule can be chosen once and reused at every stage, even when a competing plan may randomize and use the…

11 thms2 active usersReviewed
🏆Completed
Control TheoryOperations ResearchOptimization·Captain: mikedeng1

Stochastic Optimal Control: The Discrete-Time Case I: Finite-Horizon Abstract Dynamic Programming — the DP Algorithm Yields the N-Stage Optimal CostTextbook

Dynamic programming (DP) solves sequential decision problems by backward recursion: compute the optimal cost of the last stage, then of the last two stages, and so on. For problems with finitely many states and controls and real-valued costs, the recursion obviously gives the optimal cost. Applications are rarely like that. Control spaces are continuous,…

12 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Optimal Policies for a Multi-Echelon Inventory Problem: The Two-Echelon Optimal Cost Splits into the Isolated Installation-1 Cost Plus a Function of Echelon StockResearch Paper

Most physical supply chains hold stock at several levels: a factory warehouse feeds a regional depot, which feeds a retail outlet. Each level orders from the one above it, and a shortage upstream delays replenishment downstream. Optimizing such a multi-echelon system by dynamic programming looks hopeless, because the state is a vector of stock levels and…

8 thms2 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Algorithm 97: Shortest Path: Floyd's Procedure Computes the Shortest Path Length Between Every Pair of PointsResearch Paper

Routing and network optimization often require the length of the best route between every ordered pair of points. Robert W. Floyd's Algorithm 97 gives a compact procedure for this task: it receives a matrix of direct-link lengths and changes the matrix in place until each entry is meant to represent a shortest-path length. The procedure is a small…

6 thms2 active usersReviewed
PreviousPage 12 of 14Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me