Computational Enhancement in the Application of the Branch and Bound Method for Linear Integer Programs and Related Models

In this paper, a reformulation that was proposed for a knapsack problem has been extended to single and bi-objective linear integer programs. A further reformulation by adding an upper bound constraint for a knapsack problem is also proposed and extended to the bi-objective case. These reformulations significantly reduce the number of branch and bound iterations … Read more

A random search method for finding ‘K ≥ 2’ number of ranked optimal solution to an assignment problem

A need for an optimal solution for a given mathematical model is well known and many solution approaches have been developed to identify efficiently an optimal solution in a given situation. For example, one such class of mathematical models with industrial applications have been classified as mathematical programming models (MPM). The main idea behind these … Read more

A parallelizable augmented Lagrangian method applied to large-scale non-convex-constrained optimization problems

We contribute improvements to a Lagrangian dual solution approach applied to large-scale optimization problems whose objective functions are convex, continuously differentiable and possibly nonlinear, while the non-relaxed constraint set is compact but not necessarily convex. Such problems arise, for example, in the split-variable deterministic reformulation of stochastic mixed-integer optimization problems. The dual solution approach needs … Read more

Combining Progressive Hedging with a Frank-Wolfe Method to Compute Lagrangian Dual Bounds in Stochastic Mixed-Integer Programming

We present a new primal-dual algorithm for computing the value of the Lagrangian dual of a stochastic mixed-integer program (SMIP) formed by relaxing its nonanticipativity constraints. The algorithm relies on the well-known progressive hedging method, but unlike previous progressive hedging approaches for SMIP, our algorithm can be shown to converge to the optimal Lagrangian dual … Read more

On the Maximal Extensions of Monotone Operators and Criteria for Maximality

Within a nonzero, real Banach space we study the problem of characterising a maximal extension of a monotone operator in terms of minimality properties of representative functions that are bounded by the Penot and Fitzpatrick functions. We single out a property of this space of representative functions that enable a very compact treatment of maximality … Read more

A Trust Region Method for the Solution of the Surrogate Dual in Integer Programming

We propose an algorithm for solving the surrogate dual of a mixed integer program. The algorithm uses a trust region method based on a piecewise affine model of the dual surrogate value function. A new and much more flexible way of updating bounds on the surrogate dual’s value is proposed, which numerical experiments prove to … Read more

On the Augmented Lagrangian Dual for Integer Programming

We consider the augmented Lagrangian dual for integer programming, and provide a primal characterization of the resulting bound. As a corollary, we obtain proof that the augmented Lagrangian is a strong dual for integer programming. We are able to show that the penalty parameter applied to the augmented Lagrangian term may be placed at a … Read more

A Constructive Proof of the Existence of a Utility in Revealed Preference Theory

Within the context of the standard model of rationality within economic modelling we show the existence of a utility function that rationalises a demand correspondence, hence completely characterizes the associated preference structure, by taking a dense demand sample. This resolves the problem of revealed preferences under some very mild assumptions on the demand correspondence which … Read more

A New Approach to the Feasibility Pump in Mixed Integer Programming

The feasibility pump is a recent, highly successful heuristic for general mixed integer linear programming problems. We show that the feasibility pump heuristic can be interpreted as a discrete version of the proximal point algorithm. In doing so, we extend and generalize some of the fundamental results in this area to provide new supporting theory. … Read more

Boosting the Feasibility Pump

The Feasibility Pump (FP) has proved to be an effective method for finding feasible solutions to mixed integer programming problems. FP iterates between a rounding procedure and a projection procedure, which together provide a sequence of points alternating between LP feasible but fractional solutions, and integer but LP relaxed infeasible solutions. The process attempts to … Read more