IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v35y1987i6p820-831.html
   My bibliography  Save this article

Generating Alternative Mixed-Integer Programming Models Using Variable Redefinition

Author

Listed:
  • R. Kipp Martin

    (University of Chicago, Chicago, Illinois)

Abstract

Dropping the “complicating” constraints in a mixed-integer linear program often yields a “special structure subproblem” that can be reformulated using a different set of decision variables. Once the new variables have been identified, the entire problem can be reformulated in terms of the new variables. We develop a theory of variable redefinition based on relating the two sets of decision variables by a linear transformation, and describe methods for reformulating the special structure problem. The reformulated models have a more accurate linear relaxation than the problems from which they were derived, an important property within the context of linear programming-based branch-and-bound modeling approaches.

Suggested Citation

  • R. Kipp Martin, 1987. "Generating Alternative Mixed-Integer Programming Models Using Variable Redefinition," Operations Research, INFORMS, vol. 35(6), pages 820-831, December.
    • Handle: RePEc:inm:oropre:v:35:y:1987:i:6:p:820-831
    DOI: 10.1287/opre.35.6.820
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.35.6.820
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.35.6.820?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

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


    Cited by:

    1. Jans, Raf, 2010. "Classification of Dantzig-Wolfe reformulations for binary mixed integer programming problems," European Journal of Operational Research, Elsevier, vol. 204(2), pages 251-254, July.
    2. François Vanderbeck, 2000. "On Dantzig-Wolfe Decomposition in Integer Programming and ways to Perform Branching in a Branch-and-Price Algorithm," Operations Research, INFORMS, vol. 48(1), pages 111-128, February.
    3. Pedro Gazmuri & Sergio Maturana, 2001. "Developing and Implementing a Production Planning DSS for CTI Using Structured Modeling," Interfaces, INFORMS, vol. 31(4), pages 22-36, August.
    4. Luis Gouveia, 1998. "Using Variable Redefinition for Computing Lower Bounds for Minimum Spanning and Steiner Trees with Hop Constraints," INFORMS Journal on Computing, INFORMS, vol. 10(2), pages 180-188, May.
    5. Awi Federgruen & Joern Meissner & Michal Tzur, 2007. "Progressive Interval Heuristics for Multi-Item Capacitated Lot-Sizing Problems," Operations Research, INFORMS, vol. 55(3), pages 490-502, June.
    6. VAN VYVE, Mathieu, 2011. "Linear prices for non-convex electricity markets: models and algorithms," LIDAM Discussion Papers CORE 2011050, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    7. Crema, Alejandro, 1997. "A contraction algorithm for the multiparametric integer linear programming problem," European Journal of Operational Research, Elsevier, vol. 101(1), pages 130-139, August.
    8. Minjiao Zhang & Simge Küçükyavuz & Hande Yaman, 2012. "A Polyhedral Study of Multiechelon Lot Sizing with Intermediate Demands," Operations Research, INFORMS, vol. 60(4), pages 918-935, August.
    9. Wolsey, Laurence A., 1995. "Progress with single-item lot-sizing," European Journal of Operational Research, Elsevier, vol. 86(3), pages 395-401, November.
    10. Selvaprabu Nadarajah & Andre A. Cire, 2020. "Network-Based Approximate Linear Programming for Discrete Optimization," Operations Research, INFORMS, vol. 68(6), pages 1767-1786, November.
    11. Margarita P. Castro & Andre A. Cire & J. Christopher Beck, 2022. "Decision Diagrams for Discrete Optimization: A Survey of Recent Advances," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 2271-2295, July.
    12. Zeger Degraeve & Raf Jans, 2007. "A New Dantzig-Wolfe Reformulation and Branch-and-Price Algorithm for the Capacitated Lot-Sizing Problem with Setup Times," Operations Research, INFORMS, vol. 55(5), pages 909-920, October.
    13. S. Rajagopalan, 1998. "Capacity Expansion and Equipment Replacement: A Unified Approach," Operations Research, INFORMS, vol. 46(6), pages 846-857, December.
    14. Gouveia, Luis & Requejo, Cristina, 2001. "A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem," European Journal of Operational Research, Elsevier, vol. 132(3), pages 539-552, August.
    15. Amin Hosseininasab & Willem-Jan van Hoeve, 2021. "Exact Multiple Sequence Alignment by Synchronized Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 721-738, May.

    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:inm:oropre:v:35:y:1987:i:6:p:820-831. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.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.