This site offers you two services:

- solving unconstrained binary quadratic programs and
- computing a maximum cut of edge-weighted graphs.

You can choose between two options:

- using an exact algorithm, i.e., an SDP based Branch & Bound algorithm or
- computing upper and lower bounds only using the ConicBundle.

@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).

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.

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. |