This talk will describe a primal search algorithm to optimise an integer programme defined over a polyhedron, wherein the search is conducted on the lattice described by the linear constraints of the model. Search directions are derived in the spirit of Graver bases and are extracted dynamically using a feasibility-seeking residual problem. The algorithm also allows for the use of Graver-base specific valid inequalities based on the specific properties of the coefficient matrix of the constraints of the integer programme. Computational results will be presented to show the potential of the algorithm, particularly on 0-1 programming formulations with nonlinear objective functions.

In recent years, significant work has been focused on methods for exploring and sampling from and optimizing over the set of feasible points of an integer program, known as a fiber. These methods focus on producing a basis of moves which enable transitions between feasible points and facilitate Markov Chain Monte Carlo methods over the fiber. In this talk, we will address integer programs with very large bases for which computation using the whole set is intractable and analyze the performance of augmentation methods for optimization when using a small sample of the basis. An intelligent sampling approach could both potentially enable the solution of problems of a much higher dimension and also enable the use of larger bases with more attractive properties for smaller problems (e.g, Graver bases for which a greedy augmentation method produces an optimal solution). In particular, we will study a specific total variation-regularized optimization problem and present theoretical and experimental results for this problem.

The Cubic Knapsack Problem (CKP) is respectively a generalization of Quadratic Knapsack Problem (QKP) and Knapsack Problem (KP). CKP is known as combinatorial optimization problem in which, a cubic function of binary variables is maximizing subject to one dimension knapsack constraint. It has many applications in biology, project selection, capital budgeting problem, etc. The CKP is NP-hard problem in the strong sense, because it's a generalization of QKP that is NP-hard, then there is no polynomial exact algorithm that can solve it. In this work, we introduced a dynamic programming heuristic in the space of lifted variable to solve CKP by finding a near optimal solution. The solution of dynamic programming heuristic is compared with exact solution for and with other heuristic find in the litterature.