Biq Mac Solver - Binary quadratic and Max cut Solver

This site offers you two services:

It is the final outcome of a joint project between Giovanni Rinaldi, IASI-CNR, Rome and Franz Rendl and Angelika Wiegele, Department of Mathematics, Alpen-Adria-Universität Klagenfurt.

You can choose between two options:

The algorithm used for the exact solution method is an SDP based Branch & Bound algorithm, described in [RRW10]. Bibtex entry:
        @article {RRW10,
        author={Rendl, Franz and Rinaldi, Giovanni and Wiegele, Angelika},
        title={Solving {M}ax-{C}ut to Optimality by Intersecting Semidefinite and Polyhedral Relaxations},
        journal = {Math. Programming},
        volume = {121},
        year = {2010},
        number = {2},
        pages = {307},
        }
For computing upper or lower bounds, respectively, we use the ConicBundle package of Christoph Helmberg.

While uploading, your data will be checked and the job queued. Once the job is finished or the time-limit of three hours is exceeded, you will receive an email with the output. Questions, comments and bug-reports please send to biqmac@aau.at.
Note: When submitting an instance, you agree that your data will be stored in a database and may be added to the Biq Mac Library (with a credit to the sender).



your input
exact solution method (for medium-sized instances)
bound computation (for large instances)
Biq: Solve min x'Qx s.t. x in {0,1}^n (description)
Mac: Compute a maximum cut (description)

Description of the input for solving quadratic 0-1 problems

To solve min x'Qx s.t. x in {0,1}^n you have to specify an email-address, your name, a name of the instance and we also kindly ask you to shortly mention the source of the problem. You have to upload a text-file, specifying matrix Q in the following format:

        n   m
        i_1 j_1 q_{i_1,j_1}
        i_2 j_2 q_{i_2,j_2}
        ...
        i_m j_m q_{i_m,j_m}
where n is the number of variables, m the number of entries of Q specified in the subsequent list. Q is assumed to be symmetric and indexed by numbers from 1 to n. Hence, if you specify entry (i,j) having value q, also entry (j,i) has value q. The values of Q can be integers or reals.
Your input file may start with comment lines. The first character of a comment line has to be this: #
Many examples can be found in the Biq Mac Library.

Description of graph input for solving Max-Cut problems

To compute a maximum cut you have to specify an email-address, your name, a graph name and we also kindly ask you to shortly mention the source of the problem. You have to upload a text-file, specifying your graph in the following format (rudy-output format):

        n   m
        h_1 t_1 c_{h_1,t_1}
        h_2 t_2 c_{h_2,t_2}
        ...
        h_m t_m c_{h_m,t_m}
where n is the number of nodes, m the number of edges and for each edge, h_i and t_i are the end-nodes and c_{h_i,t_i} the weight (integer or real). Nodes have to be numbered from 1 up to n. Loops will be ignored, multiple edges will be summed up.
Your input file may start with comment lines. The first character of a comment line has to be this: #
Many examples can be found in the Biq Mac Library.

This service is provided by Arbeitsgruppe OR, Department of Mathematics at the Alpen-Adria-Universität Klagenfurt. November 2007, July 2009.
The project was partially financed by the Marie-Curie Research Training Network ADONET.