Reach Us
+44 1704 335730

^{1}Graduate School of Mathematics, University of Sumatera Utara

^{2}Graduate School of Computer Science, University of Sumatera Utara

- *Corresponding Author:
- Herman Mawengkang

Graduate School of Mathematics, University of Sumatera Utara

**E-mail:**[email protected]

**Received date:** January 2012; **Revised date:** March 2012; **Accepted date:** April 2012

**Visit for more related articles at** Global Journal of Technology and Optimization

The special class of a nonlinear mathematical programming problem which is addressed in this paper has a structure characterized by a subset of variables restricted to assume discrete values, which are linear and separable from the continuous variables. The strategy of releasing non-basic variables from their bounds, combined with the “active constraint” method and the notion of super-basics, has been developed for efficiently tackling the problem. After solving the problem by ignoring the integrality requirements, this strategy is used to force the appropriate non-integer basic variables to move to their neighborhood integer points. A study of criteria for choosing a non-basic variable to work with in the integer zing strategy has also been made. Successful implementation of these algorithms was achieved on various test problems. The results show that the proposed integer zing strategy is promising in tackling certain classes of mixed integer nonlinear programming problems.

Mixed integer programming, nonlinear programming, direct search, neighbourhood search, large scale optimization.

Mixed Integer Nonlinear Programming (MINLP) refers to mathematical programming with continuous and discrete variables and nonlinearities in the objective function and constraints. The special class of Mixed-Integer nonlinear programming problem which is addressed in this paper is to assume discrete values, which are linear and separable from the continuous variables. This problem is defined by the following model.

Where and are continuous and generally well-behaved functions defined on the ndimensional compact polyhedral convex set is a discrete set, say the nonnegative integer points of some convex polytope, where for most applications Y is the unit hypercube are respectively matrices and vectors of comfortable dimensions; the vectors are column vectors unless specified otherwise.

There are various applications for the MINLP model, including the process industry and the financial, engineering, management science and operations research sectors. It includes problems in process flow sheets, portfolio selection, batch processing in chemical engineering (consisting of mixing, reaction, and centrifuge separation), and optimal design of gas or water transmission networks. Other areas of interest include the automobile, aircraft, and VLSI manufacturing areas. An impressive collection of MINLP applications can be found in [9] and [10]. The needs in such diverse areas have motivated research and development in MINLP solver technology, particularly in algorithms for handling large-scale, highly combinatorial and highly nonlinear problems.

Methods for solving MINLPs include innovative approaches and related techniques taken and extended from MIP, such as, Outer Approximation (OA) methods [5,7,10], Branch-and- Bound (B&B) [1,11,16], Extended Cutting Plane methods [19], and Generalized Bender’s Decomposition (GBD) [8] for solving MINLPs have been discussed in the literature since the early 1980’s. These approaches generally rely on the successive solutions of closely related NLP problems. For example, B&B starts out forming a pure continuous NLP problem by dropping the integrality requirements of the discrete variables (often called the relaxed MINLP or RMINLP). Moreover, each node of the emerging B&B tree represents a solution of the RMINLP with adjusted bounds on the discrete variables.

Heuristic approaches to solving MINLPs include Variable Neighbourhood Search [13], automatically tuned variable fixing strategies [2], Local Branching [14], feasible neighbourhood search [14], Feasibility Pump [3,4,6], heuristics based on Iterative Rounding [15]. Recently [12] propose a MINLP heuristic called the Relaxed-Exact-Continuous-Integer Problem Exploration (RECIPE) algorithm. The algorithm puts together a global search phase based on Variable Neighbourhood Search [13] and a local search phase based on a MINLP heuristic. In heuristic approaches, however, one of the main algorithmic difficulties connected to MINLPs is to find a feasible solution.

From the worst-case complexity point of view, finding a feasible MINLP solution is as hard as finding a feasible Nonlinear Programming solution, which is NP-hard [14].

Due to the fact that the functions in MINLPs are not smooth, therefore in this paper we use a direct search method, known as unconstrained optimization techniques that do not explicitly use derivatives. More information regarding to direct search method in optimization can be found in [19].

In this paper we address a strategy of releasing nonbasic variables from their bounds, combined with the “active constrained” method and the notion of superbasics for efficiently tackling a particular class of MINLP problems.

The rest of this paper is organized as follows. In Section 2 we give a brief notion of neighbourhood search.Tthe basic approach of the proposed method is presented in Section 3. How to derive the proposed method is given in Section 4. The algorithm is presented in Section 5. Section 6 addresses a computational experience. The conclusions can be found in Section 7.

It should be noted that, generally, in integer programming the reduced gradient vector, which is normally used to detect an optimality condition, is not available, even though the problems are convex. Thus we need to impose a certain condition for the local testing search procedure in order to assure that we have obtained the “best” suboptimal integer feasible solution.

Scarf [18] has proposed a quantity test to replace the pricing test for optimality in the integer programming problem. The test is conducted by a search through the neighbours of a proposed feasible point to see whether a nearby point is also feasible and yields an improvement to the objective function.

Let be an integer point belongs to a finite set of neighbourhood We define a neighbourhood system associated with that is, if such an integer point satisfies the following two requirements

With respect to the neighbourhood system mentioned above, the proposed integerizing strategy can be described as follows.

Given a non-integer component, of an optimal vector , The adjacent points of being considered are If one of these points satisfies the constraints and yields a minimum deterioration of the optimal objective value we move to another component, if not we have integerfeasible solution.

Let be the integer feasible point which satisfies the above conditions. We could then say if implies that the point is either infeasible or yields an inferior value to the objective function obtained with respect to In this case is said to be an “optimal” integer feasible solution to the integer programming problem. Obviously, in our case, a neigbourhood search is conducted through a proposed feasible points such that the integer feasible solution would be at the least distance from the optimal continuous solution.

Before we proceed to the case of MINLP problems, it is worthwhile to discuss the basic strategy of process for linear case, i.e., Mixed Integer Linear Programming (MILP) problems. Consider a MILP problem with the following form

Minimize (5)

Subject to

integer for some (8)

A component of the optimal basic feasible vector to MILP solved as continuous can be written as

Note that, this expression can be found in the final tableau of Simplex procedure. If is an integer variable and we assume that is not an integer, the partitioning of into the integer and fractional components is that given

suppose we wish to increase to its nearest integer, Based on the idea of suboptimal solutions we may elevate a particular non-basic variable, say above its bound of zero, provided as one of the element of the vector is negative. Let be amount of movement of the non variable such that the numerical value of scalar is integer. Referring to Eqn. (9), can then be expressed as

while the remaining nonbasic stay at zero. It can be seen that after substituting (10) into (11) for and taking into account the partitioning of given in (10), we obtain

Thus, is now an integer

It is now clear that a non-basic variable plays an important role to integrate the corresponding basic variable. Therefore, the following result is necessary in order to confirm that must be a non-integer variable to work with in integer zing process.

**Theorem 1: ***Suppose the MILP problem (5)-(8) has an optimal
solution, then some of the non-basic variables. *

*must be non-integer variables.*

**Proof**

Solving the problem as continuous slack variables (which are non-integer, except in the case of equality constraint) If we assume that the vector of basic variables consists of all the slack variables then all integer variables would be in the non-basic vector and therefore integer valued.

It is clear that the other components, of vector will also be affected as the numerical value of the scalar increases to Consequently, if some element of vector i.e., are positive, then the corresponding element of will decrease, and eventually may pass through zero. However, any component of vector x must not go below zero due to the non-negativity restriction. Therefore, a formula, called the minimum ratio test is needed in order to see what is the maximum movement of the non-basic is such that all components of x remain feasible. This ratio test would include two cases.

1. A basic variable decreases to zero (lower bound)

2. The basic variable, increases to an integer.

Specifically, corresponding to each of these two cases above, one would compute

How far one can release the nonbasic from its bound of
zero, such that vector *x *remains feasible, will depend on the
ratio test given below

(14)

obviously, if one of the basic variable will hit the lower bound before becomes integer. If the numerical value of the basic variable will be integer and feasibility is still maintained. Analogously, we would be able to reduce the numerical value of the basic variable to its closest integer In this case the amount of movement of a particular non-basic variable, corresponding to any positive element of vector is given by

(15)

In order to maintain the feasibility, the ratio test is still needed. Consider the movement of a particular non-basic variable, as expressed in Eqns.(11) and (15).

The only factor that one needs to calculate is the corresponding element of vector α. A vector can be expressed as

Therefore, in order to get a particular element of vector we should be able to distinguish the corresponding column of matrix Suppose we need the value of element letting be the th column vector of we then have

(17)

Subsequently, the numerical value of αkj* can be obtained from

(18)

in Linear Programming (LP) terminology the operation conducted in Eqns. (17) and (18) is called the pricing operation. The vector of reduced costs is used to measure the deterioration of the objective function value caused by releasing a nonbasic variable from its bound. Consequently, in deciding which nonbasic should be released in the integer zing process, the vector must be taken into account, such that deterioration is minimized. Recall that the minimum continuous solution provides a lower bound to any integer-feasible solution. Nevertheless, the amount of movement of particular non-basic variable as given in Eqns. (11) or (15), depends in some way on the corresponding element of vector Therefore it can be observed that the deterioration of the objective function value due to releasing a non-basic variable so as to integer rize a basic variable may be measured by the ration

(19)

where means the absolute value of scalar a.

In order to minimize the detonation of the optimal continuous solution we then use the following strategy for deciding which non-basic variable may be increased from its bound of zero, that is,

From the “active constraint” strategy and the partitioning of the constraints corresponding to basic superbasic and nonbasic variables we can write

or

The basis matrix is assumed to be square and nonsingular, we get

(24)

Where

Expression (23) indicates that the non-basic variables are being held equal to their bound. It is evident through the “nearly” basic expression of Eqn. (24), the integer zing strategy discussed in the previous section, designed for MILP problem can be implemented. Particularly, we would be able to release a nonbasic variable from its bound, Eqn.(23) and exchange it with a corresponding basic variable in the integer zing process, although the solution would be degenerate. Furthermore, the Theorem (1) above can also be extended for MINLP problem.

**Theorem 2:** *Suppose the MINLP problem has a bounded
optimal continuous solution, then we can always get a noninteger in the optimum basic variable vector.*

**Proof**

1. If these variables are non-basic, they will be at their bound. Therefore they have integer value.

2. If is super-basic, it is possible to make basic and bring in a non-basic at its bound to replace it in the super-basic. However, the ratio test expressed in (14) cannot be used as a tool to guarantee that the integer solution optimal found gill remains in the feasible region. Instead, we use the feasibility test from Minos in order to check whether the integer solution is feasible or infeasible.

**Pivoting**

Currently, we are in a position where particular basic variable, is being integer zed, thereby a corresponding non-basic variable, is being released from its bound of zero. Suppose the maximum movement of satisfies

such that is integer valued to exploit the manner of changing the basis in linear programming, we would be able to move into (to replace ) and integer-valued into S in order to maintain the integer solution. We now have a degenerate solution since a basic variable is at its bound. The integer zing process continues with a new set In this case, eventually we may end up with all of the integer variables being super-basic.

**Theorem 3:** *A suboptimal solution exists to the MILP and
MINLP problem in which all of the integer variables are superbasic.*

**Proof**

1. If all of the integer variables are in N, then they will be a bound.

2. If an integer variable is basic it is possible to either

• Interchange it with a super-basic continuous variable, or

• Make this integer variable super-basic and bring in a non-basic at its bound to replace it in the basis which gives a degenerate solution.

The other case which can happen is that different basic variables may hit its bound beforebecomes integer. Or in other words, we are in a situation where

In this case we move the basic variable into and its position in the basic variable vector would be replaced by nonbasic Noteis still a non-integer basic variable with a new value.

After solving the relaxed problem, the procedure for searching a suboptimal but integer-feasible solution from an optimal continuous solution can be described as follows.

Let

be the (continuous) solution of the relaxed problem, is the integer component of non-integer variable and is the fractional component.

Stage 1.

**Step 1.** Get row the smallest integer infeasibility, such that

**Step 2.** Calculate

this is a pricing operation

**Step 3.** Calculate

With corresponds to

*I. For non-basic j at lower bound*

calculate

and calculate

and calculate

II. For* non-basic j at upper bound*

Otherwise go to next non-integer non-basic or superbasic (if available). Eventually the columnis to be increased form LB or decreased from UB. If none go to next

**Step 4.** Calculate

**Step 5.** Ratio test; there would be three possibilities for the
basic variables in order to stay feasible due to the
releasing of non-basic from its bounds.

If lower bound

Let

the maximum movement of depends on:

If upper bound

Let

the maximum movement of depends on:

**Step 6.** Exchanging basis for the three possibilities

1. If becomes non-basic at lower bound

becomes basic (replaces

•stays basic (non-integer)

2. If or becomes non-basic at upper bound

becomes basic (replaces

• stays basic (non-integer)

3. If

•becomes basic (replaces

• becomes super-basic at integer-valued

**Step 7. **If row go to Stage 2, otherwise

Repeat from step 1.

**Stage 2.** Adjust integer feasible super-basics using line search
approach.

The super-basics can be varied at some points subject to preserving of the basic variables. Thus a search through the neighborhood system, as defined in Section 2, will verify the (local) optimality of the integerfeasible solution obtained.

Define as the index of the super-basic variable with the smallest fractional component, and ` is the index set of the basic variable. The integer line search would proceed as follows.

Step 1. This is basically a one dimensional steepest descent.

Choose The criterion for selecting will be that of maximum reduced cost

Step 2. Calculate Also determine direction of move – check sign of and adjust the unit tests in Step 3 in light of this.

Step 3. Check that a unit move is possible:

Step 4. Move by 1 unit; check that objective improves, i.e. search in the neighbourhood system.

**Mathematical Statement of the problem**

This synthesis problem is the one of simultaneously determining the optimal structural and operating parameters for a process so as to satisfy a given design specification. The decision variables are defined as follows.

is a binary variable which is associated with each process unit (piece of equipment) to denote its potential existence in the final optimal configuration, and

are the continuous which represent process parameters such as flow rates of materials.

Generally, the objective is to minimize the annual costs, including both investment and operation costs.

Minimize

Subject to

The above formulation contains 8 binary variables, 9 bounded continuous variables, 23 inequality constraints. Nonlinearities appear in the objective function and in four inequalities.

**Discussion of the results**

We solved this problem using PC with processor Intel(R) Core
(TM) i5-2300 CPU @ 280 GHZ and RAM 4.00GB. The
continuous optimal solution was obtained by using NLP
software. Only one binary variable is integer-valued (at its lower
bound) in the continuous solution. A binary variable is in
super-basic set with non integer value. We then moved this
variable to its closest integer by using truncation strategy and
kept it super-basic. We must check the feasibility of the
corresponding basic variables due to this movement. We integer
zed the remaining non-integer binary variables by using our
proposed integer zing strategy. Both the continuous and the
integer results of the synthesis problem can be seen in the **Table 1**.

Our objective result is in agreement with the result obtained by [2] .

This is a marketing problem faced by a firm which wishes to position a new brand product in an existing product class. It is natural that individual choices for his/her most prefered products are influenced essentially by the perceptions and values of the products (e. g. the design of the product). Individuals usually differ in their choice of an object out of an existing set, and they would also differ if asked to specify an ideal object. Due to these differences, the aim of the problem considered here is to optimally design a new product in order to attract the largest number of consumers

**Mathematical Statement of the Problem**

The mathematical programming formulation of the problem is due to Duran and Grossmann [5].

Let be the number of consumers who are a representative sample of the common population for a certain price range of a product class. Also, let be the number of an existing product (e. g. different brands of cars) in a market which are evaluated by consumers and are located in a multi attribute space of dimension We then define

ideal point on attribute for the ith consumer,

- weight given to attribute by the ith consumer

- ideal point on attribute for the ith consumer,

Further more, a region (hyper ellipsoid) defining the distance of each consumers to the ideal point can be determined in terms of the existing product, in a way to produce a formulation such that each consumer will select a product which is closest to his/her ideal point. It was mentioned above that the objective of the problem is to optimally design a new product so as to attract the largest number of consumers.

Duran and Grossmann [5] have extended the scope of the positioning problem by introducing the revenue of the firm from the new product sales to consumer as well as a function for representing the cost of reaching locations of the new product within an attribute space. Now, the objective of the problem would be to maximize the profits the firm. The binary variable is introduced for ecah consumer to denote whether he/she is attracted by the new product or not.

Consider a positioning problem in which there are 10 existing products 25 consumers and attributes The algebraic representation of such a problem can be written as follows.

where

The data for the coordinates of existing product ideal points and attribute weights can be obtained in Duran and Grossmann (1986b).

It can be seen that the above formulation is a MINLP model and it containts 25 binary variables, 5 continuous bounded variables, 30 inequality constraints (25 of them acting nonlinearly) and a nonlinear objective function.

**Discussion of the Result**

We solved the problem on PC with processor Intel(R) Core
(TM) i5-2300 CPU @ 280 GHZ and RAM 4.00GB. We used
our Nonlinear Programming software in order to get the
optimal continuous solution. The results are presented in Tabel
2. It can be observed that five binary variables have had integer
value (all of them are in upper bound). The binary variable happens to be a superbasic in the continuous result with noninteger
value. We moved this variable to its closest integer by
using a truncation strategy and kept the integer result as
superbasic. The corresponding basic variables would be
affected due to this movement. Therefore it is necessary to
check the feasibility of the results. The proposed integerizing
algorithm was then implemented on the remaining non-integer
binary variables. The integer results can also be found in **Table
2**.

It is interesting to note that our result is slightly better that Duran and Grossmann’s [5] result The binary variable has a value of 1.0 in our result instead of 0.0 as in Duran and Grossmann’s result. The total computational time to get the integer result by using our proposed algorithm is 10.98 seconds.

This paper has presented a direct search method for achieving integer-feasibility for a class of mixed-integer nonlinear programming problems in a relatively short time. The direct search approach used the strategy of releasing nonbasic variable from their bounds, combined with the “active constraint” method and the notion of superbasic. After solving a problem by ignoring the integrality requirements, this strategy is used to force the appropriate non-integer basic variables to move to their neighborhoods integer points.

A study of the criteria for choosing a nonbasic variable to work with in the integerizing strategy has also been made. The number of integerizing steps would be finite if the number of integer variables contained in the problem are finite. However, it should be noted that the computational time for the integerizing process does not necessarily depend on the number of integer variables, since many of the integer variables may have an integer value at the continuous optimal solution.

The new direct search method has benn shown to be successful on a range of problems, while not always able to achieve global optimality. In a number of cases to obtain the suboptimal point is acceptable, since the exponential complexity of the combinatorial problems in general precludes branch-and-bound, except on small to medium problems.

Computational testing of the procedure presented this paper has demonstrated that it is a viable approach for large problems.

- P. Belotti, J. Lee, L. Liberti, F. Margot, A. Wachter, Branching and Bounds Tightening Techniques for nonconvex MINLP, Optimization Methods and Software, 2009, vol. 24(4): pp. 597-634.
- T. Berthold and A. Gleixner. Undercover-Primal MINLP Heuristic. In P. Bonami, L. Liberti, A. Miller and A. Sartenaer (eds). Proceedings of the European Workshop on MINLP, Marseille, 2010, pp 103-113.
- C. D’Ambrosio, A. Frangioni, L. Liberti, A.Lodi. Experiments with a Feasibility Pump approachfor nonconvex MINLPs. In: P. Festa(ed) Proceedings of the 9th Synposiumon Experimental Algorithms (SEA 2010), Lecture Notes in Computer Science, Springer, Berlin, 2010, vol. 6049.
- C. D’Ambrosio, A. Frangioni, L. Liberti, A. Lodi. A storm of Feasibility Pump for non-convex MINLP. Tech. Rep. DEIS, Universita di Bologna, 2010, OR-10-13.
- M. A. Duran and I. E Grossmann, An Outer- Approximation Algorithm For a class of Mixed-Integer Nonlinear Programs, Mathematical Programming, 1986, 36: 307.
- M. Fischetti, F. Glover, A. Lodi. The Feasibility Pump. Mathematical Programming, 2005, vol. A 104(1), pp. 91- 104.
- Roger Fletcher and Sven Leyffer, Solving Mixed Integer Nonlinear Programming by Outer Approximation, Mathematical Programming, 1994, Vol. 66: 327.
- A.M. Geoffrion. A Generalized Benders Decomposition, J. Op-tim. Theory Appl., 1972, vol. 10 (4), pp. 237–260
- I.E. Grossmann and N.V. Sahinidis (eds). Special Issue on Mixed-integer Programming and its Application to Engineering, Part I, Optim. Eng., Kluwer Academic Publishers, Netherlands, 2002, vol. 3 (4)
- I.E. Grossmann and N.V. Sahinidis (eds). Special Issue on Mixed-integer Programming and its Application to Engineering, Part II, Optim. Eng., Kluwer Academic Publishers, Netherlands, 2002, vol. 4 (1)
- O. K. Gupta and A. Ravindran. Branch and Bound Experiments in Convex Nonlinear Integer Programming, Manage Sci., 1985, vol. 31 (12), pp. 1533–1546.
- L. Liberti, N. Miladenovie, G. Nannicini. A Recipe for Finding Good Solutions to MINLPs. Mathematical Programming Computation, August 2011.
- L. Liberti, G. Nannicini, N. Mladenovic. A good recipe for solving MINLPs. In: V. Maniezzo, T. Stutzle, S.Voss(eds.) Metaheuristics: Hybridizing metaheuristics and Mathematical Programming. Annals of Information Systems, Springer, 2009, vol. 10, pp. 231-245.
- H. Mawengkang and B. A Murtagh, Solving Nonlinear Integer Programs with Large-Scale Optimization Software. Annals of Operations Research, 1986, pp. 5425-437.
- G. Nannicini and P. Belotti, Local Branching for MINPs. Technical Report workingpaper, CMU, 2009.
- G. Nannicini, P. Belotti. Rounding-based heuristics for non-convex MINLPs. In: P. Bonami, L. Liberti, A. Miller, A. Sartenear (eds). Proceedings of the European Workshop on MINLP. CIRM, Marseille, France, 2009.
- I. Quesada and I.E. Grossmann. An LP/NLP Based Branch and Bound Algorithm for Convex MINLP Optimization Problems, Computers Chem. Eng., 1992, 16 (10/11), pp. 937–947.
- H. E. Scarf, Testing for Optimality in the Absence of Convexity. In: W. P. Heller, R. M Starr and D. A. Starett (Eds) Cambridge University Press, 1986, pp. 117-134.
- Tamara G. Kolda, Robert M. Lewis, Virginia Torezon. Optimization by Direct Search: New Perspective on Some Classical and Modern Methods. SIAM Review, 2003, vol. 45 (1) pp. 385-482.
- S. A. Vavasis, Nonlinear Optimization: Complexity Issues. Oxford University Press, Oxford, 1991.
- T. Westerlund and F. Petersson. A Cutting Plane Method for Solving Convex MINLP Problems, Computers Chem. Eng., 1995, vol. 19, pp. 131–136.

Select your language of interest to view the total content in your interested language

- Computation theory
- Conditioning Monitoring
- Controllers
- Global optimization
- Image Recognition
- Information Visualization
- Internet computing
- Machines
- Mathematical optimization
- Mechatronics and Robotics
- Modeling and Simulation
- Network
- Parallel Processing
- Power System
- Signal Processing
- Simulator
- Soft Computing and Computational Intelligent
- Software design
- Statistics
- Technology
- Ubiquitous Computing
- Wireless Sensor

- Total views:
**11972** - [From(publication date):

June-2012 - Dec 15, 2019] - Breakdown by view type
- HTML page views :
**8154** - PDF downloads :
**3818**

**Make the best use of Scientific Research and information from our 700 + peer reviewed, Open Access Journals**

International Conferences 2019-20