Landscape Surrogate: Learning Decision Losses for Mathematical Optimization
Under Partial Information
Arman Zharmagambetov 1 Brandon Amos 1 Aaron Ferber 2 Taoan Huang 2 Bistra Dilkina 2 Yuandong Tian 1

Abstractin the problem definition. For example, combinatorial problems involving nonlinear objectives are generally hard toaddress. One possible approach could be learning so-called
linear surrogate costs (Ferber et al., 2022) that guide an
efficient linear solver towards high quality solutions for theoriginal hard nonlinear problem. This automatically finds asurrogate mixed integer linear program (MILP), for which
relatively efficient solvers exist (Gurobi, 2019). Anotherexample is the smart predict+optimize framework (a.k.a.
decision-focused learning) (Elmachtoub & Grigas, 2017;
Wilder et al., 2020) where some problem parameters are unknown at test time and must be inferred from the observed
input using a parametric mapping (e.g., neural nets).

Recent works in learning-integrated optimization
have shown promise in settings where the optimization problem is only partially observed orwhere general-purpose optimizers perform poorly
without expert tuning. By learning an optimizer g
to tackle these challenging problems with f as theobjective, the optimization process can be substantially accelerated by leveraging past experience.
Training the optimizer can be done with supervision from known optimal solutions (not always
available) or implicitly by optimizing the compound function f ◦ g, but the implicit approachis slow and challenging due to frequent calls tothe optimizer and sparse gradients, particularly
for combinatorial solvers. To address these challenges, we propose using a smooth and learnable
Landscape Surrogate M instead of f ◦ g. Thissurrogate can be computed faster than g, provides
dense and smooth gradients during training, cangeneralize to unseen optimization problems, andis efficiently learned via alternating optimization.
We test our approach on both synthetic problems
and real-world problems, achieving comparable
or superior objective values compared to state-ofthe-art baselines while reducing the number ofcalls to g. Notably, our approach outperforms
existing methods for computationally expensive
high-dimensional problems.

Despite having completely different settings and purposes,
what is common among learning surrogate costs, smart
predict+optimize, and other integrations of learning and optimization, is the need to learn a certain target mapping toestimate the parameters of a latent optimization problem.
This makes the optimization problem well-defined, easy toaddress, or both. In this work, we draw general connections
between different problem families and combine them into a
unified framework. The core idea (section 1) is to formulate
the learning problem via constructing a compound functionf ◦ g that includes a parametric solver g and the original objective f . To the best of our knowledge, this paper is the firstto propose a generic optimization formulation (section 1)
for these types of problems.
Minimizing this new compound function f ◦g is a nontrivial
task as it requires differentiation through the argmin operator. Although various methods have been proposed to tackle
this issue (Amos & Kolter, 2017; Agrawal et al., 2019), they
have several limitations. First, they are not directly applicable to combinatorial optimization problems, which have 0
gradient almost everywhere, and thus require various computationally expensive approximations (Pogančic̀ et al., 2020;
Wilder et al., 2020; Ferber et al., 2020; Wang et al., 2019).
Second, even if the decision variables are continuous, thesolution space (i.e., argmin) may be discontinuous. Somepapers (Donti et al., 2017; Gould et al., 2016) discuss the
fully continuous domain but typically involve computing theJacobian matrix, which leads to scalability issues. Furthermore, in some cases, an explicit expression for the objective
may not be given, and we may only have black-box access

Optimization problems in various settings have been widely
studied, and numerous methods exist to solve them (Korte &Vygen, 2018; Nocedal & Wright, 2006). Although the literature on this topic is immense, real-world applications consider settings that are nontrivial or extremely costly to solve.
The issue often stems from uncertainty in the objective or*

Equal contribution 1 Meta AI (FAIR) 2 University of Southern
California. Correspondence to: Arman Zharmagambetov <armanz@meta.com>, Yuandong Tian <yuandong@meta.com>.
Published at the Differentiable Almost Everything Workshop of the
40 th International Conference on Machine Learning, Honolulu,
Hawaii, USA. July 2023. Copyright 2023 by the author(s).

1

LANCER: Learning Decision Losses for Mathematical Optimization Under Partial Information

as the observable descriptions {yi } ⊆ Y, while for thetest instance, we only know its observable description ytest .
Given this setting, we propose the following general training
procedure on a training set Dtrain := {(yi , zi )}N
i=1 :min L(Y, Z) :=Figure 1. Overview of our proposed framework LANCER. We replace the non-convex and often non-differentiable function f ◦ gwith landscape surrogate M and use it to learn the target mappingcθ . The current output of cθ is then used to evaluate f and torefine M. This procedure is repeated in alternating optimization
fashion.

θ

Our proposed training procedure is general and covers many
previous works that rely on either fully or partially observed
problem information:• In Smart Predict+Optimize (P+O), f belongs to a specific function family (e.g., linear or quadratic programs).
The full problem description z includes objective coefficients, but we only have access to noisy versions of themin y. Then the goal in P+O is to identify a mapping cθ(e.g. a neural net) so that a downstream solver outputs ahigh quality solution: gθ (y) = arg minx∈Ω f (x; cθ (y)).
Here arg minx∈Ω f can often be solved with standard
approaches, and the main challenge is to estimate theproblem description accurately (w.r.t. eq. (2)).

We will make the implementation of LANCER available
at https://github.com/facebookresearch/
LANCER.

• Learning surrogate costs for MINLP. When f is a general nonlinear objective (but y = z is fully observed),
computing arg minx∈Ω f also becomes non-trivial, especially if x is in combinatorial spaces. Such problems arecommonly referred as mixed integer nonlinear programming (MINLP). To leverage the power of linear combinatorial solvers, SurCo (Ferber et al., 2022) sets the learnable
solver to be gθ (y) = arg minx∈Ω x⊤ cθ (y), which is alinear solver and does not include the nonlinear function
f at all. Intuitively, this models the complexity of f by
the learned surrogate cost cθ , which is parameterized bya neural network.

1. A Unified Training Procedure
Consider the following optimization problem:
x∈Ω

(2)

Here gθ : Y 7→ Ω is a learnable solver that returns a highquality solution for objective f directly from the observable problem description yi . θ are the learnable solver’s
parameters. Once gθ is learned, we can solve new problem
instances with observable description ytest by either calling
xtest = gθ (ytest ) to get a reasonable solution, or continue
to optimize Eqn. 1 using x = xtest as an initial solution.

These limitations motivate Landscape Surrogate losses(LANCER), a unified model for solving coupled learningand optimization problems. LANCER accurately approximates the behavior of the compound function f ◦ g, allowing us to use it to learn our target parametric mapping (seefig. 1). Furthermore, we propose an efficient alternating
optimization algorithm that jointly trains LANCER and theparameters of the target mapping. Our motivation is thattraining LANCER in this manner better distills task-specificknowledge, resulting in improved overall performance.

s.t.

f (gθ (yi ); zi )i=1

to the objective function, preventing straightforward end-toend backpropagation. Some works discuss derivative-free
approaches but they rely on frequent calls to the solver g(Shah et al., 2022).

min f (x; z)

N
X

(1)

x

where f is the function to be optimized, x ∈ Ω are thedecision variables that must lie in the feasible region, typically specified by (non)linear (in)equalities and possibly
integer constraints, and z ∈ Z is the problem description.
For example, if f is to find a shortest path in a graph, thenx is the path to be optimized, and z represents the pairwise
distances in the formulation.

2. LANCER: Learning Landscape Surrogate
Losses

Ideally, we would like to have an optimizer that can (1)deal with the complexity of the loss function landscape (2)leverage past experience in solving similar problems, and(3) can deal with a partial information setting, in which only
an observable problem description y can be seen but not thetrue problem description z.

While multiple approaches exist to learn θ, at each step of
the training process, we need to call a solver to evaluategθ , which can be computationally expensive. Furthermore,
typically gθ is learned via gradient descent of Eqn. 2, which
involves backpropagating through the solver. One issue of
this procedure is that the gradient is non–zero only at certain locations, which makes the gradient-based optimizationdifficult.

To design such an optimizer, we consider the following
setting: assume that for the training instances, we haveaccess to the full problem descriptions {zi } ⊆ Z, as well
2

LANCER: Learning Decision Losses for Mathematical Optimization Under Partial Information
Shortest Path

One question arises: can we model the composite functionf ◦ gθ jointly? The intuition here is that while gθ can be
hard to compute, f ◦ gθ can be smooth to model, since f
can be smooth around the solution provided by gθ . If wemodel f ◦ gθ locally by a landscape surrogate model M,
and optimize directly on the local landscape of M, then thetarget mapping cθ can be trained without running expensive
solvers:
min M(Y, Z) :=θNX

M (cθ (yi ); zi ) .

Figure 2. Normalized test regret (lower is better) for different
P+O methods: 2-stage, SPO+ (Elmachtoub & Grigas, 2017),
DBB (Pogančic̀ et al., 2020), LODLs (Shah et al., 2022) and ours
(LANCER). Overlaid dark green bars (right) indicate the warm
started method from 2stg. DBB performs considerably worse on
the right benchmark and is cut off on the y-axis.

(3)

i=1

Note that M directly depends on cθ (not on gθ ). Obviously,
M cannot be any arbitrary function. Rather it should satisfy
certain conditions: 1) capture a task-specific loss f ◦ gθ ; 2)
be differentiable and smooth. The primary advantage is that
we can avoid backpropagating through the solver or eventhrough f . Moreover, Mw is typically high dimensional
and potentially can make the learning problem for cθ mucheasier. The question is how to obtain such a model M?
One way is to parameterize it and formulate the learning
problem:

Reusing landscape surrogate model Mw Once Algorithm 1 finishes, we usually discard Mw as it is an intermediate result of the algorithm, and we only retain cθ (andsolver g) for model deployment. However, we have foundthrough empirical exploration that the learned surrogate loss
Mw can be reused for a range of problems, increasing theversatility of the approach. This is particularly advantageous for SurCo setting, where we handle one instance at atime. In this scenario, we utilize the trained Mw for unseen
test instances by executing only the θ-step of Algorithm 1.
The main advantage of this extension is that it eliminates
the need for access to the solver g, leading to significant
deployment runtime improvements.

min ∥Mw (Y, Z; θ ∗ ) − L(Y, Z; θ ∗ )∥ws.t.

θ ∗ ∈ argminθ Mw (Y, Z; θ)

Multidimensional Knapsack(4)

where we add θ as an argument to explicitly emphasize
the dependence of the loss function on the target mapping c. Note that M does not need to be accurate overthe entire domain, but only needs to be accurate aroundthe optimal solution θ ∗ . In other words, Mw serves as asurrogate loss that approximates L in a certain landscape:Mw (Y, Z, θ) ∼ L(Y, Z, θ).

3. Experiments
We validate LANCER in two settings: smart predict+optimize and learning surrogate costs for MINLP. Overall, LANCER exhibits superior or comparable objective values while maintaining efficient runtime. Additional experiments and ablation studies can be found in Appendix C.

Notice that Eqn. 4 is an instance of bi-level optimization.
Established methods from the bi-level optimization literature, such as (Gould et al., 2016; Ye et al., 2022), could
potentially be used, but most of them still rely on ∇θ L(or even ∇2θ ), which involves differentiating through thesolver. To overcome this issue, we propose a simple andgeneric algorithm 1, which is based on alternating optimization (high-level idea is depicted in fig. 1). The core idea
is to simultaneously learn both mappings (Mw and cθ ) to
explore different solution spaces. By improving our target model cθ , we obtain better estimates of the surrogate
loss around the solution, and a better estimator Mw leads
to better optimization of the desired loss L. The use ofalternating optimization helps both mappings reach a common goal. Note that the algorithm avoids backpropagating
through the solver or even through f . The only requirement is evaluating the function f at the solution of g, which
can be achieved by black-box solver access. As a result,
this approach eliminates the complexity and computational
expense associated with computing derivatives of combinatorial solvers, making it a more efficient and practicalsolution.

3.1. Synthetic data
The shortest path (SP) and multidimensional knapsack(MKS) are both classic problems in combinatorial optimization with broad practical applications. In this setting, we
consider a scenario where problem parameters z, such asgraph edge weights and item prices, cannot be directly observed during test time, and instead need to be estimatedfrom y via learnable mapping z = cθ (y). That is, we consider smart P+O setting. Experimental setup can be foundin Appendix B.1.
The results are summarized in fig. 2. We report the normalized regret as described in (Tang & Khalil, 2022). The
findings indicate that LANCER and SPO+ consistently outperform the two-stage baseline, particularly when considering the warm start. As SPO+ is specifically designed forlinear programs, it provides informative gradients, making it
a robust baseline. Even in MKS, where theorems proposed
3

LANCER: Learning Decision Losses for Mathematical Optimization Under Partial Information

Table 1. Portfolio selection normalized test decision loss (lower isbetter).
MethodTest DL
Random1
Optimal02–Stage
0.57 ± 0.02
LODLs (Shah et al., 2022)
0.55 ± 0.02
MDFL (Wilder et al., 2020) 0.52 ± 0.01
LANCER
0.53 ± 0.02

in (Elmachtoub & Grigas, 2017) are no longer applicable,
SPO+ performs decently with minimal tuning effort. The
DBB approach, however, demonstrates unsatisfactory default performance but can yield favorable outcomes withproper initialization and tuning (see the right plot). Interestingly, the other P+O baselines, initialized randomly, wereunable to outperform a naive 2stg in both benchmarks.

Figure 3. Objective (lower is better) and deployment runtime for
combinatorial portfolio selection problem. For LANCER–zero and
SurCo–zero, numbers at each point correspond to the number of
iterations.

LANCER achieves superior performance in both tasks, witha noticeable advantage in MKS. This may be attributed
to the high dimension of the MKS problem and the large
feature space (y). One possible explanation is that the sparse
gradients of the derivative-based method make the learning
problem harder, whereas LANCER models the landscape off ◦ g, providing informative gradients for cθ .

description z is given at train/test time.
Results are shown in fig. 3. We first tried to solve the given
MINLP exactly via SCIP. However, it fails to produce theoptimal solution within 1 hour time limit and we report
the best incumbent feasible solution. MIQP (blue squares)
and MILP (blue triangles) approximations overlook the coskewness and non-linear terms, respectively. For LANCER
and SurCo, we present results for two scenarios: learning
the linear cost vector c directly (zero) for each instance, anda parameterized version cθ (z) (prior). The main distinctionof “prior” is that no learning occurs during test time. Consequently, the deployment runtime is similar to that of the
MILP approximation, but LANCER–prior produces slightly
superior solutions. Remarkably, LANCER–zero achieves
significantly better loss values, surpassing all other methods. Although it takes longer to run, the runtime remains
manageable, and importantly, the solution quality improves
with an increasing number of iterations.

3.2. Real-world use case: the quadratic programming
In this study, we tackle the classical quadratic (Markowitz,
1952) portfolio selection problem. We use real-world
data from Quandl (Quandl) and follow the setup describedin Shah et al. (2022). The prediction task leverages eachstock’s historical data y to forecast future prices z, which
are then utilized to solve the QP (i.e., P+O setting). The
predictor is the MLP with 1 hidden layer of size 500. The remaining setup description can be found in Appendix B.2.1.
Results Table 1 summarizes our results. We report thenormalized decision loss (i.e., normalized Eqn. (2)) on test
data. Since the problem is smooth and exact gradientscan be calculated, MDFL achieves the best performanceclosely followed by the LANCER. The remaining results arein agreement with (Shah et al., 2022). While LANCER does
not achieve the best overall performance, it does so using
a significantly smaller number of calls to a solver, as we
discuss in more detail in Appendix C.2.

4. Conclusion
This paper makes a dual contribution: 1) we derive a unified
training procedure to address various coupled learning andoptimization settings, including smart P+O and surrogate
learning; 2) we propose an effective and powerful method
called LANCER to tackle this training procedure. LANCER
offers several advantages over existing literature, such asversatility, differentiability, and efficiency. Experimental results validate these advantages, leading to significant performance improvements. One potential drawback is the complexity of tuning M, requiring model selection and training.
However, future research directions include addressing thisdrawback and exploring extensions of LANCER, such as
applying it to fully black box f scenarios.

3.3. Real-world use case: combinatorial portfolio
selection with third-order objective
The convex portfolio optimization problem discussed in theprevious section 3.2 is unable to capture desirable properties
such as logical constraints (Bertsimas et al., 1999; Ferber
et al., 2020), or higher-order loss functions (Harvey et al.,2010) that integrate metrics like co-skewness to better modelrisk. We use the Quandl (Quandl) data (see Appendix B.2.2
for setup details). Here, we assume that the full problem
4

LANCER: Learning Decision Losses for Mathematical Optimization Under Partial Information

References

Gurobi. Gurobi optimizer reference manual, 2019.

Achterberg, T. SCIP: Solving constraint integer programs. Mathematical Programming Computation, 1(1):1–41, July 2009. ISSN 1867-2957. doi: 10.1007/
s12532-008-0001-1.

Harvey, C. R., Liechty, J. C., Liechty, M. W., and Muller,
P. Portfolio selection with higher moments. Quantitative
Finance, 10:469–485, 2010.
Korte, B. and Vygen, J. Combinatorial Optimization: Theory and Algorithms. Number 21 in Algorithms and Combinatorics. Springer-Verlag, sixth edition, 2018.

Agrawal, A., Amos, B., Barratt, S., Boyd, S., Diamond,S., and Kolter, J. Z. Differentiable convex optimization
layers. In Wallach, H., Larochelle, H., Beygelzimer, A.,d’Alché Buc, F., Fox, E., and Garnett, R. (eds.), Advancesin Neural Information Processing Systems (NEURIPS),
volume 32, pp. 9562—-9574. MIT Press, Cambridge,
MA, 2019.

Lim, S., Sommer, C., Nikolova, E., and Rus, D. Practicalroute planning under delay uncertainty: Stochastic shortest path queries. In Robotics: Science and Systems VIII,
pp. 249–256, 2012. doi: 10.15607/RSS.2012.VIII.032.

Amos, B. and Kolter, J. Z. Optnet: Differentiable optimization as a layer in neural networks. In Precup, D.
and Teh, Y. W. (eds.), Proc. of the 34th Int. Conf. Machine Learning (ICML 2017), pp. 136—-145, Sydney,
Australia, August 6–11 2017.

Lin, L.-J. Self-improving reactive agents based on reinforcement learning, planning and teaching. Machine Learning,
8:293—-321, 1992.
Markowitz, H. Portfolio selection. J. of Finance, 7(1):77–91, March 1952.

Bertsimas, D., Darnell, C., and Soucy, R. Portfolio construction through mixed-integer programming at grantham,mayo, van otterloo and company. Interfaces, 29:49–66,
1999.

Nocedal, J. and Wright, S. J. Numerical Optimization.
Springer Series in Operations Research and Financial
Engineering. Springer-Verlag, New York, second edition,
2006.

Diamond, S. and Boyd, S. CVXPY: A Python-embedded
modeling language for convex optimization. Journal of
Machine Learning Research, 17(83):1–5, 2016.

Pogančic̀, M. V., Paulus, A., Musil, V., Martius, G., andRolinek, M. Differentiation of blackbox combinatorial
solvers. In Proc. of the 8th Int. Conf. Learning Representations (ICLR 2020), Addis Ababa, Ethiopia, April 26–30
2020.

Donti, P., Amos, B., and Kolter, J. Z. Task-based end-to-end
model learning in stochastic optimization. In Guyon, I.,
v. Luxburg, U., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), Advances in Neural
Information Processing Systems (NIPS), volume 30, pp.
1320–1332. MIT Press, Cambridge, MA, 2017.

Quandl. Wiki various end-of-day data, 2022. URL https://www.quandl.com/data/WIKI.

Elmachtoub, A. N. and Grigas, P. Smart “predict, then
optimize”. arXiv:1710.08005, October 22 2017.

Shah, S., Wang, K., Wilder, B., Perrault, A., and Tambe,
M. Decision-focused learning without decision-making:Learning locally optimized decision losses. In Advancesin Neural Information Processing System, pp. 1320–1332,
2022.

Fan, Y. Y., Kalaba, R. E., and Moore, J. E. Arriving on time. Journal of Optimization Theory and Applications, 127(1):497—-513, December 2005. doi:
10.1007/s10957-005-7498-5.

Tang, B. and Khalil, E. B. Pyepo: A pytorch-based end-toend predict-then-optimize library for linear and integer
programming. arXiv:2206.14234, June 28 2022.

Ferber, A., Wilder, B., Dilkina, B., and Tambe, M. MIPaaL:
Mixed integer program as a layer. In AAAI Conferenceon Artificial Intelligence (AAAI 2020), 2020.
Ferber, A., Huang, T., Zha, D., Schubert, M., Steiner, B.,
Dilkina, B., and Tian, Y. Surco: Learning linear surrogates for combinatorial nonlinear optimization problems.
arXiv:2210.12547, October 22 2022.

Wang, P.-W., Donti, P., Wilder, B., and Kolter, Z. Satnet:
Bridging deep learning and logical reasoning using a
differentiable satisfiability solver. In International Conference on Machine Learning, pp. 6545–6554. PMLR,
2019.

Gould, S., Fernando, B., Cherian, A., Anderson, P., Cruz,
R. S., and Guo, E. On differentiating parameterizedargmin and argmax problems with application to bi-level
optimization. arXiv:1607.05447, July 21 2016.

Wilder, B., Dilkina, B., and Tambe, M. Melding the datadecisions pipeline: Decision-focused learning for combinatorial optimization. In AAAI Conference on Artificial
Intelligence (AAAI 2020), 2020.
5LANCER: Learning Decision Losses for Mathematical Optimization Under Partial InformationYe, M., Liu, B., Wright, S., Stone, P., and Liu, Q. Bome!
bilevel optimization made easy: A simple first-order approach. In Advances in Neural Information Processing
System, 2022.

6

LANCER: Learning Decision Losses for Mathematical Optimization Under Partial Information

A. Algorithm details
Algorithm 1 Pseudocode for simultaneously learning LANCER and target model cθ . Note that the algorithm may varyslightly based on setting: P+O in algorithm 2 and variations of SurCo in algorithms 3-4.
1: Input: Dtrain ← {yi , zi }N
i=1 , solver g, objective f , target model cθ ;2: Initialize cθ (e.g. random, warm start);
3: for t = 1 . . . T do
4:
• w-step (fix θ and optimize over w):
5:
for (yi , zi ) ∈ Dtrain do
6:
evaluate ĉi = cθ (yi );7:evaluate fˆi = f (g(ĉi ); zi );8:
add (ĉi , zi , fˆi ) to D;
9:
end forP
10:
solve minw i∈D Mw (ĉi , zi ) − fˆi via supervised learning;11:• θ-step (fix w and
P optimize over θ):
12:
solve minθ i∈Dtrain Mw (cθ (yi ), zi ) via supervised learning.
13: end for
A.1. Reusing past evaluations of f ◦ gθIn LANCER, the learning process of Mw is solely reliant on D and is independent of the current state of cθ . Put simply, toeffectively learn Mw , we only need the inputs and outputs of f ◦ gθ , namely cθ (yi ), Z, and the corresponding objective
value f̂ . Interestingly, we can cache the predicted descriptions themselves, cθ (yi ), without the need for the model θ or
problem information. This caching mechanism allows us to reuse the data (cθ (yi ), z, f̂ ) from previous iterations (1 . . . T −1)
as-is. By adopting this practice, we enhance and diversify the available training data for Mw , which proves particularly
advantageous for neural networks. This concept bears resemblance to the concept of a replay buffer (Lin, 1992) commonly
found in the literature on Reinforcement Learning.
A.2. Computational complexity
It is quite straightforward to estimate the runtime of our approach from Algorithm 1. Let us denote Ig as the time to get thesolution from solver g(yi ). Also, let Iw and Iθ be the runtime of training the parametric loss Mw and the target model cθ ,respectively. Then, assuming evaluating f is negligible, one iteration of our algorithm naively takes O(N · Ig + Iw + Iθ ),so the total runtime is O(T · N · Ig + T · Iw + T · Iθ ). In practice, we iterate at most 100 times (T < 100). Therefore, themain bottleneck is O(T · N · Ig ), which is mainly overtaken by an access to g. Although we claim that leveraging M tolearn θ is efficient, we admit that there is still a requirement to access the solver g.
However, there are several accelerations that can be made:1. O(N · Ig ) is embarrassingly parallel computation since each request to g is independent and, additionally, subsampling
on Dtrain can be performed.
2. We can “warm start” the solver g from solutions obtained in t − 1, which typically yields faster convergence.
3. Although we did not test this, but one can “early stop” the solver g if it is too costly to solve optimally (e.g. large scale
MILP). Our hypothesis is that it is enough to obtain a feasible solution x̂ in certain neighborhood of x∗ . Since we arestill able to evaluate f and (f (x̂), ĉ, z) is a “valid” tuple, we can use it to train Mw .
4. Moreover, we empirically found out that the supervised learning steps (lines 10 and 12) do not require “perfect”
learning. That is, we perform several gradient updates over w and θ, which significantly reduces Iw and Iθ .
A.3. Variations of the algorithm
Algorithms 2-4 below closely resemble what we present in the main paper. However, there are minor variations that dependon the problem setting, whether it involves learning linear surrogates for MINLP or smart Predict+Optimize setting.
7

LANCER: Learning Decision Losses for Mathematical Optimization Under Partial Information

Algorithm 2 Pseudocode for learning LANCER and target model cθ for smart Predict+Optimize setting. Note: y – input(always observed) features, z – ground truth problem descriptions (available at train time only).
1: Input: Dtrain ← {yi , zi }N
i=1 , solver g, objective f (can be black–box), target model cθ , (optional) prediction loss
penalty λ;P
2: Initialize cθ from solving: minθ i∈Dtrain ∥cθ (yi ) − zi ∥;3: Set D ← {};4: for t = 1 . . . T do
5:
• w-step (fix θ and optimize over w):
6:
for (yi , zi ) ∈ Dtrain do
7:
evaluate ĉi = cθ (yi );8:evaluate fˆi = f (g(ĉi ); zi );9:
add (ĉi , zi , fˆi ) to D;
10:
end forP
11:
minimize: minw j∈D Mw (ĉj , zj ) − fˆj ;12:• θ-step (fix w and optimize
over θ):P
13:
minimize: minθ i∈Dtrain Mw (cθ (yi ), zi ) + λ∥cθ (yi ) − zi ∥.
14: end for
Algorithm 3 Pseudocode for learning linear surrogates with LANCER–zero (used sections 5.1.2 and 5.2.2 in the main paper).
Note that y = z in this setting and we have only one optimization problem instance.
1: Input: problem description y, solver g, objective f (can be black–box);
2: Initialize c ∈ RL ;3: Set D ← {};4: for t = 1 . . . T do
5:
• w-step (fix c and optimize over w):
6:
randomly sample {ĉi }Ni around c;
7:
for i = 1...N do
8:evaluate fˆi = f (g(ĉi ); y);9:add (ĉi , fˆi ) to D;
10:
end forP
11:
minimize: minw j∈D Mw (ĉj ) − fˆj ;12:• θ-step (fix w and optimize over c):// θ = c in this setting as we solve for a single problem instance y13:
14:
minimize: minc Mw (c).
15: end for
Algorithm 4 Pseudocode for learning linear surrogates with LANCER–prior (used section 5.2.2 in the main paper): we learncθ on a distribution of optimization problems. Note that y = z in this setting
1: Input: Dtrain ← {yi }N
i=1 , solver g, objective f (can be black–box), target model cθ ;2: Initialize cθ (random, warm start from heuristics);
3: Set D ← {};4: for t = 1 . . . T do
5:
• w-step (fix θ and optimize over w):
6:
for (yi ) ∈ Dtrain do
7:
evaluate ĉi = cθ (yi );8:evaluate fˆi = f (g(ĉi ); yi );9:add (ĉi , yi , fˆi ) to D;
10:
end forP
11:
minimize: minw j∈D Mw (ĉj , yj ) − fˆj ;12:• θ-step (fix w and optimize
over θ):P
13:
minimize: minθ i∈Dtrain Mw (cθ (yi ), yi ).
14: end for
8

LANCER: Learning Decision Losses for Mathematical Optimization Under Partial Information

B. Details of experimental setup
B.1. Synthetic data
Data

We follow the setup and scripts from PyEPO (Tang & Khalil, 2022) library to generate data.

• for SP, we follow the same data generation process as in the original scripts: 5 × 5 grid (40 total edges), 1000 training
problem instances with 5 input features (i.e., Y ∈ R1000×5 ) and the same for the test set. Input features (y) are
generated using normal distribution with N (0, 1). The ground truth descriptors z are obtained by first randomly andlinearly projecting y in 40 dimensions followed by nonlinearity (polynomial of degree 6 and normalization). Lastly,
random noise is added to z to make the problem harder. We use the standard linear program (LP) formulation of theshortest path and implement solver g in SCIP (Achterberg, 2009).
• As for MKS, we begin by generating a cost vector for each item using a random uniform distribution between 0 and
5. Then, we obtain features y by passing z through a random neural network with one hidden layer of size 500 andtanh activation. Knapsack capacity is 40, knapsack dimension is 5, 100 total items to choose from, feature dimension
is 256 and there are 1000 instances in both train/test. Lastly, weight for each item is generated according to theuniform distribution between 0 and 1. We use the standard mixed-integer linear program (MILP) formulation of themultidimensional knapsack and implement solver g in SCIP (Achterberg, 2009).
Target mapping cθ All baselines use the same target mappings for each problem: linear mapping for SP and MLP with 1
hidden layer for MKS (size of 300 and tanh activation).
LANCER

The training procedure closely follows Algorithm 2. Other problem dependent settings are as follows:• for SP, LANCER uses MLP with 2 hidden layers of size 100 (tanh activation). We train LANCER for T = 10 iterations.
At each iteration, we make 5 updates (using Adam optimizer with lr= 0.001) for each mappings (cθ and Mw ).
• for MKS, LANCER uses MLP with 2 hidden layers of size 200 (tanh activation). We train LANCER for T = 7 iterations.
At each iteration, we perform 5 updates (using Adam optimizer with lr= 0.001) for cθ and 10 updates for Mw .
Baselines• SPO+,DBB: We use the versions implemented within PyEPO and set the number of epochs to 25. Both methods use
the Adam optimizer with learning rates tuned for each problem. Other arguments follow the default setting suggested
by authors.
• LODLs: We use the implementation provided by authors in (Shah et al., 2022). We set the number of sampling points
to 1000 and employ “random Hessian” version of the algorithm. Other arguments follow the default setting suggested
by authors.
B.2. Real-world use case: quadratic and broader nonlinear portfolio selection
B.2.1. T HE QUADRATIC PROGRAMMING (QP) FORMULATION
We use the standard quadratic program formulation of the Markowitz’ (Markowitz, 1952) portfolio selection problem:
min αxT Gx − µT x
x

s.t.

k
X

(5)
xi = 1 and

x≥0

i=1

where µ is an expected return vector for each portfolio and G is the covariance matrix. We set the user-defined hyperparameter α = 0.1 in all experiments and use CvxPy (Diamond & Boyd, 2016) to solve QP in eq. (5).
Data We reuse the code from Shah et al. (2022) to generate data (downloaded from QuandlWIKI (Quandl)) and use thesame setup. The features y are historical stock prices and the task is to predict an expected return µ (using MLP with 1
hidden layer of size 500) in smart Predict+Optimize fashion. There are 200 instances in train/validation set and 400 instancesin test set. The number of portfolios in each instance is 50.
9LANCER: Learning Decision Losses for Mathematical Optimization Under Partial Information

LANCER The training procedure closely follows Algorithm 2. We use MLP with 2 hidden layers of size 100 and tanh
activation. We train LANCER for T = 8 iterations. At each iteration, we make 10 updates (using Adam optimizer) to fit
each mapping (cθ and Mw ).
Baselines• LODLs: We use the implementation provided by authors in (Shah et al., 2022). We replicate their configurations forthis experiment, except we made a quick fix in the code as they forgot to add a matrix transpose in the quadratic term.
• MDFL (Melding Decision Focused Learning) (Wilder et al., 2020): we use the version implemented in (Shah et al.,2022) and follow their configurations.
B.2.2. C OMBINATORIAL PORTFOLIO SELECTION WITH THIRD - ORDER OBJECTIVE
We extend the portfolio selection problem in eq. (5) as follows:
min αxT Gx + γ∥x − x0 ∥1 − µT x − βxT Sx ⊗ x
x,v

s.t.

k
X

xi = 1i=1fmin ∗ vi ≤ xi ≤ fmax ∗ vim≤kXvi ≤ Mfor i = 1 . . . k(fraction of each selected portfolio)(6)(no. of selected portfolios must be between m and M )

i=1

x≥0
v ∈ {0, 1}
where S is co-skewness matrix and v is the binary variables to enforce discrete constraints (e.g. hard limit on number of
portfolios). We also introduce the initial portfolio selection vector x0 (generated uniformly at random) and enforce our final
solution to be close to it (via γ). We set the penalty on co-skewness as β = 0.5, γ = 0.01, m = 3, M = 10, fmin = 0.01
and fmax = 0.2 throughout all experiments. We reuse the same data as in section B.2.1 but increase the number of portfolios
to 100 and add co-skewness matrix S to it. Note that in this task we assume that all problem descriptors are fully observed(e.g. µ, G, S).
LANCER The training procedure for LANCER-zero closely follows Algorithm 3 and LANCER-prior closely follows
Algorithm 4. We use MLP with 2 hidden layers of size 300 and tanh activation. We train LANCER for T = 40 iterations.
At each iteration, we perform 10 updates (using Adam optimizer) for each learnable models (cθ and Mw). Additionally,
LANCER-prior uses a parametric mapping for cθ which is implemented via 1 hidden layer MLP of size 500, which µ takes
as input.
Baselines• SCIP attempts to solve the problem defined in Eqn. (6) in three different settings related to the objective: ignores all
nonlinear terms (MILP), ignores cubic term (MIQP) and attempts to solve the original nonlinear problem (MINLP).
We set the maximum time limit to 60 min before terminating the solver and obtaining the best solution.
• for SurCo (Ferber et al., 2022), we use two versions: SurCo-prior and SurCo-zero. SurCo-prior uses the same mapping
for cθ as LANCER described above. We use DBB (Pogančic̀ et al., 2020) to differentiate through the solver with
λ = 100 and apply Adam optimizer for 100 epochs with the learning rate = 0.1 (0.0001 for prior).

C. Additional experimental results
C.1. Combinatorial optimization with nonlinear objective
In this section, we apply LANCER for solving mixed integer nonlinear programs (MINLP). Specifically, we transform a
combinatorial problem with a nonlinear objective into an instance of MILP via learning linear surrogate costs as described
10

LANCER: Learning Decision Losses for Mathematical Optimization Under Partial Information
Grid 5x5

Grid 15x15

Figure 4. Results on stochastic shortest path using different grid sizes: 5x5 (left) and 15x15 (right). We report avg objective values (higher
is better) on three settings described in (Ferber et al., 2022). For grid size of 15x15, SCIP (Achterberg, 2009) was unable to finish within
the 30 min time limit.

in Ferber et al. (2022). Note that in this setting, we assume that the full problem description y = z is given and fully
observable (in contrast to the P+O setting).
We examine on-the-fly optimization, where each problem is treated independently. In this scenario, the cost vector cθ (y)simplifies to a constant value c. SurCo is then responsible for directly training the cost vector c of the linear surrogate. We
refer to this version as LANCER–zero to be consistent with SurCo–zero.
C.1.1. S ETUP
Nonlinear shortest path problems arise when the objective is to maximize the probability of reaching a destination before
a specified time in graphs with random edges (Lim et al., 2012; Fan et al., 2005). These problems commonly occur inrisk-aware contexts, such as emergency service operators aiming to maximize timely arrival or situations where driver
incentives depend on meeting deadlines. The problem formulation is similar to the standard linear programming (LP)formulation of the shortest path, as described in section 3.1, with a few adjustments: 1) the weight of each edge follows anormal distribution, i.e., we ∼ N (µe , σe ); 2) the objective is to maximize the probability that the sum of weights along theshortest path
 the standard Gaussian cumulative distribution function
pP using
Pcan be expressed
Pis below a threshold W , whichσ(CDF), P ( e∈E we ≤ W ) = Φ (W − e∈E µe )/e∈E e where E is the set of edges belonging to the shortest
path. We use 5 × 5 and 15 × 15 grid graphs with 25 draws of edge weights. We set the threshold W to three different values
corresponding to loose, normal, and tight deadlines.
We aim to solve the following optimization problem with nonlinear objective:


s X
X
min Φ (W −xu,v σu,v xu,v µu,v )/xs.t.

(u,v)∈E(u,v)∈EX

xu,t ≥ 1(at least one unit of flow into t)

xu,t −X(7)(u,t)∈EX

u:(u,v)∈Ex≥0xu,t ≥ 0 ,∀v ∈/ {s, t}(flow in ≥ flow out)

u:(v,u)∈E

where Φ is the standard Gaussian cumulative distribution function (CDF), E is the set of all edges, W is the user-defined
threshold, µu,v and σu,v are the mean and the variance of the corresponding edge’s weight.
Data We closely follow the data generation process described in (Ferber et al., 2022). Specifically, each edge is a randomvariable with µ coming from the uniform distribution (between 0.1 and 0.2); and with σ is also generated uniformly
11

LANCER: Learning Decision Losses for Mathematical Optimization Under Partial Information
Multidimensional Knapsack

Portfolio Optimization

Figure 5. Trade-off curves between black-box solver calls (MILP or QP) vs decision loss (or regret) on P+O problems. Point labels (e.g.
1,4,7) correspond to the epoch; except for LODLs, where they correspond to the number of samples per instance. Each algorithm uses a
different number of BB calls per epoch.

randomly (between 0.1 and 0.3 multiplied by 1 − µ). For thresholds W , we set them as follows: calculate the distance ofthe shortest path distance using the mean value as an edge weight and multiply it to 0.9 for tight, 1.0 for normal and 1.1 forloose deadlines, respectively. We set the number of problem instances to 25 and use the Bellman-ford algorithm for a solverg.
LANCER The training procedure closely follows Algorithm 3. We use MLP with 2 hidden layers of size 200 (300 for
15 × 15 grid size) and tanh activation. We train LANCER for T = 40 iterations. At each iteration, we make 10 updates(using Adam optimizer) for each learnable models (c and Mw ).
Baselines• SCIP attempts to solve the original MINLP defined in Eqn. (7). We set the maximum time limit to 30 min before
terminating the solver.
• Domain Heuristic simply assigns each edge’s weight as we = µe + γσe (where γ is a hyperparameter) and run the
Bellman-ford’s algorithm.
• SurCo (Ferber et al., 2022) replicates the same experimental setup as described in the original paper. Specifically, we
use DBB (Pogančic̀ et al., 2020) to differentiate through the solver with λ = 1000 and apply Adam optimizer for 40
epochs with the learning rate = 0.1.
C.1.2. R ESULTS
Fig. 4 illustrates the performance of different methods in both grid sizes. SCIP directly formulates the MINLP to maximize
the CDF, resulting in an optimal solution. However, this approach is not scalable for larger problems and is limited to smaller
instances like the 5 × 5 grid. The heuristic method assigns each edge weight as we = µe + γσe , where γ is a user-defined
hyperparameter, and employs standard shortest path algorithms (e.g., Bellman-ford). As the results indicate, this heuristic
approach produces highly suboptimal solutions. SurCo–zero and LANCER–zero demonstrate similar performance, withLANCER–zero being superior in almost all scenarios.
C.2. Computational efficiency
Comparing baseline methods, including LANCER, we find that querying solver gθ is the primary computational bottleneck.
To evaluate this aspect, we empirically analyze different algorithms on various benchmarks in the P+O domain. The results,
depicted in fig. 5, highlight that LODLs require sampling a relatively large number of points per training instance, leading
to potentially time-consuming solver access. On the other hand, gradient-based methods like DBB, MDFL, and SPO+
typically solve the optimization problem 1-2 times per update but require more iterations to converge. In contrast, LANCER
12LANCER: Learning Decision Losses for Mathematical Optimization Under Partial Information

Table 2. Results of reusing M on stochastic shortest path problem from fig. 4 (15 × 15 grid). Here, “reused Mw ” has limited access tothe solver g, and thus is much faster while retaining solution quality.
MethodLoose Deadline
Normal Deadline
Tight Deadline
obj.
time (s)obj.
time (s)obj.
time (s)LANCER–zero
0.556 ± 0.006 61.1 ± 3.2 0.497 ± 0.004 62.3 ± 2.9 0.434 ± 0.005 62.8 ± 2.7
LANCER–reused Mw 0.556 ± 0.007 2.9 ± 0.3 0.496 ± 0.004 2.7 ± 0.6 0.432 ± 0.004 2.5 ± 0.6

accesses the solver in the w-step, with the number of accesses proportional to the training set size and a small total numberof alternating optimization iterations. Moreover, we leverage saved solutions from previous iterations, akin to a replay buffer,when fitting M. These combined factors allow us to achieve favorable results with a small value of T .
C.3. Reusing landscape surrogate Mw
In this scenario, we introduce a dependency of Mw on both the predicted linear cost (c) and the problem descriptor (y), as
described in section 2. This enables us to reuse Mw for different problem instances without retraining, and eliminate thedependency on the solver gθ , giving LANCER a substantial runtime acceleration. To validate this hypothesis, we pretrain
Mw using 200 instances of the stochastic shortest path on a 15 × 15 grid by providing concatenated (c, y) as input. We
apply LANCER–zero to the same test set as before and present results in fig. 2, demonstrating comparable performance
between these two approaches, with “reused Mw ” being much faster.

D. Interpreting combinatorial portfolio selection with third-order objective
Based on our experimental findings, LANCER showcased the most significant improvement in addressing the combinatorial
portfolio selection problem. Inspired by this success, we delved further into the intricacies of this problem and sought tovisualize the actual solutions obtained by the two best-performing methods: SurCo and LANCER. We present the results fora randomly selected instance in Figure 6.
We have assigned a symbol of a corresponding S&P company to each point for clarity. On the Y-axis, we represent the
expected return of a selected stock, which is multiplied by its fraction (approximate solution x in Eqn. (6)). Similarly,
the X-axis displays the “risk−skewness score” calculated as follows: αx ⊙ (Gx) − βx ⊙ (Sx ⊗ x), where ⊙ denotes
element-wise multiplication. This computation results in a vector of dimensions equal to the number of stocks, enabling us
to interpret it as a score assigned to each stock. Furthermore, the combinatorial constraints outlined in Eqn. (6) enforce theselection of a maximum of M stocks with fractions lower than or equal to fmax .
As we try to maximize the return and minimize the risk−skewness score, we want all point to be in the upper-left corner.
This is what LANCER achieves. It is interesting to see that LANCER chooses the less number of portfolios (6 vs 9) but
assigns higher fraction to them improving overall objective.

13

LANCER: Learning Decision Losses for Mathematical Optimization Under Partial Information

Figure 6. Visualization of the solution for a single instance of the combinatorial portfolio selection with third-order objective. LANCER
demonstrates a tendency to select and allocate a significant proportion to stocks characterized by a combination of low ’risk − skewness’and high rewards (upper-left corner).

14