Home  ›  Solving a Problem With a Continuous Variables and One Binary

Solving a Problem With a Continuous Variables and One Binary

Written By Thursday 20 October 2022 Add Comment Edit

Abstract

We discuss a class of tightly feasible MILP for which branch-and-bound is ineffective. We consider its hardness, evaluate the probability that randomly generated instances are feasible, and introduce a heuristic solution method based on the old idea of reformulating binary variables to continuous while introducing a linear complementarity constraint. We show the extent of the computational advantage, under a time limit, of our heuristic with respect to a state-of-the-art branch-and-bound implementation.

Keywords

  • Reformulation
  • Infeasible
  • Market split
  • Market share
  • Hard instances

This work was partially supported by: the PGMO grant "Projet 2016-1751H"; a Siebel Energy Institute Seed Grant; the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement n. 764759 ETN "MINOA".

References

  1. Aardal, K., Bixby, R.E., Hurkens, C.A.J., Lenstra, A.K., Smeltink, J.W.: Market split and basis reduction: towards a solution of the cornuéjols-dawande instances. In: Cornuéjols, G., Burkard, R.E., Woeginger, G.J. (eds.) IPCO 1999. LNCS, vol. 1610, pp. 1–16. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48777-8_1

    CrossRef  MATH  Google Scholar

  2. Aardal, K., Hurkens, C., Lenstra, A.: Solving a system of linear Diophantine equations with lower and upper bounds on the variables. Math. Oper. Res. 25(3), 427–442 (2000)

    CrossRef  MathSciNet  Google Scholar

  3. Barvinok, A.I.: Feasibility testing for systems of real quadratic equations. Discrete Comput. Geom. 10(1), 1–13 (1993). https://doi.org/10.1007/BF02573959

    CrossRef  MathSciNet  MATH  Google Scholar

  4. Bradley, G.: Algorithms for Hermite and Smith normal matrices and linear Diophantine equations. Math. Comput. 25(116), 897–907 (1971)

    CrossRef  MathSciNet  Google Scholar

  5. Cornuéjols, G., Dawande, M.: A class of hard small 0—1 programs. In: Bixby, R.E., Boyd, E.A., Ríos-Mercado, R.Z. (eds.) IPCO 1998. LNCS, vol. 1412, pp. 284–293. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-69346-7_22

    CrossRef  Google Scholar

  6. D'Ambrosio, C.: Personal communication (2017)

    Google Scholar

  7. Di Giacomo, L., Patrizi, G., Argento, E.: Linear complementarity as a general solution method to combinatorial problems. INFORMS J. Comput. 19(1), 73–79 (2007)

    Google Scholar

  8. Fourer, R., Gay, D.: The AMPL Book. Duxbury Press, Pacific Grove (2002)

    Google Scholar

  9. Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman and Company, New York (1979)

    MATH  Google Scholar

  10. Gill, P.: User's guide for SNOPT version 7.2. Systems Optimization Laboratory, Stanford University, California (2006)

    Google Scholar

  11. Hall, P.: The distribution of means for samples of size \(n\) drawn from a population in which the variate takes values between 0 and 1, all such values being equally probable. Biometrika 19(3/4), 240–245 (1927)

    CrossRef  Google Scholar

  12. IBM: ILOG CPLEX 12.10 User's Manual. IBM (2020)

    Google Scholar

  13. Lazebnik, F.: On systems of linear Diophantine equations. Math. Mag. 69(4), 261–266 (1996)

    CrossRef  MathSciNet  Google Scholar

  14. Ledoux, M.: The concentration of measure phenomenon. In: Number 89 in Mathematical Surveys and Monographs. AMS, Providence (2005)

    Google Scholar

  15. Lenstra, H.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538–548 (1983)

    CrossRef  MathSciNet  Google Scholar

  16. Locatelli, M., Schoen, F.: Random linkage: a family of acceptance/rejection algorithms for global optimization. Math. Program. 85(2), 379–396 (1999)

    CrossRef  MathSciNet  Google Scholar

  17. Lopez, C., Beasley, J.: A note on solving MINLP's using formulation space search. Optim. Lett. 8, 1167–1182 (2014)

    CrossRef  MathSciNet  Google Scholar

  18. Murray, W., Ng, K.-M.: An algorithm for nonlinear optimization problems with binary variables. Comput. Optim. Appl. 47, 257–288 (2010)

    CrossRef  MathSciNet  Google Scholar

  19. Pardalos, P., Rosen, J.: Global optimization approach to the linear complementarity problem. SIAM J. Sci. Stat. Comput. 9(2), 341–353 (1988)

    CrossRef  MathSciNet  Google Scholar

  20. Raghavachari, M.: On connections between zero-one integer programming and concave programming under linear constraints. Oper. Res. 17(4), 680–684 (1969)

    CrossRef  MathSciNet  Google Scholar

  21. Sahraoui, Y., Bendotti, P., D'Ambrosio, C.: Real-world hydro-power unit-commitment: dealing with numerical errors and feasibility issues. Energy 184, 91–104 (2019)

    CrossRef  Google Scholar

  22. Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Chichester (1986)

    MATH  Google Scholar

  23. Taktak, R., D'Ambrosio, C.: An overview on mathematical programming approaches for the deterministic unit commitment problem in hydro valleys. Energy Syst. 8(1), 57–79 (2016). https://doi.org/10.1007/s12667-015-0189-x

    CrossRef  Google Scholar

Download references

Author information

Authors and Affiliations

  1. LIX CNRS, École Polytechnique, Institut Polytechnique de Paris, 91128, Palaiseau, France

    Leo Liberti

Corresponding author

Correspondence to Leo Liberti .

Editor information

Editors and Affiliations

  1. Matrosov Institute for System Dynamics and Control Theory SB RAS, Irkutsk, Russia

    Prof. Dr. Alexander Strekalovsky

  2. Sobolev Institute of Mathematics SB RAS, Novosibirsk, Russia

    Prof. Yury Kochetov

  3. Matrosov Institute for System Dynamics and Control Theory SB RAS, Irkutsk, Russia

    Prof. Tatiana Gruzdeva

  4. Matrosov Institute for System Dynamics and Control Theory SB RAS, Irkutsk, Russia

    Prof. Andrei Orlov

Rights and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Verify currency and authenticity via CrossMark

Cite this paper

Liberti, L. (2021). Continuous Reformulation of Binary Variables, Revisited. In: Strekalovsky, A., Kochetov, Y., Gruzdeva, T., Orlov, A. (eds) Mathematical Optimization Theory and Operations Research: Recent Trends. MOTOR 2021. Communications in Computer and Information Science, vol 1476. Springer, Cham. https://doi.org/10.1007/978-3-030-86433-0_14

Download citation

  • .RIS
  • .ENW
  • .BIB

  • DOI : https://doi.org/10.1007/978-3-030-86433-0_14

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-86432-3

  • Online ISBN: 978-3-030-86433-0

  • eBook Packages: Computer Science Computer Science (R0)

walkerbeffele.blogspot.com

Source: https://link.springer.com/chapter/10.1007/978-3-030-86433-0_14

0 Response to "Solving a Problem With a Continuous Variables and One Binary"

Post a Comment

Subscribe to: Post Comments (Atom)

Iklan Atas Artikel

Iklan Tengah Artikel 1

Iklan Tengah Artikel 2

Iklan Bawah Artikel