liveBook · Manning

Combinatorial optimization

As explained in Applied Reinforcement Learning

Combinatorial optimization is optimization over a discrete set of possible configurations or decisions.

Combinatorial optimization searches among discrete configurations or decisions for a good solution. In logistics, packing boxes into trailers means choosing a position and orientation for each box while respecting space and overlap constraints. The many possible placements make this a large decision space, so reinforcement learning can be used to learn a packing policy. section 3.4

Packing trailers

Given a fixed sequence of rectangular boxes and trailers of different dimensions, choose where each box goes and one of six orientations. Successful placements use space; invalid placements and skipped boxes receive penalties in the environment’s reward design. section 3.4

Figure 3.7 Visualization of one instance of trailer loading and packing environment.

A visualization of one trailer-packing instance makes the placement problem concrete. section 3.4

How Applied Reinforcement Learning covers it

How deep it goes
Works through the packing problem and environment design, including placement constraints and reward signals.
Examples
Uses boxes with six orientations packed into trailers of varying dimensions.
What you can do after
Build it from scratch by encoding trailer packing as a sequential environment with placement actions and reward signals.
How it connects
Connects combinatorial optimization to reinforcement learning and three-dimensional bin packing.

Also explained in

Compare how 2 books explain combinatorial optimization →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Applied Reinforcement Learning. The section links point to the parts of the book it draws on.