Mixed problems
Class: BIP / MILP · Script: one script and one notebook per problem
(python/fam10_1_prizes.py … fam10_9_shelves.py).
Prerequisites
-
From this module, Chapter 5 «Logic and binary variables»: logical constraints between binary variables.
-
From this module, Chapter 6 «Links between variables»: minimum lot, maximum variable, min-max and max-min.
-
From this module, Chapter 9 «Production planning»: the bound protocol applied to a family of problems.
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''.
-
10.2 Combinatorial auction
A set packing on the bids: two bids sharing a lot cannot both be accepted.
-
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.
-
10.4 Boxes of lights for the trees
Configurations of fixed composition and a variety constraint: how many boxes of each type to buy.
-
10.5 Shipments in boxes
Covering a demand with containers of different size, one per product type.
-
10.6 Children among summer camps
Integer counts and composition constraints. The LP relaxation does not see parity: the useful bound is combinatorial.
-
10.7 Branches between two companies
Min-max on the worst imbalance. The relaxation is zero: every branch is split in half.
-
10.8 Tracks among CDs
Absolute value and levelling of the durations. Here too the relaxation is zero.
-
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}\).
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.