Source-linked AI summary
VLM Fine-Tuning for End-to-End Combinatorial Optimization
Qingsong Yan, Xia Jiang, Yaoxin Wu, Wen Song, Lu Zhang, Yingjie Zhou
TL;DR
Text-only serialization can make spatial and relational structures in CO instances difficult to perceive. The paper pairs instance text with input-derived images and trains one VLM across tasks using supervised fine-tuning and verifier-guided reinforcement learning. The VLM generally improves solution quality over its text-only counterpart, especially on CVRP and JSSP, with more pronounced advantages at larger scales.
Problem
Textual serialization alone can obscure spatial and relational structures that are important for generating effective CO solutions.
Source: §1 · p. 1Method
Results
The VLM generally improves solution quality over the text-only solver, with clear gains on CVRP and JSSP and more pronounced advantages at larger problem scales.
Source: §4.1 · p. 3, §5 · p. 4, §4.2 · p. 4Takeaways & Limitations
Across the tested CO problems, input-derived visual representations generally enhance the shared VLM solver's performance over its text-only counterpart.
Source: §4.1 · p. 3, §5 · p. 4Visual inputs use only instance-derived information, without solution-derived information, and text remains authoritative for exact numerical values.
Source: §2 · p. 1, §3.1 · p. 2
Abstract
from arXiv · showhide
Large language models (LLMs) have provided a unified interface for end-to-end combinatorial optimization (CO), but textual serialization alone may obscure spatial and relational structures that are important for generating effective CO solutions. This paper presents a general-purpose vision-language solver that augments textual instance descriptions with input-derived visual representations. A single vision-language model (VLM) is applied across different CO tasks and trained using supervised fine-tuning followed by verifier-guided reinforcement learning. While the visual inputs contain no gold solutions or solution-derived information, our experiments show that the VLM generally improves solution quality over its text-only counterpart, with particularly clear gains on more complex CO problems such as CVRP and JSSP. The advantage of visual information is more pronounced at large problem scales.
1. INTRODUCTION
End-to-end LLM solvers provide a unified natural-language interface to CO, but text alone can make spatial and relational structures difficult to perceive. The paper investigates adding input-derived images and reports that visual information improves CO solving.
1. INTRODUCTION
- Textual serialization makes spatial and relational structures, including graph connectivity and object relationships, difficult to perceive.This motivates investigating whether visual information can improve LLM-based CO solving.Source: §1 · p. 1
- The solver represents each CO instance with text and an input-derived image, then trains one VLM across problems using supervised fine-tuning and verifier-guided reinforcement learning.The visual representation contains no solution-derived information.Source: §1 · p. 1
- Experiments show that visual information improves end-to-end CO solving over the text-only solver, with stronger generalization as problem size increases.The paper highlights substantial gains over the text-only solver.Source: §1 · p. 1
2. PROBLEM STATEMENT
The paper formalizes CO instances in terms of feasible solutions and objectives, then represents each instance with complementary text and image inputs. A shared policy generates solutions that are parsed and verified against the original instance.
2. PROBLEM STATEMENT
- Each instance has a solution space, objective function, and constraint set; the goal is a feasible solution that minimizes or maximizes the objective.The feasible solution space contains solutions satisfying every constraint.Source: §2 · p. 1
- Text serialization preserves exact instance information, while an image supplies complementary structural information; both are generated solely from the instance.The representation includes no solution-derived information.Source: §2 · p. 1
- A shared policy generates a textual response that a problem-specific parser converts into a numerical solution, which a verifier evaluates against the original instance.The verifier reports feasibility and objective value.Source: §2 · pp. 1–2
- Evaluation reports feasibility rate and average gap over feasible solutions.The relative gap is computed against an optimal or best-known reference objective.Source: §2 · p. 2
3. THE METHOD
The method uses one shared VLM for heterogeneous CO problems, pairing textual instance descriptions with problem-adapted images. It trains the model with supervised fine-tuning and verifier-guided reinforcement learning.
3. THE METHOD
- A shared VLM processes heterogeneous CO problems; problem-specific components are limited to input construction and solution verification.The model receives multimodal instance inputs and generates textual solutions.Source: §3 · p. 2
3.1. Visual Representation
- Routing images encode customers and nearby links, graph images show nodes and adjacency, and JSSP images encode operations, processing times, and job precedence.CVRP labels also include customer IDs and demands; in routing images, node distances are proportional to spatial distances.Source: §3.1 · p. 2
3.2. Supervised Fine-tuning
- SFT applies autoregressive loss only to target-response tokens, using the instruction, instance text, image tokens, and output-format prompt as conditioning.LoRA adapts the model while pretrained VLM parameters remain frozen; the resulting model initializes RL.Source: §3.2 · p. 3
3.3. Reinforcement Learning
- Verifier-guided RL scores feasibility and objective quality, assigning objective reward only to candidates that satisfy the required constraints.The feasibility verifier checks problem-specific constraints against the original instance, and the objective verifier evaluates feasible parsed solutions.Source: §3.3 · p. 3
4. EXPERIMENTS
The experiments compare the fine-tuned VLM with general-purpose and CO-specific baselines across seven problems. The VLM improves on the text-only counterpart, with clearer gains on CVRP and JSSP and a more pronounced advantage at larger scales.
4. EXPERIMENTS
- The evaluation fine-tunes Qwen3-VL on seven CO problems, using 500,000 SFT instances per problem and at most 3,200 RL instances.Inference uses greedy decoding or Best-of-N selection from eight stochastic candidates.Source: §4 · p. 3
4.1. Comparative Study
- The VLM reduces Gap by 0.16% on TSP, 0.72% on OP, and 0.18% on MVC while retaining full feasibility; it achieves 97% vs. 94% feasibility on MIS.It matches the fine-tuned LLM on PFSP and, with greedy decoding, both fine-tuned approaches outperform the other reported baselines.Source: §4.1 · p. 3
- Against the fine-tuned text-only LLM under Best-of-N, the VLM reduces Gap by 0.95% on CVRP and 2.35% on JSSP.Table 1 evaluates feasibility, relative gap, and average time across seven CO problems.Source: §4.1 · p. 3, Table 1 · p. 4
4.2. Comparison across Problem Scales
- The VLM’s advantage over competing baselines becomes more pronounced and consistent as instance size increases.Small, medium, and large instances are defined using scheduling dimensions or node counts, and comparisons include text-only and domain-specific baselines.Source: §4.2 · p. 4, Table 2 · p. 4
5. CONCLUSION AND FUTURE WORK
The VLM improves solution quality over a text-only LLM, with significant gains on complex CVRP and JSSP; its visual-information advantage grows at larger problem sizes.
- The VLM improves solution quality over the text-only LLM, with significant gains on complex CVRP and JSSP.Source: §5 · p. 4
- The advantage of visual information becomes more pronounced as problem size increases.Source: §5 · p. 4
- Future work will explore VLMs in general optimization and improve transferability to more complex CO instances.Source: §5 · p. 4