Skip to content

Mixed problems

Class: BIP / MILP · Script: one script and one notebook per problem (python/fam10_1_prizes.py … fam10_9_shelves.py).

Prerequisites

Objectives

At the end of this chapter you will be able to:

  • recognise which modelling pieces a problem without a familiar structure combines;

  • model selection with alternative modes, covering with packs and splitting with balancing;

  • explain why the LP relaxation of a splitting problem is weak;

  • find a dual bound with a combinatorial argument: parity, number of containers, dominance.

The three preceding families have a recognisable structure: one assigns, one locates, one plans. The nine problems in this chapter do not have one, and none should be forced on them: each puts together different pieces, and the modelling work consists precisely in recognising which.

  • Selection with alternative modes (10.1 and 10.2): a subset is chosen, but each object has more than one way of being chosen, and the ways exclude one another.
  • Quantities with a minimum lot (10.3): next to the binaries there are continuous quantities, and a quantity may be zero or else between a threshold and a cap.
  • Covering with containers (10.4 and 10.5): a requirement must be covered by buying packs of fixed composition, and the excess is either paid for or wasted.
  • Splitting and balancing (10.6–10.9): a set must be divided among several containers and the quality is measured by how much the containers resemble one another.

Four of these problems share a trait that did not appear in the three families: the LP relaxation is weak, and in two cases it is exactly zero. The reason is always the same: a fractional solution can split every object in half and put one half in each container, levelling everything.

Where to look for a combinatorial bound when the relaxation is not enough

Parity: a count that cannot but be even. Number of containers: how many are needed at the very least, read off the capacities. Dominance of one class: a class of objects that by itself imposes the value. These are combinatorial arguments: they come from integrality, and the dual of the relaxation cannot see them.

The nine problems

  • 10.1 Prizes with two payment modes


    Set packing on four variables instead of two: the quantity \(x_i + y_i\) is the indicator ``prize \(i\) taken''.

    BIP · set packing

  • 10.2 Combinatorial auction


    A set packing on the bids: two bids sharing a lot cannot both be accepted.

    BIP · set packing

  • 10.3 Diet with a minimum lot


    Continuous quantities with a minimum lot: a food is bought at zero or else between its threshold and its cap.

    MILP · minimum lot

  • 10.4 Boxes of lights for the trees


    Configurations of fixed composition and a variety constraint: how many boxes of each type to buy.

    MILP · containers

  • 10.5 Shipments in boxes


    Covering a demand with containers of different size, one per product type.

    MILP · capacity

  • 10.6 Children among summer camps


    Integer counts and composition constraints. The LP relaxation does not see parity: the useful bound is combinatorial.

    ILP · integer counts

  • 10.7 Branches between two companies


    Min-max on the worst imbalance. The relaxation is zero: every branch is split in half.

    BIP · min-max

  • 10.8 Tracks among CDs


    Absolute value and levelling of the durations. Here too the relaxation is zero.

    MILP · max and min

  • 10.9 Books among shelves


    Maximum variable: the height of a shelf is that of its tallest book, imposed with \(y_s \ge h_b\, x_{bs}\).

    MILP · maximum variable

In summary

In summary

  • The nine problems have no common structure: the modelling work is recognising which pieces they put together.

  • Selection with alternative modes, counts with a minimum lot, covering with containers, splitting and balancing.

  • In four problems the LP relaxation is weak, in two exactly zero: a fractional solution splits every object in half.

  • The useful dual bound then comes from integrality, with combinatorial arguments that the dual of the relaxation cannot see.