Advanced Search
MyIDEAS: Login

Networks formulations of mixed-integer programs

Contents:

Author Info

  • Conforti, Michele
Registered author(s):

    Abstract

    We consider mixed-integer sets described by system of linear inequalities in which the constraint matrix A is totally unimodular; the right-hand side is arbitrary vector; and a subset of the variables is required to be integer. We show that the problem of checking nonemptiness of a set of this types NP-complete, even in the case in which the linear system describes mixed-integer network flows with half-integral requirement on the nodes. This is in contrast to the case in which A is totally unimodular and contains at most two nonzeros per row. In this case, we provide an extended formulation for the convex hull of solutions whose constraint matrix is a dual-network matrix with an integral right-hand-side vector. The size of this formulation depends on the number of distinct fractional parts taken by the continuous variables in the extreme points of the convex hull of the given set. When this umber is polynomial in the dimension of A, the extended formulation is of polynomial size. If, in addition, the corresponding list of fractional parts can be computed efficiently, then our results provides a polynomial algorithm for the optimization problem over these sets. We show that there are instances for which this list is of exponential size, and we also give conditions under which it is short and can be efficiently computed. Finally, we show that these results provide a unified framework leading to polynomial-size extended formulations for several generalizations of mixing sets and lot-sizing sets studied in the last few years.

    Download Info

    If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
    File URL: http://hdl.handle.net/2078.1/28751-PDF_01
    Download Restriction: no

    Bibliographic Info

    Paper provided by Université catholique de Louvain in its series Open Access publications from Université catholique de Louvain with number info:hdl:2078.1/28751.

    as in new window
    Length:
    Date of creation: 2009
    Date of revision:
    Publication status: Published in Mathematics of Operations Research (2009) v.34, p.194-209
    Handle: RePEc:ner:louvai:info:hdl:2078.1/28751

    Contact details of provider:
    Web page: http://www.uclouvain.be

    Related research

    Keywords:

    References

    No references listed on IDEAS
    You can help add them by filling out this form.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as in new window

    Cited by:
    1. Herings, P. Jean-Jacques & Mauleon, Ana & Vannetelbosch, Vincent, 2006. "Farsightedly Stable Networks," Research Memoranda 041, Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization.
    2. Maniquet, François, 2008. "Social orderings for the assignment of indivisible objects," Journal of Economic Theory, Elsevier, vol. 143(1), pages 199-215, November.
    3. Caruso, Geoffrey, 2009. "Space-time patterns of urban sprawl, a 1D cellular automata and microeconomic approach," Open Access publications from Université catholique de Louvain info:hdl:2078.1/28730, Université catholique de Louvain.
    4. Dembour, Carole, 2009. "Investment in public infrastructure with spillovers and tax competition between contiguous regions," Open Access publications from Université catholique de Louvain info:hdl:2078.1/28497, Université catholique de Louvain.
    5. Peeters, Dominique, 2009. "Network autocorrelation," Open Access publications from Université catholique de Louvain info:hdl:2078.1/28748, Université catholique de Louvain.
    6. VAN VYVE, Mathieu & WOLSEY, Laurence & YAMAN, Hande, 2012. "Relaxations for two-level multi-item lot-sizing problem," CORE Discussion Papers 2012031, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    7. Thisse, Jacques-François, 2010. "Toward a unified theory of economic geography an urban economics," Open Access publications from Université catholique de Louvain info:hdl:2078.1/30406, Université catholique de Louvain.

    Lists

    This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

    Statistics

    Access and download statistics

    Corrections

    When requesting a correction, please mention this item's handle: RePEc:ner:louvai:info:hdl:2078.1/28751

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Fabrizio Tinti).

    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.

    If references are entirely missing, you can add them using this form.

    If the full references list an item that is present in RePEc, but the system did not link to it, you can help with 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 profile, as there may be some citations waiting for confirmation.

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