Discrete mathematics brings interesting problems for teaching and learning proof, with accessible objects such as integers (arithmetic), graphs (modeling, order) or polyominoes (geometry). Many problems that are still open can be explained to a large public. The objects can be manipulated by simple dynamic operations (removing, adding, 'gluing', contracting, splitting, decomposing, etc.). All these operations can be seen as tools for proving. In this paper we particularly explore the field of 'discrete optimization'. A theoretical background is defined by taking two main axes into account, namely, the epistemological analysis of discrete problems studied by contemporary researchers in discrete optimization and the design of adidactical situations for classrooms in the frame of the Theory of Didactical Situations. Two problems coming from ongoing research in discrete optimization (the Pentamino Exclusion and the Eight Queens problems) are developed and transposed for the classroom. They underscore the learning potentialities of discrete mathematics and epistemological obstacles concerning proving processes. They emphasize the understanding of a necessary condition and a sufficient condition and problematize the difference between optimal and optimum. They provide proofs involving partitioning strategies, greedy algorithms but also primal-dual methods leading to the concept of duality. The way such problems can be implemented in the classroom is described in a collaborative study by mathematicians and mathematics education researchers ("Maths à Modeler" Research Federation) through the Research Situations for the Classroom project.