I was reading this paper by Cerna et al. (2018)1. In the paper there are only CPLEX-solvable equations given by the authors and the results.

How valuable is this paper, and what is its quality? Can we just provide equations, tests, and results in a problem and publish a paper in a good journal?

Doesn't it require to prove the correctness of these equations related to the problem?


[1] Cerna, F. V. et al. (2018). Optimal Delivery Scheduling and Charging of EVs in the Navigation of a City Map. IEEE Transactions on Smart Grid. 9(5):4815-4827.

  • 7
    $\begingroup$ Providing different MILP formulations for a problem is arguably the most common type of paper one encounters in OR literature. In most cases, the equations provided in the MILP formulation are very simple to verify for their correctness, so authors very often skip proofs to show correctness of the model. However, when additional inequalities such as cutting planes are added to the formulation, very often you will find proofs of correctness for those cuts. $\endgroup$ – batwing Jan 17 '20 at 19:36
  • $\begingroup$ Then how can we compare which formulation is better, for example, TSP Miller-Tucker-Zemlin formulation and Dantzig-Fulkerson-Johnson formulation? $\endgroup$ – ooo Jan 18 '20 at 7:54
  • 3
    $\begingroup$ To claim if a formulation is better than some other formulation rigorously, the approach I am most familiar is to show that the LP relaxation of one formulation is tighter than the LP relaxation of the other formulation, where tightness is measured in terms of the size of the feasible region. Regarding your example, many textbooks on Integer Programming contain proofs to show that DFJ formulation for TSP is tighter than the MTZ formulation in exactly the way I described. $\endgroup$ – batwing Jan 18 '20 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.