Convex envelope results and strong formulations for a class of mixed-integer programs

Date

1996-06-01

Author

Denizel, M
Erenguc, SS
Sherali, HD

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

240
views

0
downloads

In this article we present a novel technique for deriving the convex envelope of certain nonconvex fixed-charge functions of the type that arise in several related applications that have been considered in the literature. One common attribute of these problems is that they involve choosing levels for the undertaking of several activities. Two or more activities share a common resource, and a fixed charge is incurred when any of these activities is undertaken at a positive level. We consider nonconvex programming formulations for these problems in which the fixed charges are expressed in the form of concave functions. With the use of the developed convex envelope results, we show that the convex envelope relaxations of the nonconvex formulations lead to the linear programming relaxations of the strong IP/MIP formulations of these problems. Moreover, our technique for deriving convex envelopes offers a useful construct that could be exploited in other related contexts as well. (C) 1996 John Wiley & Sons, Inc.

Subject Keywords

Flexible manufacturing systems

URI

https://hdl.handle.net/11511/66527

Journal

NAVAL RESEARCH LOGISTICS

Collections

Department of Industrial Design, Article

Suggestions

OpenMETU
Core

Hierarchical and decentralized multitasking control of discrete event systems Schmidt, Klaus Verner; Cury, José E. R. (2007-12-01) In this paper, a hierarchical and decentralized approach for composite discrete-event systems (DES) that have to fulfill multiple tasks is elaborated. Colored marking generators that can distinguish classes of tasks are used as the system model, and a colored abstraction procedure as well as sufficient conditions for nonblocking and hierarchically consistent control are developed. It is shown that the computational complexity for supervisor computation is reduced. A flexible manufacturing system example dem...
Noncommutative affine spaces and Lie-complete rings Dosi, Anar (2015-02-01) In this paper, we investigate the structure sheaves of an (infinite-dimensional) affine NC-space A(nc)(x) affine Lie-space A(lich)(x), and their nilpotent perturbations A(nc,q)(x) and A(lich),(x)(q) respectively. We prove that the schemes A(nc)(x) and A(lich)(x) are identical if and only if x is a finite set of variables, that is, when we deal with finite-dimensional noncommutative affine spaces. For each (Zariski) open subset U subset of X = Spec(C vertical bar x vertical bar), we obtain the precise descri...
Efficient Computation of Green's Functions for Multilayer Media in the Context of 5G Applications Mittra, Raj; Özgün, Özlem; Li, Chao; Kuzuoğlu, Mustafa (2021-03-22) This paper presents a novel method for effective computation of Sommerfeld integrals which arise in problems involving antennas or scatterers embedded in planar multilayered media. Sommerfeld integrals that need to be computed in the evaluation of spatial-domain Green's functions are often highly oscillatory and slowly decaying. For this reason, standard numerical integration methods are not efficient for such integrals, especially at millimeter waves. The main motivation of the proposed method is to comput...
Flexible assembly line design problem with fixed number of workstations Barutçuoğlu, Şirin; Azizoğlu, Meral; Department of Industrial Engineering (2009) In this thesis, we study a Flexible Assembly Line Design problem. We assume the task times and equipment costs are correlated in the sense that for all tasks the cheaper equipment gives no smaller task time. Given the cycle time and number of workstations we aim to find the assignment of tasks and equipments to the workstations that minimizes the total equipment cost. We study a special case of the problem with identical task times. For the general case, we develop a branch and bound algorithm that uses pow...
Discrete linear Hamiltonian systems: Lyapunov type inequalities, stability and disconjugacy criteria Zafer, Ağacık (2012-12-15) In this paper, we first establish new Lyapunov type inequalities for discrete planar linear Hamiltonian systems. Next, by making use of the inequalities, we derive stability and disconjugacy criteria. Stability criteria are obtained with the help of the Floquet theory, so the system is assumed to be periodic in that case.

Citation Formats

M. Denizel, S. Erenguc, and H. Sherali, “Convex envelope results and strong formulations for a class of mixed-integer programs,” NAVAL RESEARCH LOGISTICS, pp. 503–518, 1996, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/66527.