Inverse Optimization: Theory, Methods, and Practical Applications

FINAL DEGREE PROJECT Inverse Optimization: Theory, Methods, and Practical Applications Presented by: Jairo Escánez García Supervised by: DR. EMILIO CARRIZOSA PRIEGO FACULTY OF MATHEMATICS Statistics and Operational Research Department Sevilla, June 2025 Contents Abstract 11 Resumen 13 1 Introduction 15 1.1 Contents basic description . . . . . . . . . . . . . . . . . . . . . . . 15 1.2 Notation................................. 15 1.3 Generalconcepts ............................ 16 1.3.1 The Forward Problem . . . . . . . . . . . . . . . . . . . . . 16 1.3.2 Optimal Solution Set . . . . . . . . . . . . . . . . . . . . . . 17 1.3.3 The Inverse Problem . . . . . . . . . . . . . . . . . . . . . . 17 2 Classical Inverse Optimization 19 2.1 Classical Inverse Optimization Paradigm . . . . . . . . . . . . . . . . 20 2.2 LinearModels.............................. 20 2.2.1 Estimating the Objective Vector . . . . . . . . . . . . . . . . 21 2.2.2 Estimating the Constraints Parameters . . . . . . . . . . . . . 22 2.2.2.1 Estimating the Constraint Matrix . . . . . . . . . . 22 2.2.2.2 Estimating Both the Constraint Matrix and the RightHand-Side Vector . . . . . . . . . . . . . . . . . . 23 2.2.3 Jointly Estimating the Objective Vector and the Constraint Parameters............................. 23 2.3 Conic and Convex Models . . . . . . . . . . . . . . . . . . . . . . . 24 2.4 Partially Constrained Inverse Problems . . . . . . . . . . . . . . . . . 25 2.5 Inverse Optimal Value . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3 Data-Driven Inverse Optimization 27 3.1 Distance From the Optimal Solution Set . . . . . . . . . . . . . . . . 28 3.2 Suboptimality of the Dataset . . . . . . . . . . . . . . . . . . . . . . 32 3.2.1 Absolute Suboptimality Loss Function . . . . . . . . . . . . . 32 3.2.1.1 Estimating the Objective Vector of a Linear Model . 32 3 4 Contents 3.2.1.2 Estimating the Constraints Parameters of a Linear Model ........................ 33 3.2.2 Relative Suboptimality Loss Function . . . . . . . . . . . . . 34 3.2.2.1 Estimating the Objective Vector of a Linear Model . 34 3.2.2.2 Jointly Estimating the Forward Model Parameters of aLinearModel ................... 35 3.3 Violating the KKT Conditions . . . . . . . . . . . . . . . . . . . . . 36 4 Deep Inverse Optimization 37 4.1 Introduction............................... 37 4.2 Deep Learning Framework for IO . . . . . . . . . . . . . . . . . . . 38 4.3 Discussion................................ 40 5 Implementation and computational experiments 41 5.1 Neural Network Model . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.2 Deep Inverse Optimization . . . . . . . . . . . . . . . . . . . . . . . 42 5.3 EvaluationMetrics ........................... 43 5.4 Linear Program with Dynamic Feasible Regions . . . . . . . . . . . . 43 5.4.1 Forward Optimization Problem . . . . . . . . . . . . . . . . 43 5.4.2 Model Description . . . . . . . . . . . . . . . . . . . . . . . 45 5.4.2.1 Neural Network Model . . . . . . . . . . . . . . . 45 5.4.2.2 Deep Inverse Optimization Algorithm . . . . . . . 46 5.4.3 Results ............................. 46 5.5 Linear Program with Fixed Feasible Regions . . . . . . . . . . . . . . 49 5.5.1 Forward Optimization Problem . . . . . . . . . . . . . . . . 49 5.5.2 Model Description . . . . . . . . . . . . . . . . . . . . . . . 50 5.5.2.1 Neural Network Model . . . . . . . . . . . . . . . 50 5.5.2.2 Deep Inverse Optimization Algorithm . . . . . . . 51 5.5.3 Results ............................. 51 5.6 Conclusions............................... 52 A Linear Program with Dynamic Feasible Regions 55 A.1 Part 1: data obtaining and preprocessing . . . . . . . . . . . . . . . . 55 A.2 Part 2: model definition and training . . . . . . . . . . . . . . . . . . 58 A.2.1 Evaluation of the model on the test set . . . . . . . . . . . . . 68 A.3 Part3:DeepIOmodel ......................... 71 B Linear Program with Fixed Feasible Regions 79 B.1 Part 1: data obtaining and preprocessing . . . . . . . . . . . . . . . . 79 B.2 Part 2: model definition and training . . . . . . . . . . . . . . . . . . 84 B.2.1 Evaluation of the model on the test set . . . . . . . . . . . . . 94 B.3 Part3:DeepIOmodel ......................... 97 Contents 5 Bibliography 102 6 Contents List of Figures 1.1 Taxonomy of Inverse Optimization Models . . . . . . . . . . . . . . 16 3.1 Example of discontinuity on the objective function. . . . . . . . . . . 30 5.1 Neural Network Model . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.2 Linear Program with Dynamic Feasible Regions . . . . . . . . . . . . 44 5.3 Neural Network Model 1 . . . . . . . . . . . . . . . . . . . . . . . . 46 5.4 DeepIOsolutions............................ 48 5.5 Neural Network solutions . . . . . . . . . . . . . . . . . . . . . . . . 48 5.6 Comparison of solutions generated by both models. . . . . . . . . . . 48 5.7 Linear Program with Fixed Feasible Regions . . . . . . . . . . . . . . 50 5.8 DeepIOsolutions............................ 52 5.9 Neural Network solutions . . . . . . . . . . . . . . . . . . . . . . . . 52 5.10 Comparison of solutions generated by both models. . . . . . . . . . . 52 7 8 List of Figures List of Tables 5.1 Metrics for both models in experiment 1 . . . . . . . . . . . . . . . . 47 5.2 Metrics for both models in experiment 2 . . . . . . . . . . . . . . . . 51 9 16 1.3. General concepts We use lowercase letters to denote scalars. For example, kis a scalar. Let int(C)denote the interior, and extr(C)denote the set of extreme points of the convex hull of a set C. The Dirac delta function is denoted by δx(·). Probability distributions are denoted by P, and the expectation operator is denoted by EP[·]. The empirical distribution corresponding to a dataset {ˆxi}N i=1 is denoted by PN:= 1 NPN i=1 δˆxi. The p-norm of a vector xis denoted by ∥x∥p. 1.3 General concepts In Inverse Optimization, we distinguish between two key of elements, the Forward Problem and the Inverse Problem, which we will define in the following sections. Figure 1.1: Taxonomy of Inverse Optimization Models 1.3.1 The Forward Problem The Forward Problem refers to the optimization problem that the decision-maker seeks to solve. As an optimization problem, it is defined by the objective function f(x,u,θ)and the feasible set X(u,θ), where u∈Uand θ∈Θare given parameters that control the objective. The goal is to find the optimal solution x∗that minimizes the objective function. The parameter urepresents the input or context, characterizing the forward optimization model, while the parameter θis the parameter to be estimated, reflecting the decision-maker’s preferences. Definition 1.3.1. Forward Optimization Problem Let the Forward Optimization Problem be defined as FOP(u,θ) := min x{f(x,u,θ)|x∈X(u,θ)}. Notation 1.3.1. For a given ui, we denote the Forward Optimization Problem as FOPi(θ) := FOP(ui,θ). Chapter 1. Introduction 17 1.3.2 Optimal Solution Set Definition 1.3.2. Optimal Solution Set For fixed u∈Uand θ∈Θ, we define the Optimal Solution Set as Xopt(u,θ) := arg min x{f(x,u,θ)|x∈X(u,θ)} This is the set of optimal solutions of the Forward Optimization Problem FOP(u,θ) for fixed uand θ. Notation 1.3.2. For a given ui, we denote the Optimal Solution Set as Xopt i(θ) := Xopt(ui,θ). 1.3.3 The Inverse Problem The Inverse Problem refers to the task of inferring the parameters θof the forward optimization model from a dataset of optimal decisions {(ˆxi,ˆui)}N i=1. The goal is to find the parameter vector θ∗that best fits the observed decisions, where the degree of fitting will be measured depending on the approach used to solve the Inverse Problem. The Inverse Problem can be formulated using two different approaches based on the observed decisions: the Classical Inverse Optimization Problem and the Data-Driven Inverse Optimization Problem. • In the Classical Inverse Optimization Problem, we assume that the observed decisions are optimal, meaning that ˆxiis the optimal solution of the Forward Optimization Problem FOP(ˆui,θ)for the entire dataset. This is called Perfect Model-Data Fit. • In the Data-Driven Inverse Optimization Problem, we do not require the observed decisions to be optimal, so we do not assume Perfect Model-Data Fit. With more detail, given a dataset, Inverse Optimization estimates a parameter vector θ∗such that the aggregate fit of the corresponding forward model FOPi(θ∗)to ˆxi is optimized. An estimate θ∗is considered a perfect fit for ˆxiif ˆxi∈Xopt i(θ∗). To formalize this, we introduce the concept of the Inverse-Feasible-Set. Definition 1.3.3. Inverse-Feasible-Set Let the Inverse-Feasible-Set be defined as Θinv(ˆui,ˆxi) := {θ∈Θ|ˆxi∈Xopt(ˆui,θ)} This is the set of parameters θthat make the observed decision ˆxioptimal under the Forward Optimization Problem FOP(ˆui,θ). 18 1.3. General concepts With this concept, we can reformulate the two approaches of the Inverse Problem as follows. In the Classical Inverse Optimization Problem, we not only assume that the observed decisions are optimal, but also that the parameter θthat we are trying to estimate is inverse-feasible, meaning that θ∈Θinv(ˆui,ˆxi)for the entire dataset and minimizes a specific objective function h(θ). The Classical Inverse Optimization Problem is formulated as follows: min θ{h(θ)|θ∈Θinv(ˆui,ˆxi)∀i= 1,...,N}(1.1) Intuitively, we search for the best parameter θthat minimizes the objective function h(θ)and makes all the observed decisions optimal within the set TN i=1 Θinv(ˆui,ˆxi). On the other hand, in the Data-Driven Inverse Optimization Problem, inverse feasibility is not enforced. We use the concept of a loss function ℓ(xi,Xopt i(θ)) to measure the error of the Forward Optimization Model with respect to the observed decisions. The Data-Driven Inverse Optimization Problem is formulated as follows: min θ{k h(θ) + 1 N N X i=1 ℓ(ˆxi,Xopt(ˆui,θ))|θ∈Θ}(1.2) Here, kis a positive constant that weights the importance of the objective function h(θ)and the loss function ℓ(ˆxi,Xopt(ˆui,θ)). Notation 1.3.3. Consider a dataset {(ˆxi,ˆui)}N i=1 of N≥1decisions. We can alternatively define the following objects: fi(x,θ) := f(x,ˆui,θ) Xi(θ) := X(ˆui,θ) Using this notation, we can distinguish between different types of input data: 1. We observe a dataset of decisions and inputs {(ˆxi,ˆui)}N i=1. 2. We observe a dataset of decisions and forward models {(ˆxi,FOPi(θ))}N i=1. 3. We observe a dataset of decisions and optimal solution sets {(ˆxi,Xopt i(θ))}N i=1. Chapter 2 Classical Inverse Optimization In this chapter, we explore the Classical Inverse Optimization Model (1.1), introduced in chapter 1, its computational challenges, and methods to solve specific instances of the problem. In detail, we present techniques for linear, conic, convex, and partially constrained models, that each reformulate the inverse optimization model into a tractable optimization problem as discussed in [4]. Although the reformulation techniques discussed in this chapter can solve any instances of Problem (1.1), we focus on the most common objective function, namely h(θ) = ∥θ−ˆ θ∥p, where ˆ θis a fixed vector known as the reference value. This reference value can be derived from expert knowledge, historical data, or other sources of information. For ease of exposition, we assume a single decision input, i.e., n= 1. The techniques presented in this chapter can be easily extended to cases where n>1. A single decision input implies a single forward model, allowing us to omit the contextual input. Therefore, we exclude uand the index iin this chapter. Now, we can redefine the Classical Inverse Optimization Model for this specific objective function. Definition 2.0.1. Classical Inverse Optimization Model Given a forward optimization model FOP(θ)and a reference value ˆ θ, the Classical Inverse Optimization Model is defined as follows: IOP −C(ˆx,ˆ θ) := min θ{∥θ−ˆ θ∥p|θ∈Θinv(ˆx)} It is important to note that the parameter to estimate, θ, is inverse-feasible with respect 19 20 2.1. Classical Inverse Optimization Paradigm to the observed decision ˆx, as θ∈Θinv(ˆx). As mentioned in the introduction, this is a characteristic of Classical Inverse Optimization. Next, we particularize the model for specific forward optimization problems and provide characterizations of the inverse feasible set to reformulate the inverse optimization problem into a tractable optimization problem. 2.1 Classical Inverse Optimization Paradigm Proposition 2.1.1. Given a forward optimization model FOP(θ)with objective function f. Then, ˆx is an optimal solution of FOP(θ)if and only if f(ˆx,θ)≤f(x,θ),∀x∈X(θ) Using 2.1.1, the inverse feasible set Θinv(ˆx)can be rewritten as: Θinv(ˆx) := {θ∈Θ|f(ˆx, θ)≤f(x,θ),∀x∈X(θ)}(2.1) The earliest paradigms in Classical Inverse Optimization relied on this characterization to solve the inverse optimization problem. However, the computational complexity of this approach is high because it requires enumerating all feasible solutions of the forward optimization model, which is generally impractical. As a result, alternative and tractable characterizations of the inverse feasible set have been developed. 2.2 Linear Models Consider the linear forward optimization model: FOP −L(θ,Φ,Ψ) := min x{θTx|Φx ≥Ψ} where the objective vector θ∈Rn, the constraint matrix Φ∈Rm×n, and the righthand-side constraint vector Ψ∈Rm. The literature on linear inverse optimization models generally focuses on the estimation of either the objective vector θor the constraint parameters Φand Ψindependently. That is, assuming that the other parameters are known: • Estimating the objective vector θ: Let Φ=A,Ψ=b, be the known constraint parameters. The inverse optimization problem seeks to estimate the objective vector θwith minimum distance from the reference value ˆ θ. • Estimating the constraints Φand Ψ: Let θ=cbe the known objective vector, where c∈Rn. The inverse optimization problem searches for estimate the Chapter 2. Classical Inverse Optimization 21 constraint parameters (Φ,Ψ)of a minimum distance from the reference values (ˆ Φ,ˆ Ψ). Note that this problem generalizes the cases of estimating only the constant matrix Φ(i.e., Θ:={(Φ,Ψ)|Ψ=b}) or only the right-hand-side vector Ψ(i.e., Θ := {(Φ,Ψ)|Φ=A}). Notation 2.2.1. When it is obvious from the context, we simplify the notation by omitting from FOP −L(θ,Φ,Ψ)the parameters that are known. For example, FOP −L(θ):=FOP −L(θ,A,b) = minx{θTx|Ax≥b}. 2.2.1 Estimating the Objective Vector In this section, we show that the inverse optimization problem of a linear program can be reformulated as an optimization problem with linear constraints, by characterizing the inverse feasible set Θinv(ˆx)using the complementary slackness conditions in linear programming. Proposition 2.2.1. Complementary Slackness If ˆx is an optimal solution of FOP −L(θ), then there exists a dual vector λ∈Rm satisfying: 1. Dual Feasibility: ATλ=θ 2. λ≥0 3. Complementary Slackness: (Aˆx −b)Tλ= 0 Using 2.2.1, we can rewrite the inverse feasible set as: Θinv(ˆx) := {θ∈Rn| ∃λ∈Rm,λ≥0,ATλ=θ,(Aˆx −b)Tλ= 0} Thus, the inverse optimization problem can be reformulated as a linear optimization problem: IOP −L(ˆx) := min θ∈Θ∥θ−ˆ θ∥p s.t.ATλ=θ (Aˆx −b)Tλ=0 λ≥0 (2.2) We can also reformulate the linear inverse optimization problem by using the Strong Duality property from linear programming. Proposition 2.2.2. Strong Duality If ˆx is an optimal solution of FOP −L(θ), then there exists a dual vector λ∈Rm satisfying: 22 2.2. Linear Models 1. Dual Feasibility: ATλ=θ 2. λ≥0 3. Strong Duality: θTˆx =λTb Proposition 2.2.2 allows us to rewrite the second constraint (Aˆx −b)Tλ=0. And the new inverse optimization problem is: IOP −L(ˆx) := min θ∈Θ∥θ−ˆ θ∥p s.t.ATλ=θ θTˆx =λTb λ≥0 (2.3) A generalization of this problem is presented in chapter 3, where the optimality of the dataset is not assumed. 2.2.2 Estimating the Constraints Parameters Recall that when estimating the constraint parameters, we assume the objective vector θis known, i.e., θ=c. 2.2.2.1 Estimating the Constraint Matrix First, we assume the right-hand-side vector Ψis known, i.e., Ψ=b. The inverse optimization problem aims to estimate the constraint matrix Φsuch that it is of minimum distance from the reference value ˆ Φ. Using Proposition 2.2.2, the inverse feasible set can be rewritten as: Θinv(ˆx) := {Φ∈Rm×n| ∃λ∈Rm,λ≥0,ΦTλ=c,cTˆx =λTb} The inverse optimization problem can be reformulated as the following optimization problem: IOP −L(ˆx) := min Φ∈Rm×n∥Φ−ˆ Φ∥p s.t.ΦTλ=c cTˆx =λTb λ≥0 (2.4) Note that problem (2.4) contains a bilinear constraint, ΦTλ=c, which makes the problem non-convex, non-linear, and computationally challenging to solve. Chan and Kaw [2] propose a solution to this problem by observing that for ˆx to be optimal, at Chapter 2. Classical Inverse Optimization 23 least one constraint must satisfy the equality. Specifically, an optimal solution for the inverse problem can be obtained by perturbing the nearest facet {x|ˆ ΦT jx≥bj}from ˆx until it satisfies the equality constraint. 2.2.2.2 Estimating Both the Constraint Matrix and the Right-Hand-Side Vector We now consider the general case where both the constraint matrix Φand the righthand-side vector Ψare unknown. The inverse optimization problem is to estimate the constraint parameters (Φ,Ψ)with minimum distance from the reference values (ˆ Φ,ˆ Ψ). Using Proposition 2.2.2, we can rewrite the inverse feasible set as: Θinv(ˆx) := {(Φ,Ψ)∈Rm×n×Rm| ∃λ∈Rm,λ≥0,ΦTλ=c,cTˆx =λTΨ} Observe that now there are two bilinear constraints that make the problem non-convex, non-linear, and computationally difficult to solve. Because of this, we use the simplest constraint to formulate the problem: min (Φ,Ψ)∈Rm×n×Rm∥(Φ,Ψ)−(ˆ Φ,ˆ Ψ)∥p s.t.Φˆx ≥Ψ 2.2.3 Jointly Estimating the Objective Vector and the Constraint Parameters In this section, we consider the case where both the objective vector θand the constraint parameters are unknown, except for the constraint matrix Φ, which we assume is known Φ=A. The inverse optimization problem is to estimate the objective vector θand the right-hand-side vector Ψ"such that they are of minimum distance from the reference values (ˆ θ,ˆ Ψ). Consider the linear forward optimization model FOP −L(θ,Ψ)with Φ=A, and the objective vector θand the right-hand-side vector Ψare unknown. Using Proposition 2.2.1, we can leverage the complementary slackness formulation: min θ∈Θ∥(θ,Ψ)−(ˆ θ,ˆ Ψ)∥p s.t.ATλ=θ (Aˆx −Ψ)Tλ=0 λ≥0 (2.5) Again, the complementary slackness constraint is bilinear. To linearize it, we introduce an additional variable z∈ {0,1}m. Thus, Problem (2.5) can be formulated as a mixed- 24 2.3. Conic and Convex Models integer linear optimization problem (MILP). min θ∈Θ,Ψ∈Rm∥(θ,Ψ)−(ˆ θ,ˆ Ψ)∥p s.t.Aˆx −Ψ≥0 Aˆx −Ψ≤Mz λ≤M(1−z) ATλ=θ λ≥0 z∈ {0,1}m (2.6) where Mis a sufficiently large positive constant. 2.3 Conic and Convex Models In this section, we consider m≥2,C⊆Rnas a closed convex cone with nonempty interior, such that {x,−x} ⊆ Cimplies x=0. The conic forward optimization model is: FOP −CON(θ) := min x{f(x,θ)| − g(x,θ)∈C}(2.7) where f(x,θ)is a convex function in xfor fixed θ, and g(x,θ) = (g1(x,θ), . . . , gm(x,θ)) is a vector-valued convex function whose components are each differentiable and convex. Note that setting C=Rn +reduces the forward problem to a classical convex optimization problem where, −g(x,θ)∈Cif and only if g(x,θ)≥0. Iyengar and Kang [7] used the KKT conditions to characterize the inverse feasible set of the conic forward optimization model and derive a tractable reformulation of IOP −C(ˆx,ˆ θ). Proposition 2.3.1. KKT Conditions A decision ˆx is an optimal solution of FOP −CON(θ)if: 1. There exists x∈Csuch that −g(x,θ)∈int(C) 2. There exists λ∈Csuch that ∇xf(ˆx, θ)+Pm j=1 λj∇xgj(ˆx, θ)=0and λjgj(ˆx, θ) = 0,∀j= 1, . . . , m Using Proposition 2.3.1, we can rewrite the inverse feasible set as: Θinv(ˆx) := {θ∈Θ| ∃x∈C,−g(x,θ)∈int(C) ∃λ∈C,∇xf(ˆx, θ) + m X j=1 λj∇xgj(ˆx, θ)=0 λjgj(ˆx, θ)=0,∀j= 1, . . . , m} Chapter 2. Classical Inverse Optimization 25 For a general FOP −CON(θ), this set includes bilinear constraints in λjand gj(ˆx, θ), making the corresponding inverse optimization problem not easily solvable. Lemma 2.3.1. Consider the conic forward optimization model FOP −CON(θ). Assume that g(x,θ)=g(x)and that there exists xsuch that −g(x)∈int(C). Then, the IOP −C(ˆx,ˆ θ)is equivalent to the following optimization problem: min θ∈Θ∥θ−ˆ θ∥p s.t.∇xf(ˆx, θ) + m X j=1 λj∇xgj(ˆx) = 0 λjgj(ˆx) = 0,∀j= 1, . . . , m λ∈C Furthermore, if ∇xf(x,θ)is an affine function of θ, then the problem is convex. 2.4 Partially Constrained Inverse Problems In this section, we consider the case where the forward optimization model is partially constrained, meaning only a part of a decision is observed. The input to these inverse problems is not a single decision ˆx ∈X, but rather a set of decisions ˆ X:= {x|x∈X,xi=ˆxi,∀i∈M} ⊆ X, where M⊆ {1,...,n}is the set of observed indices. The partially constrained inverse optimization problem aims to estimate a θsuch that at least one decision x∈ˆ Xis optimal for the forward optimization model: min θ,x{∥θ−ˆ θ∥p|x∈ˆ X,θ∈Θinv(x)}(2.8) For example, for the linear forward optimization model FOP −L(θ), using Proposition 2.2.1, Problem (2.8) can be reformulated as: min θ∈Θ∥θ−ˆ θ∥p s.t.Ax≥b ATλ=θ (Ax−b)Tλ=0 λ≥0 x∈ˆ X 32 3.2. Suboptimality of the Dataset 3.2 Suboptimality of the Dataset In this section, we introduce two popular loss functions that measure the degree of suboptimality of the observed decisions ˆx under our estimated forward model FOPi(θ). The literature has focused on the following two loss functions: •Absolute suboptimality loss function: This function measures the absolute difference between the objective function value of the observed decision and the optimal decision under the estimated forward model. ℓASO(ˆx,X(θ)) := |f(ˆx,θ)−min x∈X(θ)f(x,θ)| •Relative Suboptimality loss function: This function measures the competitive ratio of the objective function value of the observed decision and the optimal decision under the estimated forward model. ℓRSO(ˆx,X(θ)) :=  f(ˆx,θ) minx∈X(θ)f(x,θ)−1 Let IOP −DD(ℓASO,PN)and IOP −DD(ℓRSO,PN)be the inverse optimization data-driven problems using the Absolute Suboptimality and Relative Suboptimality loss functions, respectively. 3.2.1 Absolute Suboptimality Loss Function First let us consider the special case where the observed decisions of the dataset are known to be feasible, this is, ˆxi∈Xi(θ)for all (ˆxi,ˆui)in Dand θin Θ. In this case, we can remove the absolute value from the loss function and reformulating the Inverse Optimization Problem Data-Driven as: IOP −DD(ℓASO,PN) = min θ∈Θ 1 N N X i=1 (fi(ˆxi,θ)−fi(xi,θ)) s.t.xi∈Xopt i(θ)∀i∈ {1, . . . , N} 3.2.1.1 Estimating the Objective Vector of a Linear Model Now we particularize the linear forward model FOP −L(θ)without assuming feasible observations. Inverse Absolute Suboptimality problem IOP −DD(ℓASO,PN) becomes an efficient linear program by reformulating it using Strong Duality. Chapter 3. Data-Driven Inverse Optimization 33 Theorem 3.2.1. Consider FOP −Li(θ). Then the Inverse Absolute Suboptimality problem IOP −DD(ℓASO,PN)is equivalent to the following linear program: min θ∈Θ 1 N N X i=1 |θTˆxi−bT iλi| s.t.AT iλi=θ∀i∈ {1, . . . , N} λi≥0∀i∈ {1, . . . , N} (3.4) The proof of this theorem is based on applying Strong Duality to the linear program FOP −Li(θ)as we did in (3.3). Problem (3.4) is a generalization of the Inverse Linear Optimization problem introduced in section 2.2. If ˆxiare all optimal solutions, then the objective function value will be zero, and the objective can be replaced with constraints θTˆxi=bT iλfor all i, and the problem becomes the original problem Equation 2.2. As in Problem (3.3), the number of constraints and variables increases with the number of observations, making the inverse optimization problem computationally expensive and hard to solve. However, as in Problem (3.3), if we assume that all of the points ˆxiare solutions of the same forward model, i.e., FOP −Li(θ) = FOP −L(θ)for all i, then the dual variable λiis the same for all i, i.e., λi=λfor all i. In this case, we only need to control a single dual variable instead of N, and the problem becomes: min θ∈Θ 1 N N X i=1 |θTˆxi−bTλ| s.t.ATλ=θ λ≥0 3.2.1.2 Estimating the Constraints Parameters of a Linear Model Now, we focus on estimating parameters in the constraints of the forward models FOP −Li(Φ). Recall that when estimating these parameters, we assume that the cost vector, ci, and the right-hand side vector, bi, are known. The inverse optimization problem is essentially the same as previously mentioned problem, but with the cost vector and the right-hand side vector known and the parameters in the constraints unknown and introducing the term Φxi≥bito make sure that the observations are feasible. 34 3.2. Suboptimality of the Dataset The problem is formulated as: min Φ∈Rm×n 1 N N X i=1 |cT iˆxi−bT iλi| s.t.Φλi=ci∀i∈ {1,...,N} Φxi≥bi∀i∈ {1,...,N} λi≥0∀i∈ {1, . . . , N} This problem is a bilinear program, due to the first constraint, where two variables are multiplied. 3.2.2 Relative Suboptimality Loss Function In general, minimizing the Relative Suboptimality loss function is difficult to solve due to the fractional component. However, under the assumption that the forward model satisfies a scaling invariance property, i.e., θcan be scaled maintaining the same optimal value and optimal solution set, this fractional component can be removed. Definition 3.2.1. Scaling Invariance Property. A forward model FOP(u,θ)satisfies the scaling invariance property if, for all θ∈Θ and α > 0,x∗∈Xopt(θ)implies: •x∗∈Xopt(αθ) •f(x∗, αθ) = αf(x∗,θ) If the forward model satisfies the scaling invariance property and has a nonnegative optimal value, then the parameter θcan be scaled to make the optimal value equal to one while preserving the optimal solution set. Thus, the IOP −DD(ℓRSO,PN)problem can be reformulated as: min θ∈Θ 1 N N X i=1 |fi(ˆxi,θ)−1| s.t. fi(xi,θ)=1∀i∈ {1,...,N} xi∈Xopt i(θ)∀i∈ {1, . . . , N} 3.2.2.1 Estimating the Objective Vector of a Linear Model Now, we particularize the linear forward model FOP −L(θ)using strong duality and the scaling invariance property. Chapter 3. Data-Driven Inverse Optimization 35 Theorem 3.2.2. Consider FOP −Li(θ). If it satisfies that bi≥0componentwise for all i∈ {1, . . . , N}, then the Inverse Relative Suboptimality problem IOP −DD(ℓRSO,PN) is equivalent to the following linear program: min θ∈Θ 1 N N X i=1 |θTˆxi−1| s.t.bT iλi=1∀i∈ {1, . . . , N} AT iλi=θ∀i∈ {1, . . . , N} λi≥0∀i∈ {1, . . . , N} This linear program suffers the same problem as the one in (3.4), the number of constraints and variables increases with the number of observations, making the problem computationally expensive and hard to solve when the number of observations is large. But when all of the points ˆxiare solutions of the same forward model, i.e., FOP −Li(θ) = FOP −L(θ)for all i, the inverse problem can be simplified to: min θ∈Θ 1 N N X i=1 |θTˆxi−1| s.t.bTλ= 1 ATλ=θ λ≥0 3.2.2.2 Jointly Estimating the Forward Model Parameters of a Linear Model Finally, we focus on jointly estimating the constraint matrix and the cost vector of the forward models FOP −L((θ,Φ)) := minx{θTx|Φx ≥b}. The inverse optimization problem is formulated similarly to the previous one, except replacing Aiwith Φi: min θ∈Θ,Φi∈Rm×n 1 N N X i=1 |θTˆxi−1| s.t.bT iλi= 1 ∀i∈ {1, . . . , N} ΦT iλi=θ∀i∈ {1, . . . , N} λi≥0∀i∈ {1, . . . , N} This problem suffers the same issue as the previous ones, the number of constraints and variables increases with the number of observations, making the problem computationally expensive and hard to solve when the number of observations is large. However, if all of the points ˆxiare solutions of the same forward model, the inverse problem can be simplified. 36 3.3. Violating the KKT Conditions 3.3 Violating the KKT Conditions In this section, we introduce another popular loss function that measures the degree of violation of the KKT conditions (Proposition 2.3.1) of the observed decisions ˆx under our estimated forward model FOP −CVX(θ) := minx{f(x,θ)| − g(x,θ)∈C}. Recall that, KKT conditions state that it is necessary for a point to be optimal that there exists a dual variable and that both, the decision and the dual variable, satisfy a stationarity and a complementary slackness condition. Let (x,λ)be a decision and a dual variable. We define the following loss functions that measures the degree of violation of each KKT condition: •Stationarity loss function: ℓst(x,Xopt(θ),λ) :=  ∇xf(x,θ) + m X j=1 λj∇xgj(x,θ) •Complementary Slackness loss function: ℓcs(x,Xopt(θ),λ) := ∥(λ1g1(x,θ), . . . , λmgm(x,θ))∥p These functions are not strictly loss functions, as they are defined in terms of the dual variable λ, which is unknown. However, using them we can define the following loss function with which we will work with in this section: ℓKKT(ˆx,Xopt(θ)) := min λ≥0ℓst(ˆx,Xopt(θ),λ)+ℓcs(ˆx,Xopt(θ),λ) In more detail, the KKT loss function, given (ˆx,Xopt(θ)), measures the minimum degree of violation of the KKT conditions of the observed decisions ˆx under our estimated forward model. Observe that the KKT loss function is a nonconvex function, as it is defined as the minimum of a nonconvex function, the Complementary Slackness loss function. Therefore, in practical terms, for a given ˆx, computing the KKT loss function requires solving a nonconvex optimization problem. Nevertheless, if we focus on estimating only the parameters of the objective function, then the inverse optimization problem IOP −DD(ℓKKT,PN)becomes a convex optimization problem due to the following proposition. Proposition 3.3.1. Consider FOP −CVX(θ). If gdoes not depend on θ, this is gi(x,θ)=gi(x)∀i∈ {1,...,N}, and f(x,θ)is convex in θ, then the inverse optimization problem IOP −DD(ℓKKT,PN)is a convex optimization problem. Chapter 4 Deep Inverse Optimization Unlike the other two chapters, this chapter does not focus on reformulating the inverse optimization problem, it presents an algorithm that uses deep learning techniques to solve it. The algorithm is based on the work of [12]. The main idea is to unroll an iterative optimization process and then use backpropagation to learn the parameters of the forward model that generate the observations. 4.1 Introduction Again, we have a dataset of decisions and inputs {(ˆxi,ˆui)}N i=1 with N≥1. The vectors ˆxiare the decisions, and the input vector ˆuirepresents conditions under which we may want to instantiate and, with our approximation, solve the program for an input ˆu. To illustrate this chapter, we recall the forward optimization problem: FOP(u,θ) := min x{f(x,u,θ)|x∈X(u,θ)}. In this chapter, we assume that the decision variables ˆxiare optimal solutions of the FOP, and the parameter to estimate, θ, is part of the cost and constraints of the program. Thus, the goal is, given the dataset, to learn the parameter θsuch that there exists an optimal solution of FOP(ˆui,θ)that is consistent with the corresponding observed decision ˆxi. The consistency is defined by a loss function, as we will see later. As is mentioned before, the purpose of this chapter is to explain a deep learning algorithm to make the learning process of this parameter. This parameter can appear on the objective function and constraints, individually or both. This is something that has not been extensively addressed in previous chapters because the general case of learning 37 38 4.2. Deep Learning Framework for IO the parameters of a parametric linear optimization problem where the cost vector, constraint matrix, and right-hand side constraint vector depend on ucan be solved by the algorithm presented in this chapter [12]. Additionally, this approach can be applicable in online settings, where the dataset is updated over time [1]. 4.2 Deep Learning Framework for IO We consider Deep Learning as a set of techniques for optimizing functions where the global optimum is not guaranteed to be found [6]. These techniques generally do not guarantee finding the global optimum, but, in practice, they are very effective for many problems. The algorithm searches for the features of the model through automatic differentiation, a differentiation technique that computes the gradient of the loss function with respect to the model’s parameters and then updates the parameters in the opposite direction of the gradient to minimize the loss function. This technique is very accessible to use because many current machine learning libraries provide built-in automatic differentiation capabilities, such as the one used for the experiments, PyTorch [10]. Chapter 4. Deep Inverse Optimization 39 The algorithm cycles through three steps: (1) instantiate a forward optimization model with the current parameters θ, (2) solve the optimization problem with a standard algorithm (the framework used to illustrate the experiments implements the IPM algorithm), and (3) compute and update the parameters θwith the gradient of the loss function. As is common in deep learning, the parameters to learn are called weights. Algorithm 1 Deep inverse optimization framework. Require: Initial weights θini, training dataset {(ˆxi,ˆui)}N i=1. Ensure: Learned weights θlrn. 1: θ←θini 2: for sin 1to max_steps do 3: ∆θ←0 4: for iin 1to Ndo 5: x←FOP(ˆui,θ)▷Run forward optimizer to completion 6: ℓ←ℓ(x,ˆxi)▷Compute loss w.r.t. target 7: ∂ℓ ∂θ←backprop(ℓ)▷Backpropagate gradient to weights 8: ∆θ←∆θ+1 N ∂ℓ ∂θ▷Accumulate average gradient 9: end for 10: ∆θ←α⊙∆θ▷Scale gradient component-wise 11: β←line_search(θ,∆θ)▷Find safe step size 12: θ←θ−β∆θ▷Update weights 13: end for 14: return θ This algorithm takes the dataset {(ˆxi,ˆui)}N i=1 as input and initializes the weights θto θini. Gradient-based algorithms are very sensitive to the initial weights, as they can significantly affect the convergence of the algorithm. Therefore, the choice of initial weights is crucial: a good choice can speed up the convergence of the algorithm to an optimal solution, although this is not guaranteed to be the global optimum. The algorithm then iterates over a fixed number of steps, max_steps, to determine. Each step consists of iterating over the dataset, calculating the loss function, computing the gradient, scaling the gradient, performing a line-searching, and updating the weights. This process is called an epoch. In each epoch, all the data points are processed, and for each data point (ˆxi,ˆui), an instance of the forward optimization problem is solved with the current weights θ(line 5), and the loss is computed between this optimal solution and the observed decision ˆxi(line 6). The gradient of the loss function with respect to θis computed using automatic differentiation through the operations of the forward process (line 7). Next, the gradient is scaled by a factor αusing a component-wise product (⊙) to control the 40 4.3. Discussion learning rate (line 10). Line search [9] is a technique used to find a safe step size βthat minimizes the loss function (line 11). Finally, the weights are updated by subtracting the scaled gradient (line 12). This algorithm is a general framework that can be applied to any differentiable forward optimization model. Gradients can be computed even with non-linear constraints or objective functions. The forward optimizer can be any optimization algorithm, such as the simplex method, the interior-point method, or any other optimization algorithm. The hyperparameters to tune include the initial weights θini, the learning rate α, the number of steps max_steps, and the solver used to solve the forward optimization problem. 4.3 Discussion In this chapter, we have presented a deep learning algorithm to solve the inverse optimization problem through the lens of deep learning. This allows us to apply all the techniques and tools of deep learning to solve the inverse optimization problem [8]. A key strength of this algorithm is its generality and applicability to any forward optimization model for which automatic differentiation can be applied. While it may not be the best approach to solve some specific inverse optimization problems, such as the ones presented in the previous chapters or out contribution presented in chapter 5, but it provides a new strategy. Another advantage is that the algorithm can be applied in online settings, where the dataset is updated over time [1], and for different loss functions. On the other hand, the algorithm inherits the limitations of deep learning. Specifically, the gradient descent algorithm can get stuck in local minima, and the algorithm can be slow to converge. Also, the algorithm can be sensitive to the initial weights and the learning rate. Another limitation is we need to provide a forward optimization model, which may not be known beforehand. Chapter 5 Implementation and computational experiments This section presents the implementation of a new model to solve the Inverse Optimization Problem using neural networks and a comparison with the Deep Inverse Optimization algorithm over two different Inverse Optimization problems: Linear Program with Dynamic Feasible Regions and Linear Program with fixed Feasible Regions. 5.1 Neural Network Model One of the main contributions of this project is the development of a new model to solve the Inverse Optimization Problem using neural networks. The main idea is to use a neural network to learn the parameters of the forward model that generate the observations, this is, the function to optimize f(x,u), and the set X(u). Observe that now, f(x,ui)and X(ui)do not depend on the context parameter θ, since now, the network is learning the entire forward model. The model is trained using a dataset of decisions and inputs {(ˆxi,ˆui)}N i=1 with N≥1, for a given uithe model outputs ˜xithat represents the decision that the forward model would make under the predicted forward model. To provide knowledge to the model, the penultimate layer of the neural network outputs the paremeters of the estimated Forward Optimization Problem, this is, the function to optimize f(x,ui), and the set X(ui), and the last layer of the neural network receives these two outputs and solves the optimization problem to output the decision ˜xi. Figure 5.1 shows the architecture of the neural network model. 41 48 5.4. Linear Program with Dynamic Feasible Regions Figure 5.4: Deep IO solutions Figure 5.5: Neural Network solutions Figure 5.6: Comparison of solutions generated by both models. Chapter 5. Implementation and computational experiments 49 5.5 Linear Program with Fixed Feasible Regions The goal of this experiment is to evaluate and compare the performance of two approaches for solving the Inverse Optimization Problem in the context of a Linear Program with Fixed Feasible Regions: the proposed neural network model and the Deep Inverse Optimization algorithm. This problem appears to be simpler than the previous one because the feasible region remains fixed, while the objective function varies with the input parameter u. We expect both models to perform better in this scenario; however, we aim to evaluate and compare their performance to identify the strengths and limitations of each approach. To provide a comprehensive comparison, we will analyze metrics such as computational efficiency, accuracy in the solutions, and mean squared error. This analysis will help us understand which approach is more suitable for practical applications where the feasible region is fixed but the objective function depends on varying input parameters. 5.5.1 Forward Optimization Problem In this experiment, we consider a Linear Program with Fixed Feasible Regions as the Forward Optimization Problem to generate the dataset {(ˆxi,ˆui)}N i=1. The dataset {(ˆxi,ˆui)}N i=1 was generated by solving this Forward Optimization Problem for a range of input values u∈[0,6]. For each u, the optimal solution ˆxiwas computed, and the pair (ˆxi,ˆui)was recorded. This dataset was then used to train both models. The Forward Optimization Problem is defined as follows: FOP(u,θ) := min x{c(u,θ)Tx|Ax≤b},(5.2) with the following parameters: •c(u,θ) = cos(θ+u2 2) sin(θ+u2 2) •A(u,θ) =       0 1 0−1 1 0 −1 0 1 1       •b(u,θ) =       60 0 60 0 100       50 5.5. Linear Program with Fixed Feasible Regions •u∈[0,6] •θ=4 5 Figure 5.7 illustrates how the objective vector change as uvaries for this value of θ. The the objective vector is color-coded based on the value of u. Darker shades correspond to the Forward Optimization Problem with u= 0, while lighter shades correspond to u= 6. As uincreases from 0to 6, the color transitions smoothly from dark to light. Additionally, the blue points in the figure represent the optimal solutions for each Forward Optimization Problem corresponding to the different values of u. Figure 5.7: Linear Program with Fixed Feasible Regions 5.5.2 Model Description In this experiment, we compare two approaches for solving the Inverse Optimization Problem: the proposed neural network model and the Deep Inverse Optimization algorithm. Below, we describe each model in detail. 5.5.2.1 Neural Network Model The proposed neural network model is designed to learn the parameters of the Forward Optimization Problem, including the objective vector c(u)and the parameters defining Chapter 5. Implementation and computational experiments 51 the feasible region, Aand b. The model retains the same architecture and hyperparameters as the one used in the previous experiment, allowing for a direct comparison of its performance across the two different scenarios. 5.5.2.2 Deep Inverse Optimization Algorithm For this experiment, we defined Deep Inverse Optimization model with the same Forward Optimization Problem as the probem we are trying to estimate (5.2) but with θ= 4. The goal of this model is to estimate the real parameter θof the Forward Optimization Problem from which the dataset was generated. 5.5.3 Results The Deep Inverse Optimization algorithm achieves perfect accuracy (100%) and zero mean squared error (MSE), indicating that it perfectly recovers the parameters of the Forward Optimization Problem in this scenario. Additionally, it is significantly faster, requiring only 9 minutes compared to the 66 minutes needed by the neural network model. This suggests that the Deep Inverse Optimization algorithm is well-suited for problems with fixed feasible regions and varying objective functions, where the feasible region is known in advance. On the other hand, the neural network model achieves an MSE of 29.238162 and 0% accuracy, suggesting that it struggles to recover the exact parameters of the Forward Optimization Problem in this setting. Despite its lower performance in terms of accuracy and MSE, the neural network model may still be advantageous in scenarios where the Forward Optimization Problem is unknown or difficult to model explicitly. Metric Neural Network Model Deep Inverse Optimization MSE 29.238162 0 Accuracy (%) 0 100 Time (min) 66 9 Table 5.2: Metrics for both models in experiment 2 To further illustrate the performance of both models, Figure 5.10 shows the solutions generated by the neural network model and the Deep Inverse Optimization algorithm compared to the true solutions. The left image corresponds to the Deep Inverse Optimization algorithm, while the right image corresponds to the neural network model. We can observe that the Deep Inverse Optimization algorithm provides highly accurate and feasible solutions, aligning perfectly with the true solutions. In contrast, the neural 52 5.6. Conclusions network model struggles to capture the exact structure of the feasible region, resulting in less accurate predictions. Figure 5.8: Deep IO solutions Figure 5.9: Neural Network solutions Figure 5.10: Comparison of solutions generated by both models. 5.6 Conclusions In this chapter, we presented the implementation of a new model to solve the Inverse Optimization Problem using neural networks and compared its performance with the Deep Inverse Optimization algorithm over two different scenarios: a Linear Program with Dynamic Feasible Regions and a Linear Program with Fixed Feasible Regions. The results highlight the strengths and limitations of each approach, providing valuable insights for their application in practical settings. The results of the experiments show that the neural network model outperforms the Deep Inverse Optimization algorithm in terms of accuracy and precision for the Linear Program with Dynamic Feasible Regions. The neural network model achieved a significantly lower Mean Squared Error (MSE) of 0.0000431 compared to the Deep Inverse Optimization algorithm, which had an MSE of 0.2473. Additionally, the neural network model achieved an accuracy of 65.9%, while the Deep Inverse Optimization algorithm achieved only 0.81%. In contrast, the Deep Inverse Optimization algorithm demonstrated superior performance in terms of accuracy and computational efficiency for the Linear Program with Chapter 5. Implementation and computational experiments 53 Fixed Feasible Regions. The algorithm achieved perfect accuracy (100%) and zero mean squared error (MSE), indicating that it perfectly recovers the parameters of the Forward Optimization Problem in this scenario. Additionally, it is significantly faster, requiring only 9 minutes compared to the 66 minutes needed by the neural network model. The results of the experiments provide valuable insights into the strengths and limitations of both approaches and highlight the importance of selecting the appropriate model for a given problem. By comparing the performance of the neural network model and the Deep Inverse Optimization algorithm, we can determine which approach is better suited for different scenarios and identify areas for future research and improvement, taking into account that both models are based on gradient-based optimization methods which come with inherent limitations that must be considered. The experiments show that the choice of the model depends heavily on the nature of the problem. For dynamic environments or cases where the Forward Optimization Problem is unknown or difficult to model explicitly, the neural network model is a better choice due to its flexibility and adaptability. In contrast, for problems with fixed feasible regions or known Forward Optimization Problems, the Deep Inverse Optimization algorithm is more suitable, as it can efficiently and accurately recover the parameters of the Forward Optimization Problem. Future work could explore hybrid approaches that combine the strengths of both models, leveraging the flexibility of neural networks for dynamic components and the efficiency of the Deep Inverse Optimization algorithm for fixed structures. Additionally, further research could investigate the scalability of these models to larger and more complex optimization problems, as well as their robustness to noise and uncertainty in the observed decisions. These advancements could further enhance the applicability of Inverse Optimization techniques in real-world scenarios. 54 5.6. Conclusions Appendix A Linear Program with Dynamic Feasible Regions A.1 Part 1: data obtaining and preprocessing [1]: import numpy as np import deep_inv_opt as io import deep_inv_opt.plot as iop import torch import torch.nn as nn from torch.utils.data import Dataset, DataLoader from sklearn.model_selection import ,→train_test_split from diffcp import SolverError import torch import cvxpy as cp from cvxpylayers.torch import CvxpyLayer import contextlib import io as io2 import matplotlib import matplotlib.pyplot as plt matplotlib.rcParams[’figure.max_open_warning’] ,→= 0 # Let the plots flow! %matplotlib inline 55 56 A.1. Part 1: data obtaining and preprocessing [2]: u_train =io.tensor(np.linspace(-1.5,1.5, ,→1024).reshape((-1,1))) [3]: u_train, u_val =train_test_split(u_train, ,→test_size=0.2, random_state=42) u_train, u_test =train_test_split(u_train, ,→test_size=0.15, random_state=42) Now we generate the data from the real problem. [4]: class ExamplePLP(io.ParametricLP): # Generate an LP from a given feature vector u ,→and weight vector w. def generate(self, u, w): c=[[torch.cos(w[0]+w[1]*u)], [torch.sin(w[0]+w[1]*u)]] A_ub =[[-1.0,0.0], [0.0,-1.0], [ w[0], 1+w[1]*u/3]] b_ub =[[ 0.2*w[0]*u], [-0.2*w[1]*u], [ w[0]+ 0.1*u]] return c, A_ub, b_ub, None,None [5]: plp_true =ExamplePLP(weights=[1.0,1.0]) # Generate training targets by solve the true ,→PLP. x_train =torch.cat([io.linprog(*plp_true(ui)). ,→detach().t() for ui in u_train]) # torch.save(x_train, "x_train.pt") x_val =torch.cat([io.linprog(*plp_true(ui)). ,→detach().t() for ui in u_val]) # torch.save(x_val, "x_val.pt") x_test =torch.cat([io.linprog(*plp_true(ui)). ,→detach().t() for ui in u_test]) Appendix A. Linear Program with Dynamic Feasible Regions 57 # torch.save(x_test, "x_test.pt") [34]: u_show =io.tensor(np.linspace(-1.5,1.5,10). ,→reshape((-1,1))) x_show =torch.cat([io.linprog(*plp_true(ui)). ,→detach().t() for ui in u_show]) iop.plot_parametric_linprog(plp_true, u_show, ,→color=[0,0,1], xylim=((-0.5,2.5),(-0.5,2.5)), ,→cxy=(1.2,1.2), show_solutions=True) [6]: # x_val = torch.load("x_val.pt") x_val [6]: tensor([[-0.0079, 0.0079], [ 0.0906, -0.0906], [ 0.0396, -0.0396], 64 A.2. Part 2: model definition and training nn.init.kaiming_normal_(m.weight, ,→nonlinearity=’leaky_relu’)# inicializamos los pesos ,→de la red con Kaiming nn.init.zeros_(m.bias) # inicializamos los bias ,→a 0 # initialize_weights(model) # We load the trained model weights model.load_state_dict(torch.load("model_weights. ,→pth")) [19]: <All keys matched successfully> [20]: def near(rs, x_batch, tol=1e-3): ’’’ rs: Tensor containing the solutions of the ,→LPs x_batch: Tensor containing the desired ,→solutions of the LPs tol: Tolerance to consider two vectors as ,→equal This function calculates the number of LP ,→solutions that are within a distance less than tol from the desired solutions. ’’’ d=torch.sum((rs -x_batch) ** 2, dim=1) return torch.sum(d <tol).item() [21]: tol = 0.0001 def train_loop(dataloader, model, loss_fn, ,→optimizer): model.train() size =len(dataloader.dataset) num_batches =len(dataloader) loss_media = 0.0 accuracy = 0.0 batch_size =dataloader.batch_size Appendix A. Linear Program with Dynamic Feasible Regions 65 for batch, (u_batch, x_batch) in ,→enumerate(dataloader): rs =model(u_batch) loss =loss_fn(rs, x_batch) # Backpropagation and optimization loss.backward() optimizer.step() optimizer.zero_grad() if batch %8==0: loss =loss.item() current =batch *batch_size +batch_size print(f"loss: {loss:>7f}[{current:>5d}/{size: ,→>5d}]") loss_media += loss accuracy += near(rs, x_batch, tol) return loss_media /num_batches, accuracy /size [22]: def val_loop(dataloader, model, loss_fn): model.eval() size=len(dataloader.dataset) num_batches =len(dataloader) val_loss, correct = 0,0 for u_batch, x_batch in dataloader: rs =model(u_batch) val_loss += loss_fn(rs, x_batch).item() correct += near(rs, x_batch, tol) # correct is ,→the number of LP solutions that are within a distance ,→less than tol from the desired solutions. val_loss /= num_batches correct /= size print(f"Validation Error: \n Accuracy: ,→{(100*correct):>0.1f}%, Avg loss: {val_loss:>8f} ,→\n\n") return val_loss, correct 66 A.2. Part 2: model definition and training [23]: val_acc =[] val_loss =[] train_acc =[] train_loss =[] train_acc =torch.load("train_acc.pth") val_acc =torch.load("val_acc.pth") train_loss =torch.load("train_loss.pth") val_loss =torch.load("val_loss.pth") [101]: # Entrenamiento epochs = 1 for tin range(epochs): print(f"Epoch ,→{t+1}\n-------------------------------") loss, accuracy =train_loop(dataloader, model, ,→loss_fn, optimizer) train_acc.append(accuracy) train_loss.append(loss.clone().detach()) print(f"\nTraining Error: \n Accuracy: ,→{(100*accuracy):>0.1f}%, Avg loss: {loss:>8f}\n") loss_val, accuracy_val = ,→val_loop(val_dataloader, model, loss_fn) val_acc.append(accuracy_val) val_loss.append(loss_val) print("Done!") Epoch 1 ------------------------------- loss: 0.000139 [ 16/ 696] loss: 0.000127 [ 144/ 696] loss: 0.008852 [ 272/ 696] loss: 0.000221 [ 400/ 696] loss: 0.000206 [ 528/ 696] loss: 0.000207 [ 656/ 696] Training Error: Accuracy: 30.7%, Avg loss: 0.002772 Validation Error: Accuracy: 69.3%, Avg loss: 0.002392 Appendix A. Linear Program with Dynamic Feasible Regions 67 Done! [24]: fig, axes =plt.subplots(1,2, figsize=(12,5)) # (Accuracy vs Epoch) axes[0].plot(train_acc, label="train") axes[0].plot(val_acc, label="val") axes[0].legend() axes[0].set_xlabel("Epoch") axes[0].set_ylabel("Accuracy") axes[0].set_title("Accuracy vs Epoch") axes[0].grid() axes[1].set_ylim(0,1) # (Loss vs Epoch) axes[1].plot(train_loss, label="train") axes[1].plot(val_loss, label="val") axes[1].legend() axes[1].set_xlabel("Epoch") axes[1].set_ylabel("Loss") axes[1].set_title("Loss vs Epoch") axes[1].grid() axes[1].set_ylim(0,0.04) plt.tight_layout() plt.show() 68 A.2. Part 2: model definition and training [103]: torch.save(model.state_dict(), "model_weights. ,→pth") [104]: # save the accuracy torch.save(train_acc, "train_acc.pth") torch.save(val_acc, "val_acc.pth") torch.save(train_loss, "train_loss.pth") torch.save(val_loss, "val_loss.pth") A.2.1 Evaluation of the model on the test set [23]: model.eval() [23]: ParametricLPNet( (fc): Sequential( (0): Linear(in_features=1, out_features=12, ,→bias=True) (1): ReLU() (2): Linear(in_features=12, out_features=40, ,→bias=True) (3): ReLU() (4): Linear(in_features=40, out_features=150, ,→bias=True) (5): ReLU() (6): Linear(in_features=150, out_features=300, ,→bias=True) (7): ReLU() (8): Linear(in_features=300, out_features=150, ,→bias=True) (9): ReLU() (10): Linear(in_features=150, out_features=90, ,→bias=True) (11): ReLU() (12): Linear(in_features=90, out_features=40, ,→bias=True) (13): Sigmoid() (14): Linear(in_features=40, out_features=14, ,→bias=True) ) ) Appendix A. Linear Program with Dynamic Feasible Regions 69 [24]: u=torch.tensor([[0.25]], dtype=torch.float64) x=torch.cat([io.linprog(*plp_true(ui)). ,→detach().t() for ui in u]) u,x [24]: (tensor([[0.2500]], dtype=torch.float64), tensor([[-0.0500, 0.0500]], dtype=torch. ,→float64)) [25]: x_pred =model(torch.tensor([[0.25]])) x_pred [25]: tensor([[-0.0495, 0.0562]], ,→grad_fn=<StackBackward0>) [26]: x, x_pred, torch.norm(x -x_pred) [26]: (tensor([[-0.0500, 0.0500]], dtype=torch. ,→float64), tensor([[-0.0495, 0.0562]], ,→grad_fn=<StackBackward0>), tensor(0.0063, dtype=torch.float64, ,→grad_fn=<LinalgVectorNormBackward0>)) [27]: val_loop(test_dataloader, model, loss_fn) Validation Error: Accuracy: 65.9%, Avg loss: 0.000431 [27]: (0.00043140000343555585, 0.6585365853658537) Now we plot the results of the model on the test set. [28]: def predict(model, dataloader): model.eval() size=len(dataloader.dataset) num_batches =len(dataloader) x_pred =torch.empty(0,2) for u_batch, x_batch in dataloader: rs =model(u_batch) x_pred =torch.cat((x_pred, rs)) return x_pred.detach() 70 A.2. Part 2: model definition and training [29]: X_pred =predict(model, test_dataloader) X_pred [29]: tensor([[ 7.6126e-01, 2.5680e-01], [ 8.1555e-01, 1.2352e-01], [ 9.9044e-02, -1.0426e-01], ..., [-8.9096e-03, 1.2083e-02], [-7.1218e-02, 8.6232e-02], [ 6.3070e-03, -4.5897e-03]]) [85]: plt.figure(figsize=(10,10)) plt.plot(x_test[:20,0], x_test[:20,1], ’o’, ,→label=’True solutions’, markersize=10) plt.plot(X_pred[:, 0], X_pred[:, 1], ’x’, ,→label=’Predicted solutions’, markersize=15) plt.xlabel(’x’) plt.ylabel(’y’) plt.title(’True vs Predicted solutions’) plt.legend() plt.grid() # marco los limites de la x y la y plt.xlim(-0.2,1.1) plt.ylim(-0.3,1.2) plt.gca().set_aspect(’equal’, adjustable=’box’) ,→# esto es para que los ejes tengan la misma escala plt.tight_layout() plt.show() plt.savefig("true_vs_predicted_nn.png") Appendix A. Linear Program with Dynamic Feasible Regions 71 <Figure size 640x480 with 0 Axes> A.3 Part 3: Deep IO model [30]: plp_learn =ExamplePLP([1.5,1.2]) [ ]: u_show =io.tensor(np.linspace(-1.5,1.5,10). ,→reshape((-1,1))) 72 A.3. Part 3: Deep IO model x_show =torch.cat([io.linprog(*plp_true(ui)). ,→detach().t() for ui in u_show]) # Data set. Black points are the real ,→solutions, blue points are the solutions of the ,→plp_learn iop.plot_targets(x_show, markersize=13) iop.plot_parametric_linprog(plp_learn, u_show, ,→color=[0,0,1], xylim=((-0.5,2.5),(-0.5,2.5)), ,→cxy=(1.2,1.2), show_solutions=True) [78]: u_show =io.tensor(np.linspace(1,1.5,10). ,→reshape((-1,1))) x_show =torch.cat([io.linprog(*plp_true(ui)). ,→detach().t() for ui in u_show]) Appendix A. Linear Program with Dynamic Feasible Regions 73 # Data set. Black points are the real ,→solutions, blue points are the solutions of the ,→plp_learn iop.plot_targets(x_show, markersize=13) iop.plot_parametric_linprog(plp_learn, u_show, ,→color=[0,0,1], xylim=((-0.5,2.5),(-0.5,2.5)), ,→cxy=(1.2,1.2), show_solutions=True) [58]: io.inverse_parametric_linprog(u_train, x_train, ,→plp_learn, max_steps=10, callback=io. ,→inverse_parametric_linprog_step_printer()) inverse_parametric_linprog[0001]: loss=0.360737 ,→weights=[1.5000 1.2000] inverse_parametric_linprog[0002]: loss=0.350147 ,→weights=[1.3332 0.6538] 80 B.1. Part 1: data obtaining and preprocessing [2]: u_train =io.tensor(np.linspace(0,6,1024). ,→reshape((-1,1))) u_train [2]: tensor([[0.0000e+00], [5.8651e-03], [1.1730e-02], ..., [5.9883e+00], [5.9941e+00], [6.0000e+00]], dtype=torch.float64) [3]: u_train, u_val =train_test_split(u_train, ,→test_size=0.2, random_state=42) u_train, u_test =train_test_split(u_train, ,→test_size=0.15, random_state=42) [4]: u_train [4]: tensor([[3.3255e+00], [4.7918e+00], [5.9062e+00], ... [4.0000e+00], [1.0029e+00], [3.5425e+00]], dtype=torch.float64) [5]: u_val [5]: tensor([[3.0792], [2.0938], [2.6041], ... [3.0968], [1.7243], [4.3695]], dtype=torch.float64) [6]: u_test [6]: tensor([[5.4721], [5.4428], Appendix B. Linear Program with Fixed Feasible Regions 81 [0.7625], ... [3.0616], [2.9384], [5.3959]], dtype=torch.float64) Now we generate the data from the real problem. [7]: class ExamplePLP(io.ParametricLP): # Generate an LP from a given feature vector u ,→and weight vector w. def generate(self, u, w): c=[[torch.cos(w +u**2/2)], [torch.sin(w +u**2/2)]] A_ub =[[ 0.0,1.0], [0.0,-1.0], [1.0,0.0], [-1.0,0.0], [1.0,1.0] ] b_ub =[[ 60.0 ], [0.0 ], [60.0 ], [0.0 ], [100.0 ] ] return c, A_ub, b_ub, None,None [8]: plp_true =ExamplePLP(weights=[0.8]) [10]: u_show =io.tensor(np.linspace(0,6,8). ,→reshape((-1,1))) xylim =((-4,65), (-4,65)) cxy =(55,55) iop.plot_parametric_linprog(plp_true, u_show, ,→color=[0,0,1], xylim=xylim, cxy=cxy, ,→show_solutions=True) 82 B.1. Part 1: data obtaining and preprocessing [11]: u_show =io.tensor(np.linspace(0,6,8). ,→reshape((-1,1))) xylim =((53,57), (53,57)) cxy =(55,55) iop.plot_parametric_linprog(plp_true, u_show, ,→color=[0,0,1], xylim=xylim, cxy=cxy, ,→show_solutions=True) Appendix B. Linear Program with Fixed Feasible Regions 83 [12]: # Generate training targets by solve the true ,→PLP. x_train =torch.cat([io.linprog(*plp_true(ui)). ,→detach().t() for ui in u_train]) # torch.save(x_train, "x_train.pt") x_val =torch.cat([io.linprog(*plp_true(ui)). ,→detach().t() for ui in u_val]) # torch.save(x_val, "x_val.pt") x_test =torch.cat([io.linprog(*plp_true(ui)). ,→detach().t() for ui in u_test]) # torch.save(x_test, "x_test.pt") [13]: # x_val = torch.load("x_val.pt") x_val 84 B.2. Part 2: model definition and training [13]: tensor([[3.1065e-05, 6.0000e+01], [6.0000e+01, 1.3445e-04], [4.0000e+01, 6.0000e+01], ..., [3.9506e-05, 6.0000e+01], [6.0000e+01, 4.0443e-05], [4.0000e+01, 6.0000e+01]], dtype=torch. ,→float64) [14]: # x_train = torch.load("x_train.pt") x_train [14]: tensor([[1.5130e-05, 3.2630e-04], [2.3855e-05, 6.0000e+01], [3.7182e-05, 6.0000e+01], ..., [6.0000e+01, 2.5838e-05], [5.2023e-05, 1.4278e-05], [1.9593e-05, 1.9354e-05]], dtype=torch. ,→float64) [15]: # x_test = torch.load("x_test.pt") x_test [15]: tensor([[6.0000e+01, 4.0000e+01], [6.0000e+01, 2.0927e-04], [2.9810e-05, 1.5524e-05], ... [2.8643e-05, 6.0000e+01], [3.8379e-05, 6.0000e+01], [6.0000e+01, 4.0141e-05]], dtype=torch. ,→float64) B.2 Part 2: model definition and training [16]: # Check if we are using a GPU or CPU device =torch.accelerator. ,→current_accelerator().type if torch.accelerator. ,→is_available() else "cpu" print(f"Using {device}device") Using cuda device Appendix B. Linear Program with Fixed Feasible Regions 85 [17]: learning_rate = 1e-3 batch_size = 16 [18]: # Dataset and DataLoader definition class UDataset(Dataset): def __init__(self, data, targets): self.data =data.clone().to(dtype=torch.float32) self.targets =targets.clone().to(dtype=torch. ,→float32) def __len__(self): return len(self.data) def __getitem__(self, idx): return self.data[idx], self.targets[idx] # Dataset (u, x) dataset =UDataset(u_train, x_train) dataloader =DataLoader(dataset, ,→batch_size=batch_size, shuffle=True) [19]: val_dataset =UDataset(u_val, x_val) val_dataloader =DataLoader(val_dataset, ,→batch_size=batch_size, shuffle=True) test_dataset =UDataset(u_test, x_test) test_dataloader =DataLoader(test_dataset, ,→batch_size=batch_size, shuffle=True) [20]: def gradient_descent_solver(c, A, b, lr=0.01, ,→max_iter=1000, tol=1e-6, M=1000.0): """ Solve a linear optimization problem with ,→constraints using gradient descent. Parameters: - c: Cost vector (n,) - A: Constraint matrix (m, n) - b: Constraint vector (m,) - lr: Learning rate - max_iter: Maximum number of iterations - tol: Convergence tolerance 86 B.2. Part 2: model definition and training Returns: - x: Optimal solution found """ n=c.shape[0] x=torch.zeros(n, dtype=c.dtype, ,→requires_grad=True) optimizer =torch.optim.SGD([x], lr=lr) for _in range(max_iter): optimizer.zero_grad() objective =torch.dot(c, x) +M*torch. ,→sum(torch.relu(A @x-b)) # relu(x) = max(0, x) objective.backward(retain_graph=True) optimizer.step() if torch.norm(x.grad) <tol: break return x def newton_solver(c, A, b, max_iter=100, ,→tol=1e-6, M=1000.0): """ Solve a linear optimization problem with ,→constraints using the Newton method. Parameters: - c: Cost vector (n,) - A: Constraint matrix (m, n) - b: Constraint vector (m,) - max_iter: Maximum number of iterations - tol: Convergence tolerance Returns: - x: Optimal solution found """ n=c.shape[0] x=torch.zeros(n, dtype=c.dtype, ,→requires_grad=True) for _in range(max_iter): Appendix B. Linear Program with Fixed Feasible Regions 87 loss =torch.dot(c, x) +M*torch.sum(torch. ,→relu(A @x-b)) # Gradient and Hessian grad =torch.autograd.grad(loss, x, ,→create_graph=True)[0] hess =torch.autograd.functional.hessian(lambda ,→y: torch.dot(c, y) +M*torch.sum(torch.relu(A @y- ,→b)), x) # Newton step: Δx = -H^-1 *grad try: delta_x =torch.linalg.solve(hess, -grad) except RuntimeError: break # Break if the Hessian is singular # Actualize x x=x+delta_x # Break if converged if torch.norm(delta_x) <tol: break return x [21]: def solver(c_, A_, b_): try: M= 1000.0 m,n=A_.shape A=cp.Parameter((m, n)) b=cp.Parameter(m) c=cp.Parameter(n) x=cp.Variable(n) obj =cp.Minimize(c.T@x+M*cp.sum(cp.pos(A ,→@x-b))) # cp.pos = max(0, x) cons =[0*x>= 0] prob =cp.Problem(obj, cons) 88 B.2. Part 2: model definition and training layer =CvxpyLayer(prob, parameters=[c, A, b], ,→variables=[x]) with io2.StringIO() as buf, contextlib. ,→redirect_stdout(buf): solution, =layer(c_, A_, b_) return solution except SolverError: return newton_solver(c_, A_, b_) [22]: # Define the model class ParametricLPNet(nn.Module): def __init__(self): super(ParametricLPNet, self).__init__() self.fc =nn.Sequential( nn.Linear(1,12), nn.ReLU(), nn.Linear(12,40), nn.ReLU(), nn.Linear(40,150), nn.ReLU(), nn.Linear(150,300), nn.ReLU(), nn.Linear(300,150), nn.ReLU(), nn.Linear(150,90), nn.ReLU(), nn.Linear(90,40), nn.Sigmoid(), nn.Linear(40,14) ) def forward(self, u): output =self.fc(u) c=output[:, 0:2] A=output[:, 2:10].reshape(-1,4,2) b=output[:, 10:14] return torch.stack(list(map(solver, c, A, b))) [23]: loss_fn =nn.MSELoss() Appendix B. Linear Program with Fixed Feasible Regions 89 [24]: model =ParametricLPNet() optimizer =torch.optim.Adam(model. ,→parameters(), lr=learning_rate) # optimizer = torch.optim.SGD(model. ,→parameters(), lr=learning_rate) # elegir una de las ,→dos [25]: model [25]: ParametricLPNet( (fc): Sequential( (0): Linear(in_features=1, out_features=12, ,→bias=True) (1): ReLU() (2): Linear(in_features=12, out_features=40, ,→bias=True) (3): ReLU() (4): Linear(in_features=40, out_features=150, ,→bias=True) (5): ReLU() (6): Linear(in_features=150, out_features=300, ,→bias=True) (7): ReLU() (8): Linear(in_features=300, out_features=150, ,→bias=True) (9): ReLU() (10): Linear(in_features=150, out_features=90, ,→bias=True) (11): ReLU() (12): Linear(in_features=90, out_features=40, ,→bias=True) (13): Sigmoid() (14): Linear(in_features=40, out_features=14, ,→bias=True) ) ) [26]: # Initialize the weights of the model def initialize_weights(m): if isinstance(m, nn.Linear): 96 B.2. Part 2: model definition and training [36]: X_pred =predict(model, test_dataloader) X_pred [36]: tensor([[ 5.8926e+01, 1.8113e+01], [ 5.9214e+01, 5.4558e-01], [ 1.5126e+01, 5.9356e+01], ..., [ 2.5615e+00, 5.9404e+01], [ 4.9921e+01, -6.5277e-01]]) [44]: plt.figure(figsize=(10,10)) plt.plot(x_test[:20,0], x_test[:20,1], ’o’, ,→label=’True solutions’, markersize=10) plt.plot(X_pred[:, 0], X_pred[:, 1], ’x’, ,→label=’Predicted solutions’, markersize=15) plt.plot((0,0), (0,60), ’k--’, linewidth=2) plt.plot((0,40), (60,60), ’k--’, linewidth=2) plt.plot((40,60), (60,40), ’k--’, linewidth=2) plt.plot((60,60), (40,0), ’k--’, linewidth=2) plt.plot((60,0), (0,0), ’k--’, linewidth=2) plt.xlabel(’x’) plt.ylabel(’y’) plt.title(’True vs Predicted solutions’) plt.legend() plt.grid() # marco los limites de la x y la y plt.xlim(-10,70) plt.ylim(-10,70) plt.gca().set_aspect(’equal’, adjustable=’box’) ,→# esto es para que los ejes tengan la misma escala plt.tight_layout() plt.show() plt.savefig("true_vs_predicted_nn.png") Appendix B. Linear Program with Fixed Feasible Regions 97 <Figure size 640x480 with 0 Axes> B.3 Part 3: Deep IO model [38]: plp_learn =ExamplePLP([4.5]) [39]: u_show =io.tensor(np.linspace(0,6,10). ,→reshape((-1,1))) x_show =torch.cat([io.linprog(*plp_true(ui)). ,→detach().t() for ui in u_show]) 98 B.3. Part 3: Deep IO model [40]: # Data set. Black points are the real ,→solutions, blue points are the solutions of the ,→plp_learn iop.plot_targets(x_show, markersize=13) iop.plot_parametric_linprog(plp_learn, u_show, ,→color=[0,0,1], xylim=((-5,65),(-5,65)), ,→cxy=(55,55), show_solutions=True) [85]: io.inverse_parametric_linprog(u_train, x_train, ,→plp_learn, max_steps=10, callback=io. ,→inverse_parametric_linprog_step_printer()) inverse_parametric_linprog[0001]: loss=5217.176260 ,→weights=[4.5000] inverse_parametric_linprog[0002]: loss=5121.833691 ,→weights=[116.2986] Appendix B. Linear Program with Fixed Feasible Regions 99 inverse_parametric_linprog[0003]: loss=2309.924151 ,→weights=[112.7349] inverse_parametric_linprog[0004]: loss=20.648341 ,→weights=[16004.0603] inverse_parametric_linprog[0005]: loss=2.253935 ,→weights=[16004.0728] inverse_parametric_linprog[0006]: loss=0.000091 ,→weights=[16004.0748] inverse_parametric_linprog[0007]: loss=0.000091 ,→weights=[16004.0748] inverse_parametric_linprog[0008]: loss=0.000091 ,→weights=[16004.0748] inverse_parametric_linprog[0009]: loss=0.000091 ,→weights=[16004.0748] inverse_parametric_linprog[0010]: loss=0.000091 ,→weights=[16004.0748] inverse_parametric_linprog[done]: loss=0.000091 ,→weights=[16004.0748] [85]: (<__main__.ExamplePLP at 0x751b21bec470>, tensor(9.0747e-05, dtype=torch.float64, ,→grad_fn=<MeanBackward0>), tensor([[1.5131e-05, 3.1417e-04], [2.3842e-05, 6.0000e+01], [3.7136e-05, 6.0000e+01], ..., [6.0000e+01, 2.3598e-05], [5.2365e-05, 1.4271e-05], [1.9629e-05, 1.9319e-05]], dtype=torch. ,→float64, grad_fn=<CatBackward0>)) [41]: # Plot the new plp_learn, to show that the ,→solutions (blue circles) now line up with the ,→observed targets (black circles). iop.plot_targets(x_show, markersize=13) iop.plot_parametric_linprog(plp_learn, u_show, ,→color=[0,0,1], xylim=((-5,65),(-5,65)), ,→cxy=(55,55), show_solutions=True) 100 B.3. Part 3: Deep IO model [42]: w= 16004.0748 estimated_plp =ExamplePLP([w]) accy =[torch.norm(x -io. ,→linprog(*estimated_plp(u)).t())<0.001 for u,xin ,→zip(u_test, x_test)] lss =[torch.norm(x -io. ,→linprog(*estimated_plp(u)).t()) for u,xin ,→zip(u_test, x_test)] print(f"Train accuracy: {100*sum(accy)/ ,→len(accy):.2f}%") print(f"Train avg loss: {sum(lss)/len(lss):. ,→2f}") Train accuracy: 100.00% Train avg loss: 0.00 Appendix B. Linear Program with Fixed Feasible Regions 101 [43]: X_pred_io =torch.cat([io. ,→linprog(*estimated_plp(u)).t().detach() for uin ,→u_test]) X_pred_io [43]: tensor([[6.0000e+01, 4.0000e+01], [6.0000e+01, 2.1331e-04], [2.9915e-05, 1.5509e-05], ..., [2.8590e-05, 6.0000e+01], [3.8216e-05, 6.0000e+01], [6.0000e+01, 4.0342e-05]], dtype=torch. ,→float64) [46]: plt.figure(figsize=(10,10)) plt.plot(x_test[:20,0], x_test[:20,1], ’o’, ,→label=’True solutions’, markersize=10) plt.plot(X_pred_io[:, 0], X_pred_io[:, 1], ’x’, ,→label=’Predicted solutions’, markersize=15) plt.plot((0,0), (0,60), ’k--’, linewidth=2) plt.plot((0,40), (60,60), ’k--’, linewidth=2) plt.plot((40,60), (60,40), ’k--’, linewidth=2) plt.plot((60,60), (40,0), ’k--’, linewidth=2) plt.plot((60,0), (0,0), ’k--’, linewidth=2) plt.xlabel(’x’) plt.ylabel(’y’) plt.title(’True vs Predicted solutions’) plt.legend() plt.grid() # marco los limites de la x y la y plt.xlim(-10,70) plt.ylim(-10,70) plt.gca().set_aspect(’equal’, adjustable=’box’) ,→# esto es para que los ejes tengan la misma escala plt.tight_layout() plt.show() plt.savefig("true_vs_predicted_io.png") 102 B.3. Part 3: Deep IO model <Figure size 640x480 with 0 Axes> Bibliography [1] Omar Besbes, Yuri Fonseca, and Ilan Lobel. Contextual inverse optimization: Offline and online learning. Operations Research, 2023. [2] Timothy CY Chan and Neal Kaw. Inverse optimization for the recovery of constraint parameters. European Journal of Operational Research, 282(2):415–427, 2020. [3] Timothy CY Chan, Taewoo Lee, and Daria Terekhov. Inverse optimization: Closed-form solutions, geometry, and goodness of fit. Management Science, 65(3):1115–1135, 2019. [4] Timothy CY Chan, Rafid Mahmood, and Ian Yihang Zhu. Inverse optimization: Theory and applications. Operations Research, 2023. [5] Jairo Escánez. Fdp experiments repository. https://github.com/ jairoescanez/tfg_experiments, 2024. GitHub repository containing the implementation and experiments for the FDP. [6] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016. http://www.deeplearningbook.org. [7] Garud Iyengar and Wanmo Kang. Inverse conic programming with applications. Operations Research Letters, 33(3):319–330, 2005. [8] Amitha Mathew, P. Amudha, and S. Sivakumari. Deep learning techniques: An overview. In Aboul Ella Hassanien, Roheet Bhatnagar, and Ashraf Darwish, editors, Advanced Machine Learning Technologies and Applications, pages 599– 608, Singapore, 2021. Springer Singapore. [9] Jorge J Moré and David J Thuente. Line search algorithms with guaranteed sufficient decrease. ACM Transactions on Mathematical Software (TOMS), 20(3):286–307, 1994. [10] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. In NIPS 2017 Workshop on Autodiff, 2017. 103 104 Bibliography [11] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019. [12] Daria Terekhov Yingcong Tan, Andrew Delong. Deep Inverse Optimization, pages 540–556. Springer, Department of Mechanical, Industrial and Aerospace Engineering, Concordia University, Montreal, Canada, 2019.