  Combinatorial optimisation problems are ubiquitous in artificial
intelligence. Designing the underlying models, however, requires substantial
expertise, which is a limiting factor in practice. The models typically consist
of hard and soft constraints, or combine hard constraints with an objective
function. We introduce a novel setting for learning combinatorial optimisation
problems from contextual examples. These positive and negative examples show -
in a particular context - whether the solutions are good enough or not. We
develop our framework using the MAX-SAT formalism as it is simple yet powerful
setting having these features. We study the learnability of MAX-SAT models. Our
theoretical results show that high-quality MAX-SAT models can be learned from
contextual examples in the realisable and agnostic settings, as long as the
data satisfies an intuitive "representativeness" condition. We also contribute
two implementations based on our theoretical results: one leverages ideas from
syntax-guided synthesis while the other makes use of stochastic local search
techniques. The two implementations are evaluated by recovering synthetic and
benchmark models from contextual examples. The experimental results support our
theoretical analysis, showing that MAX-SAT models can be learned from
contextual examples. Among the two implementations, the stochastic local search
learner scales much better than the syntax-guided implementation while
providing comparable or better models.
