We introduce informationally complete measurements whose outcomes are entanglement witnesses and so answer the question of how many witnesses need to be measured to decide whether an arbitrary state is entangled or not: as many as the dimension of the state space. The witnesses can be measured successively; if all of them give an inconclusive result, one exploits their tomographic completeness for a reconstruction of the quantum state and can then determine its entanglement properties by data processing.  The optimized witness-based measurement can provide exponential improvement with respect to witness efficiency in high-dimensional Hilbert spaces, at the price of a reduction in the tomographic efficiency. We describe a systematic construction and illustrate the matter with the example of two qubits. For the case of two polarization qubits of photons, we show how Hong--Ou--Mandel effect can be used to implement the optimized witnesses in a very efficient way. Owing to the details of the implementation, which actually measures the eigenstate basis of the witness rather than solely determining the expectation value, one can measure a family of optimal witnesses simultaneously, thereby effectively  realizing a nonlinear entanglement witness. Consequently, one does not need to measure more than six witnesses in this example of a 16-dimensional state space. Recent experiment realizing this idea will be discussed briefly followed by several open problems(Work in collaboration with  Yong Siah Teo and Berthold-Georg Englert).