Introduction

The basic assumption of many optimization models in operations research is that the variables are continuous. But in many real problems, decision variables are discrete. These problems are called integer programming models. If all decision variables are integer variables, the resulting model is called integer programming model. If all the variables are zero or one (doing or not doing), it is called zero-one integer programming model.

To solve these problems, there are limited softwares that need to be installed and know the programming language of those softwares. In order to make it easy to solve zero-one integer programming models, the Optimization City group has designed and developed an online solver. In the following, we will review how to use this online solver.

Instruction of using online solver of zero-one integer programming

 The GUI of the online solver of the zero-one integer programming is as follows.

Problem input

To find the optimal solution of the zero-one integer programming problem, the required inputs are as follows:

n: number of decision variables

m: number of constraints

a: This matrix has m+1 rows and n+1 columns. The coefficients of the decision variables are placed in the constraints in this matrix. The first row and first column of this matrix will be zero.

b: This vector has m+1 components, which are the values on the right hand side of the constraints.

c: This vector has n+1 components, which are the coefficients of the decision variables in the objective function.

Note: model constraints MUST be defined as less than or equal (≤). If the model is in the form of equality (=), it is possible to convert the equality constraint into less than or equal  and greater than or equal constraints, and by converting the greater than or equal constraints into less than or equal constraint, the constraints can be converted into a standard form.

Note: This problem should be defined as minimization.

Example: To teach how to use this online solver, we use the following example. A zero-one integer programming model with four variables and three constraints is defined as follows.

Solution: The input information for the given model is as follows.

Entering information in the online solver for the zero-one integer programming is as follows.

After entering the data, we click on the RUN button.

The result of running the algorithm is as follows.

In the output, the phrase “Optimal solution found” means that the model has a limited optimal solution.

In front of “Solution vector”, the optimal values of the decision variables are reported, which in this example we have:

In the last part of the output, the value of the optimal objective function is reported, which in this example is equal to 35.