| Records |
| Author |
Acuna, V.; Ferreira, C.E.; Freire, A.S.; Moreno, E. |
| Title |
Solving the maximum edge biclique packing problem on unbalanced bipartite graphs |
Type |
|
| Year |
2014 |
Publication |
Discrete Applied Mathematics |
Abbreviated Journal |
Discret Appl. Math. |
| Volume |
164 |
Issue |
|
Pages |
2-12 |
| Keywords |
Maximum edge biclique packing; Branch-and-price; Metabolic networks; Product bundling |
| Abstract |
A biclique is a complete bipartite graph. Given an (L, R)-bipartite graph G = (V, E) and a positive integer k, the maximum edge biclique packing (num') problem consists in finding a set of at most k bicliques, subgraphs of G, such that the bicliques are vertex disjoint with respect to a subset of vertices S, where S E {V, L, R}, and the number of edges inside the bicliques is maximized. The maximum edge biclique (mEs) problem is a special case of the MEBP problem in which k = 1. Several applications of the MEB problem have been studied and, in this paper, we describe applications of the MEBP problem in metabolic networks and product bundling. In these applications the input graphs are very unbalanced (i.e., IRI is considerably greater than ILI), thus we consider carefully this property in our models. We introduce a new formulation for the MEB problem and a branch-and-price scheme, using the classical branch rule by Ryan and Foster, for the MEBP problem. Finally, we present computational experiments with instances that come from the described applications and also with randomly generated instances. (C) 2011 Elsevier B.V. All rights reserved. |
| Address |
[Acuna, V.] Univ Lyon 1, F-69622 Villeurbanne, France, Email: afreire@ime.usp.br |
| Corporate Author |
|
Thesis |
|
| Publisher |
Elsevier Science Bv |
Place of Publication |
|
Editor |
|
| Language |
English |
Summary Language |
|
Original Title |
|
| Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
| Series Volume |
|
Series Issue |
|
Edition |
|
| ISSN |
0166-218x |
ISBN |
|
Medium |
|
| Area |
|
Expedition |
|
Conference |
|
| Notes |
WOS:000332427400002 |
Approved |
|
| Call Number |
UAI @ eduardo.moreno @ |
Serial |
361 |
| Permanent link to this record |
| |
|
| |
| Author |
Freire, A.S.; Moreno, E.; Vielma, J.P. |
| Title |
An integer linear programming approach for bilinear integer programming |
Type |
|
| Year |
2012 |
Publication |
Operations Research Letters |
Abbreviated Journal |
Oper. Res. Lett. |
| Volume |
40 |
Issue |
2 |
Pages |
74-77 |
| Keywords |
Bilinear programming; Integer linear programming; Product bundling |
| Abstract |
We introduce a new Integer Linear Programming (ILP) approach for solving Integer Programming (IP) problems with bilinear objectives and linear constraints. The approach relies on a series of ILP approximations of the bilinear P. We compare this approach with standard linearization techniques on random instances and a set of real-world product bundling problems. (C) 2011 Elsevier B.V. All rights reserved. |
| Address |
[Moreno, Eduardo] Univ Adolfo Ibanez, Fac Sci & Engn, Santiago, Chile, Email: afreire@ime.usp.br |
| Corporate Author |
|
Thesis |
|
| Publisher |
Elsevier Science Bv |
Place of Publication |
|
Editor |
|
| Language |
English |
Summary Language |
|
Original Title |
|
| Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
| Series Volume |
|
Series Issue |
|
Edition |
|
| ISSN |
0167-6377 |
ISBN |
|
Medium |
|
| Area |
|
Expedition |
|
Conference |
|
| Notes |
WOS:000301331700002 |
Approved |
|
| Call Number |
UAI @ eduardo.moreno @ |
Serial |
201 |
| Permanent link to this record |
| |
|
| |
| Author |
Freire, A.S.; Moreno, E.; Yushimito, W.F. |
| Title |
A branch-and-bound algorithm for the maximum capture problem with random utilities |
Type |
|
| Year |
2016 |
Publication |
European Journal Of Operational Research |
Abbreviated Journal |
Eur. J. Oper. Res. |
| Volume |
252 |
Issue |
1 |
Pages |
204-212 |
| Keywords |
Facility location; Branch and bound; Maximum capture; Random utility model |
| Abstract |
The MAXIMUM CAPTURE PROBLEM WITH RANDOM UTILITIES seeks to locate new facilities in a competitive market such that the captured demand of users is maximized, assuming that each individual chooses among all available facilities according to the well-know a random utility model namely the multinomial logit. The problem is complex mostly due to its integer nonlinear objective function. Currently, the most efficient approaches deal with this complexity by either using a nonlinear programing solver or reformulating the problem into a Mixed-Integer Linear Programing (MILP) model. In this paper, we show how the best MILP reformulation available in the literature can be strengthened by using tighter coefficients in some inequalities. We also introduce a new branch-and-bound algorithm based on a greedy approach for solving a relaxation of the original problem. Extensive computational experiments are presented, bench marking the proposed approach with other linear and non-linear relaxations of the problem. The computational experiments show that our proposed algorithm is competitive with all other methods as there is no method which outperforms the others in all instances. We also show a large-scale real instance of the problem, which comes from an application in park-and-ride facility location, where our proposed branch-and-bound algorithm was the most effective method for solving this type of problem. (C) 2015 Elsevier B.V. All rights reserved. |
| Address |
[Moreno, Eduardo; Yushimito, Wilfredo F.] Univ Adolfo Ibanez, Fac Sci & Engn, Santiago, Chile, Email: afreire@ime.usp.br; |
| Corporate Author |
|
Thesis |
|
| Publisher |
Elsevier Science Bv |
Place of Publication |
|
Editor |
|
| Language |
English |
Summary Language |
|
Original Title |
|
| Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
| Series Volume |
|
Series Issue |
|
Edition |
|
| ISSN |
0377-2217 |
ISBN |
|
Medium |
|
| Area |
|
Expedition |
|
Conference |
|
| Notes |
WOS:000371939700018 |
Approved |
|
| Call Number |
UAI @ eduardo.moreno @ |
Serial |
601 |
| Permanent link to this record |
