IDEAS home Printed from https://ideas.repec.org/p/cor/louvco/2000051.html
   My bibliography  Save this paper

Combining problem structure with basis reduction to solve a class of hard integer programs

Author

Listed:
  • LOUVEAUX, Quentin
  • WOLSEY, Laurence

Abstract

Recently Aardal et al. have successfully solved some small difficult equality constrained integer programs by using basis reduction to reformulate the problems as inequality constrained integer programs in a different space. Here we adapt theirmethod to solve integer programs that are larger, but have special structure. The practical problem motivating this work has variables xij and is a variant of the market share problem. More formally the problem can be viewed as finding a matrix X belongs Z exp.mn + satisfying XA = C,BX = D where A,B,C,D are matrices of compatible dimensions, and the approach requires us to find a reduced basis of the lattice L = {X belongs Z exp.mn : XA = 0,BX = 0}. The main topic of this paper is a study of the lattice L. It is shown that an integer basis of L can be obtained by taking the Kronecker product of vectors from integer bases of two much smaller lattices. Furthermore the resulting basis is a reduced basis if the integer bases of the two small lattices are reduced bases, and a suitable orderin is chosen. Finally some limited computational results are presented showing the benefits of making use of the problem structure.

Suggested Citation

  • LOUVEAUX, Quentin & WOLSEY, Laurence, 2000. "Combining problem structure with basis reduction to solve a class of hard integer programs," LIDAM Discussion Papers CORE 2000051, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    • Handle: RePEc:cor:louvco:2000051
    as

    Download full text from publisher

    File URL: https://sites.uclouvain.be/core/publications/coredp/coredp2000.html
    Download Restriction: no
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:cor:louvco:2000051. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Alain GILLIS (email available below). General contact details of provider: https://edirc.repec.org/data/coreebe.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.