Steffen Rebennack, Vitaliy Krasko · INFORMS journal on computing · 2019
Piecewise linear (PWL) functions are used in a variety of applications. Computing such continuous PWL functions, however, is a challenging task. Software packages and the literature on PWL function fitting are dominated by heuristic methods. This is true for both fitting discrete data points and continuous univariate functions. The only exact methods rely on nonconvex model formulations. Exact methods compute continuous PWL function for a fixed number of breakpoints minimizing some distance function between the original function and the PWL function. An optimal PWL function can only be computed if the breakpoints are allowed to be placed freely and are not fixed to a set of candidate breakpoints. In this paper, we propose the first convex model for optimal continuous univariate PWL function fitting. Dependent on the metrics chosen, the resulting formulations are either mixed-integer linear programming or mixed-integer quadratic programming problems. These models yield optimal continuous PWL functions for a set of discrete data. On the basis of these convex formulations, we further develop an exact algorithm to fit continuous univariate functions. Computational results for benchmark instances from the literature demonstrate the superiority of the proposed convex models compared with state-of-the-art nonconvex models.
Cited by 54
Li, Hongpei, Yuan, Hui, Zhang, Han et al. · arXiv (Cornell University) · 2025
Mixed-Integer Linear Programming (MILP) is a foundational tool for complex decision-making problems. However, the NP-hard nature of MILP presents a significant computational challenge, motivating the development of machine learning-based heuristic solutions to accelerate downstream solvers. While recent generative models have shown promise in learning powerful heuristics, they suffer from a critical limitation. That is, they model the distribution of only the integer variables and fail to capture the intricate coupling between integer and continuous variables, creating an information bottleneck and ultimately leading to suboptimal solutions. To this end, we propose Joint Continuous-Integer Flow for Mixed-Integer Linear Programming (FMIP), which is the first generative framework that models the joint distribution of both integer and continuous variables for MILP solutions. Built upon the joint modeling paradigm, a holistic guidance mechanism is designed to steer the generative trajectory, actively refining solutions toward optimality and feasibility during the inference process. Extensive experiments on eight standard MILP benchmarks demonstrate the superior performance of FMIP against existing baselines, reducing the primal gap by 41.34% on average. Moreover, we show that FMIP is fully compatible with arbitrary backbone networks and various downstream solvers, making it well-suited for a broad range of real-world MILP applications.
Cited by 0Open access
Quang Nhat Huynh, Shelvin Chand, Hemant Kumar Singh et al. · IEEE Transactions on Evolutionary Computation · 2018
Genetic programming (GP) is one of the commonly used tools for symbolic regression. In the field of GP, the use of semantics and an external library of subexpressions for designing better search operators has recently gained significant attention. A notable example is semantic backpropagation, which has demonstrated an ability to obtain expressions with extremely small prediction errors. However, these expressions often tend to be long and difficult to interpret, which may restrict their applicability in real-life problems. In this paper, we propose a GP framework that includes two key elements, a new library construction scheme and a novel semantic operator based on mixed-integer linear programming (MILP). The proposed library construction scheme maintains diverse subexpressions and keeps the library size in check by imposing an upper limit. The proposed semantic operator constructs new expressions by effectively combining a given number of subexpressions from the library. These improvements have been integrated in a bi-objective GP framework with random desired operator (RDO), which attempts to simultaneously reduce the complexity and improve the fitness of the evolving expressions. The contributions of individual components are studied in detail using 15 benchmarks. It is observed that the use of the proposed scheme with RDO leads to shorter expressions without sacrificing accuracy of approximation. The addition of MILP further improves the results for certain types of problems.
Cited by 27
Bagus Sartono, Eric D. Schoen, Peter Goos · Figshare · 2015
We present a mixed integer linear programming approach to orthogonally block two-level, multilevel, and mixed-level orthogonal designs. The approach involves an exact optimization technique which guarantees an optimal solution. It can be applied to many problems where combinatorial methods for blocking orthogonal designs cannot be used. By means of 54-run and 64-run examples, we demonstrate that our approach outperforms two benchmark techniques in terms of the number of estimable two-factor interaction contrasts and in terms of the D-efficiency for models with main effects and some two-factor interaction contrasts. We demonstrate the generic nature of our approach by applying it to the most challenging instances in a catalog of all orthogonal designs of strength 3 with up to 81 runs as well as a small catalog of strength-4 designs. The approach can also be applied to strength-2 designs, but, for these cases, alternative methods described in the literature may perform equally well. Supplementary materials for this article are available online.
Cited by 0Open access
Della Croce Di Dojola, Federico · PORTO Publications Open Repository TOrino (Politecnico di Torino) · 2010
Cited by 0
Schoonen, B.T.M. · Theses database, Tilburg University · 2001
Cited by 0
Louis Caccetta, Nur Aidya Hanum Aizam · eSpace (Curtin University) · 2012
The construction of an effective and satisfying weekly timetable has always been a key challenge of every university administrator. Mathematically, the problem is to optimise an objective function that reflects the value of the schedule subject to a set of constraints that relate to various operational requirements and a range of resource constraints (lecturers, rooms, etc). The usual objective is to maximise the total preferences or to minimise the total number of students affected by clashes. The problem can be conveniently expressed as a Mixed Integer Linear Programming (MILP) problem. The computational difficulty is due to the integer restrictions on the variables. Various computational models including both heuristics and exact methods have been proposed in the literature. In this paper, we present MILP models which incorporate all hard constraints and the desirable soft constraints. Hard constraints are the types that are not meant to be violated in any situation such as the conflict, sequence and operational constraints. The soft constraints are the ones which can be treated as non-essential but stimulates circumstances that are optional, namely preferences of students and lecturers to time and rooms. Randomly generated data and available literature data are used to test and evaluate our models. AIMMS 3.11 mathematical software is employed as a tool to solve the models with CPLEX 12.1 as the solver. The computational results are favourable.
Cited by 1
Domenico Salvagnin · Research Padua Archive (University of Padua) · 2009
Many decision problems in industry, logistics, and telecommunications can be viewed as satisfiability or optimization problems. Two paradigms have reached a high degree of sophistication from the point of view of both theory and implementation: Constraint Programming (CP) and Mixed Integer Programming (MIP). The CP and MIP paradigms have strengths and weaknesses that complement each other. On the one hand, CP, through the use of sophisticated propagation techniques, privileges primal inference. On the other hand, MIP, through the techniques of relaxation and strengthening through cutting planes, privileges dual inference. This thesis presents several studies in Mixed Integer Programming, with emphasis on computational aspects and integration with the Constraint Programming paradigm. In particular, CP concepts and techniques, such as nogoods, minimal infeasiblity and constraint propagation, are used to improve different MIP solving components, namely, dominance detection, Benders cuts selection strategy and primal heuristics. This cross-fertilization of techniques and ideas has proven very effective. Finally, an appendix is given covering a MIP application to robust railway timetabling.
Cited by 4Open access
Rui Zhao, Gerwin Schalk, Qiang Ji · 2018
In this paper, we consider the problem of localizing the subsequence in time series which contains the dynamic pattern of interest. This is motivated by brain computer interface application where we need to analyze the dynamic pattern of brain signals in response to external stimulus. We treat the localization as a binary label assignment problem and formalize a mixed integer linear programming (MILP) problem. The optimal solution is obtained by minimizing a cost function associated with label assignment subject to empirical constraints induced by data acquisition process. We first experiment with synthetic data to evaluate the effectiveness of the proposed MILP formulation and achieve 10.8% improvement on F <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -score. We then experiment with electrocorticographic (ECoG) data for a classification task and achieve 8.8% improvement on accuracy using subsequences localized by our method compared to other methods.
Cited by 1
Juan Pablo Vielma, Shabbir Ahmed, George L. Nemhauser · Operations Research Letters · 2012
Cited by 19
Dingbao Xie, Zhaolei Liu · Lecture notes in electrical engineering · 2021
Cited by 1
Journal of Decision Making and Healthcare · 2024
Since Free Disposal Hull (FDH) was proposed, scholars in different fields have quickly recognized that it is an excellent and easily used methodology to evaluate the relative efficiency of entities called decision making units (DMUs).In this work, an inequality evaluation approach, which is equivalent to FDH model is proposed.Moreover, considering the imprecise production data which are collected from observation or investigation, the fuzzy inequality evaluation approach is also proposed.The relative efficiency of DMU depends on the number of solutions of inequalities.Finally, the use of the proposed approach is illustrated by means of an example.
Cited by 0Open access
S. A. Sherif, Bahaa E. A. Saleh, Renato De Leone · IEEE Transactions on Image Processing · 1995
Images that are to be transmitted through a distorting imaging system may be deliberately altered to compensate for that distortion. The authors consider an incoherent diffraction-limited imaging system followed by an ideal high-contrast detector that prints binary images, and seek a binary input image (a mask) that generates a desired prescribed binary output image. They have developed a method for determining the optimal binary mask by formulating the problem as a mixed linear integer program (MLIP) and using the branch and bound method to solve it.
Cited by 52
Bagus Sartono, Schoen, Eric, Goos, Peter · Figshare · 2015
Cited by 0Open access
Arnold Neumaier, Oleg Shcherbina · 2002
Current mixed-integer linear programming solvers are based on linear programming routines that use floating point arithmetic. Occasionally, this leads to wrong solutions, even for problems where all coefficients and all solution components are small integers. It is shown how, using directed rounding and interval arithmetic, cheap pre- and postprocessing of the linear programs arising in a branch-and-cut framework can guarantee that no solution is lost, at least for mixed-integer programs in which all variables can be bounded rigorously by bounds of reasonable size.
Cited by 0
Vignesh Sivaramakrishnan, Omanshu Thapliyal, Abraham P. Vinod et al. · 2019
Mode confusion, in which the human and the automation have a mismatch in intent, is a contributing factor in many aircraft incidents and accidents. Despite extensive work studying and documenting instances of mode confusion, methodological tools to predict and prevent mode confusion are still lacking. We propose a method to identify mismatches between the pilot and automation intents, in which the pilot intent is inferred from the pilot manual, and the automation intent is an abstraction of the underlying hybrid dynamical system representation of the aircraft and flight management system. We employ a mixed-integer linear programming framework to identify all trajectories from a known initial condition that will result in mismatches in discrete event abstractions which encode both pilot and aircraft intents. We then propose heuristics that use traces from failed trajectories to correct the mode confusion through modifications to the automation intent, via parameterization of guards. We demonstrate our method on the canonical kill-the-capture scenario for longitudinal aircraft dynamics.
Cited by 1
Margot, Francois · KiltHub Repository · 2009
In this paper, a methodology for testing the accuracy and strength of cut generators for mixed-integer linear programming is presented. The procedure amounts to random diving towards a feasible solution, recording several kinds of failures. This allows for a ranking of the accuracy of the generators. Then, for generators deemed to have similar accuracy, statistical tests are performed to compare their relative strength. An application on eight Gomory cut generators and six Reduce-and-Split cut generators is given. The problem of constructing benchmark instances for which feasible solutions can be obtained is also addressed.
Cited by 0Open access
Turner, Mark Ruben · DepositOnce · 2024
Mixed-Integer Linear Programming (MILP) is a ubiquitous and practical modelling paradigm that is essential for optimising a broad range of real-world systems. The backbone of all modern MILP solvers is the branch-and-cut algorithm, which is a hybrid of the branch-and-bound and cutting planes algorithms. Cutting planes (cuts) are linear inequalities that tighten the relaxation of a MILP. While a lot of research has gone into deriving valid cuts for MILPs, less emphasis has been put on determining which cuts to select. Cuts in general are generated in rounds, and a subset of the generated cuts must be added to the relaxation. The decision on which subset of cuts to add is called cut selection. This is a crucial task since adding too many cuts makes the relaxation large and slow to optimise over. Conversely, adding too few cuts results in an insufficiently tightened relaxation, and more relaxations need to be enumerated. To further emphasise the difficulty, the effectiveness of an applied cut is both dependent on the other applied cuts, and the state of the MILP solver. In this thesis, we present theoretical results on the importance and difficulty of cut selection, as well as practical results that use cut selection to improve general MILP solver performance. Improving general MILP solver performance is of great importance for practitioners and has many runoff effects. Reducing the solve time of currently solved systems can directly improve efficiency within the application area. In addition, improved performance enables larger systems to be modelled and optimised, and MILP to be used in areas where it was previously impractical due to time restrictions. Each chapter of this thesis corresponds to a publication on cut selection, where the contributions of this thesis can naturally be divided into four components. The first two components are motivated by instance-dependent performance. In practice, for each subroutine, including cut selection, MILP solvers have adjustable parameters with hard-coded default values. It is ultimately unrealistic to expect these default values to perform well for every instance. Rather, it would be ideal if the parameters were dependent on the given instance. To show this motivation is well founded, we first introduce a family of parametric MILP instances and cuts to showcase worst-case performance of cut selection for any fixed parameter value. We then introduce a graph neural network architecture and reinforcement learning framework for learning instance-dependent cut scoring parameters. In the following component, we formalise language for determining if a cut has theoretical usefulness from a polyhedral point of view in relation to other cuts. In addition, to overcome issues of infeasible projections and dual degeneracy, we introduce analytic center based distance measures. We then construct a lightweight multi-output regression model that predicts relative solver performance of an instance for a set of distance measures. The final two components are motivated by general MILP solver improvement via cut selection. Such improvement was shown to be possible, albeit difficult to achieve, by the first half of this thesis. We relate branch-and-bound and cuts through their underlying disjunctions. Using a history of previously computed Gomory mixed-integer cuts, we reduce the solve time of SCIP over the 67% of affected MIPLIB 2017 instances by 4%. In the final component, we introduce new cut scoring measures and filtering methods based on information from other MILP solving processes. The new cut selection techniques reduce the solve time of SCIP over the 97% of affected MIPLIB 2017 instances by 5%.
Cited by 0Open access
Clement, Riley · NOVA (University of Newcastle, Australia) · 2015
Research Doctorate - Doctor of Philosophy (PhD)
Cited by 0Open access
Stojan Kravanja · Civil Engineering ' ... · 2018
The paper discusses the Mixed-Integer Non-linear Programming (MINLP) of problems in civil engineering. The MINLP enables the optimization of continuous parameters simultaneously with discrete alternatives. While continuous parameters are in structural optimization structural costs, masses, loads, stresses, resistances and deflections, as well as the discrete alternatives are in most cases defined as different topologies, standard sizes and materials. The continuous parameters are in the models expressed by continuous variables, whilst the discrete alternatives by discrete (0-1) variables. The MINLP optimization of a structure is usually a comprehensive and highly non-linear calculation process. The MINLP approach requires that a structure is generated as an MINLP superstructure including a number of structure alternatives. One of them is the optimal one. For each optimization problem/structure, an MINLP optimization model of the structure must be developed, where the cost or mass objective function of the structure is subjected to structural analysis and dimensioning equality/inequality constraints. The Modified Outer-Approximation/Equality-Relaxation algorithm and a threephase MINLP strategy are applied. Three numerical examples, i.e. the MINLP optimization of a cantilever beam, composite floor and high-pressure penstock are presented at the end of the paper.
Cited by 0Open access