{'fraction_non_alphanumeric': 0.038978494623655914, 'fraction_numerical': 0.014626818469323214, 'mean_word_length': 4.626445729537367, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 4, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Learning to Accelerate Approximate Methods for Solving Integer Programming via Early Fixing

Integer programming (IP) is an important and challenging problem. Approximate methods have shown promising performance on both effectiveness and efficiency for solving the IP problem. However, we observed that a large fraction of variables solved by some iterative approximate methods fluctuate around their final converged discrete states in very long iterations. Inspired by this observation, we aim to accelerate these approximate methods by early fixing these fluctuated variables to their converged states while not significantly harming the solution accuracy. To this end, we propose an early fixing framework along with the approximate method. We formulate the whole early fixing process as a Markov decision process, and train it using imitation learning. A policy network will evaluate the posterior probability of each free variable concerning its discrete candidate states in each block of iterations. Specifically, we adopt the powerful multi-headed attention mechanism in the policy network. Extensive experiments on our proposed early fixing framework are conducted to three different IP applications: constrained linear programming, MRF energy minimization and sparse adversarial attack. The former one is linear IP problem, while the latter two are quadratic IP problems. We extend the problem scale from regular size to significantly large size. The extensive experiments reveal the competitiveness of our early fixing framework: the runtime speeds up significantly, while the solution quality does not degrade much, even in some cases it is available to obtain better solutions. Our proposed early fixing framework can be regarded as an acceleration extension of ADMM methods for solving integer programming. The source codes are available at \url{https://github.com/SCLBD/Accelerated-Lpbox-ADMM}.


INTRODUCTION
I NTEGER programming (IP) is an important and challenging problem in many fields, such as machine learning [1] and computer vision [2]. IP can be a versatile modeling tool for discrete or combinatorial optimization problems with a wide variety of applications, and thus has attracted considerable interests from the theory and algorithm design communities over the years [3]. There are rich literature and a wide range of developed methods and theories for solving IP. Generally, we could divide them into two categories: exact methods and approximate methods. Some exact methods are widely utilized, such as branch-and-bound [4] , cutting plane [5] and branch-and-cut [6] methods. The branch-and-bound method [4] is an approach that partitions the feasible solution space into smaller subsets of solutions. The cutting-plane method [5] is any of a variety of optimization methods that iteratively refine a feasible set or objective function by means of linear inequalities, termed cuts. The branch-and-cut [6] method combines branch-and-bound and the cutting plane method. These exact methods are able to get the optimal solutions, however, they are usually suffering from timeconsuming issues due to the repeated solving of relaxed linear problems. Thereafter, in the recent years, more and more research focuses on the approximate methods, where a feasible solution is obtained within the limited time. Linear relaxation [7] relaxes the binary constraints x ∈ {0, 1} to the box constraints x ∈ [0, 1]. Spectral relaxation [8] relaxes the binary constraint to the 2 -ball, leading to a non-convex constraint. As regard to the SDP relaxation [9], the binary constraints are substituted with a positive semi-definite matrix constraint, i.e., X 0.
Besides the above mentioned relaxation-based approximate methods for integer programming, recently there has been increasing attention to another type of approximate methods, which is iterative and based on the alternating direction method of multipliers (ADMM) [10]. ADMM is a powerful algorithm for distributed convex optimization, with an attempt to blend the benefits of dual decomposition [11] and augmented Lagrangian methods [12]. ADMM coordinates the solutions of small local subproblems to find a solution of the large global problem. Many variants of ADMM have been proposed with different purposes of better acceleration, convergence, or stability, and have been applied to solving different types of optimization tasks. Bethe ADMM [13] was proposed for tree decomposition based parallel MAP inference, which used an inexact ADMM augmented with a Bethe-divergence based proximal function. Bregman ADMM [14] was then proposed, which provided a unified framework for ADMM. Bregman ADMM then has a number of variants such as generalized ADMM and inexact ADMM. Linearized ADMM [15] [16] was also proposed for convex optimization. One state-of-the-art ADMM method for solving IP is p -Box ADMM [17], where the binary constraints are equivalently replaced by the intersection of a box constraint and a p -norm sphere constraint.
Towards those ADMM based approximate methods, we observed that regarding the approximate methods a large fraction of variables fluctuated around theirs final converged states in very long iterations. In Fig. 1, we solve a constrained linear programming instance with 500 variables by p -box ADMM, which converges after 7827 iterations. The left figure illustrates the objective changes with respect to the iterations. And we can see that the convergence reaches after a long fluctuation. In the right figure, We introduce "Flip number"  [19]. However, early stopping has two shortcomings: 1). There is trade-off between the objective efficiency and the runtime effectiveness, when stopping much earlier the objective accuracy may decrease more. 2). It always use the whole set of variables to consider whether and when to stop.
Inspired by this observation, we were thinking: why not take every single variable independently and then asynchronously fix them instead of early stopping all of the variables at one iteration? To the end, we propose an early fixing framework, which aims to accelerate the approximate method by early fixing these fluctuated variables to their converged states while not significantly harming the converged performance. Fig. 2 shows the comparison between early stopping and early fixing. And there are mainly three differences: Firstly, early stopping does only consider the depth of optimization, i.e., the number of iterations, while early fixing also thinks over the width of optimization, i.e., the dimension of variables. Secondly, early stopping regards the set of variables as a whole, while early fixing treats every single variable independently. And thirdly, decisions on whether to early stop are made in every single iteration, while those for early fixing are once every block of iterations, i.e., β iterations.
Under our proposed early fixing framework, in each block of iterations, given the iterative values of the variables within the past β iterations, a policy network will evaluate the posterior probability of each variable concerning all discrete candidate states. If the posterior probability with respect to one state exceeds the fixing threshold, then the action of fixing this variable to that discrete state will be conducted, and this variable will not be updated in later iterations; otherwise, no fixing action will be conducted and this variable will be further updated. Specifically, for each variable, the continuously iterative values within the past β iterations are sequential according to the time series. Recently, the Transformer structure [20] has exhibited powerful performance in the sequential networks though the multi-headed attention (MHA) mechanism. Herein, we incorporate the attention layers in our policy network. When solving a problem with early fixing framework, one block of iterations only decides a proportion of variables to conduct early fixing, thus the process is episodic until termination. We can regard the solving process as a Markov decision process [21] and train it using imitation learning [22]. Since the input of policy network only requires the iterative values of variables, without any other constraint information, thus our early fixing framework can be versatile enough, available to all the IP problems of any orders or types, no matter linear or quadratic, constrained or unconstrained.
In this paper, in order to accelerate the ADMM based approximate methods for solving the IP problems, especially improving the scalability of the IP problems, we propose the early fixing framework combined with learning techniques. The main contributions of this paper are four-fold: (i) To the best of our knowledge, we are the first to propose an early fixing framework to accelerate the approximate methods, where the variables are treated independently with one another and we can asynchronously fix them according to their continuously iterative values within the past series of iterations. Once fixed, the variables will not be further updated.
And free variables will continue iterating and updating. (ii) We formulate the whole early fixing process when accelerating solving an IP problem as a Markov decision process, and train it using behaviour cloning as a method of imitation learning. We also incorporate the weighted binary cross-entropy (WBCE) loss during the training. (iii) We adopt the learning techniques with the attention layers in our policy network, to decide whether to fix the variable or not. (iv) We apply our proposed early fixing framework to three different IP applications: constrained linear programming, MRF energy minimization and sparse adversarial attack. The former one is linear IP problem, while the latter two are quadratic IP problems. We extend the problem scale from regular size to significantly large size. The extensive experiments reveal the competitiveness of our early fixing framework: the runtime speeds up significantly, while the solution quality does not degrade much, even in some cases it is available to obtain better solutions.

Set of Variables
The rest of this paper is organized as follows. Section 2 briefly reviews the related work. Some background information is given in Section 3. The details of our early fixing framework are described in Section 4. Section 5-7 show the extensive applications of our proposed framework in the areas of constrained linear programming, MRF energy minimization and sparse adversarial attack, respectively. We present the conclusion in Section 8. This is the testing a a δ ∈ ≥. R

RELATED WORK
Integer programming There are rich literature and a wide range of developed methods and theories for solving IP. Generally, we could divide them into two categories: exact methods and approximate methods. Some exact methods are widely utilized, such as branch-and-bound [4] , cutting plane [5] and branch-and-cut [6] methods. The branch-andbound method [4] is an approach that partitions the feasible solution space into smaller subsets of solutions. The cuttingplane method [5] is any of a variety of optimization methods that iteratively refine a feasible set or objective function by means of linear inequalities, termed cuts. The branchand-cut [6] method combines branch-and-bound and the cutting plane method. These exact methods are able to get the optimal solutions, however, they are much too slow in the runtime due to the repeated solving of relaxed linear problems. In order to obtain feasible solutions within the given time, some approximate methods are proposed. Linear relaxation [7] relaxes the binary constraints x ∈ {0, 1} to the box constraints x ∈ [0, 1]. Spectral relaxation [8] relaxes the binary constraint to the 2 -ball, leading to a non-convex constraint. As regard to the SDP relaxation [9], the binary constraints are substituted with a positive semi-definite matrix constraint, i.e., x 0.
Integer programming by ADMM Besides the above mentioned relaxation-based approximate methods for integer programming, recently there has been increasing attention to another type of approximate methods, which is iterative and based on the alternating direction method of multipliers (ADMM) [10]. ADMM is a powerful algorithm for distributed convex optimization. With an attempt to blend the benefits of dual decomposition [11] and augmented Lagrangian methods [12], ADMM coordinates the solutions of small local subproblems to find a solution of the large global problem. Many variants of ADMM have been proposed with different purposes of better acceleration, convergence, or stability, and have been applied to solving different types of optimization tasks. Bethe ADMM [13] was proposed for tree decomposition based parallel MAP inference, which used an inexact ADMM augmented with a Bethe-divergence based proximal function. Bregman ADMM [14] was then proposed, which provided a unified framework for ADMM and its variants, including generalized ADMM, inexact ADMM and Bethe ADMM. Linearized ADMM [15] [16] was also proposed for convex optimization. One state-ofthe-art ADMM method for solving IP is p -box ADMM [17], where the binary constraints are equivalently replaced by the intersection of a box constraint S b and a p -norm sphere constraint S p . The equivalent replacement can be formulated as: x − 1 2 1 p p = n 2 p }, then additional variables are introduced to separate the constraints, so as to coordinate with ADMM method. This method could give a quasi-optimal solution at the globally converged point. p -box ADMM has wide application in MAP inference [23], sparse adversarial attack [24], model compression [25], feature selection [26] and etc. Though p -Box ADMM builds the bridge between IP and continuous optimization algorithms and achieves great performances in solving IP tasks, it still remains the issues of scalability.
Integer programming meets learning The application of machine learning (ML) to discrete optimization has been a popular topic with various approaches in the literature [27]. Learning to branch is an interesting topic attracting a great deal of attention. Khalil et al. [28] took the first step towards statistical learning of branching rules in BB. Alvarez et al. [29] and Gasse et al. [30] learn a branching rule offline on a collection of similar instances, and the branching policy is learned by the imitation of the strong branching expert. Graph Neural Network (GNN) approach for learning to branch has successfully reduced the runtime [30]. Gupta et al. [31] consider the availability of expensive GPU resources for training and inference, thus devise an alternate computationally inexpensive CPU-based model that retains the predictive power of the GNN architecture. Tang et al. [32] utilize reinforcement learning for learning to cut. Recently there is one set of approaches focusing on directly learning the mapping from an IP to its approximate optimal solution, instead of solving the IP by any exact or approximate solvers. Vinyals et al. [33] introduce the pointer network as a model that uses attention to output a permutation of the input, and train this model offline to solve the TSP problem. Bello et al. [34] introduce an Actor-Critic algorithm to train the pointer network without supervised solutions. Kool et al. [35] propose a model based on attention layers [20] to solve the routing problems. Andrychowicz et al. [36] and Li et al. [37] propose learning to optimize or learning to learn, casting an optimization problem as a learning problem. Nowak et al. [38] train a Graph Neural Network in a supervised manner to directly output a tour as an adjacency matrix, which is converted into a feasible solution by a beam search.
Most of the above mentioned papers use the networks to entirely substitute with the optimizer, different from that, in this paper we simply utilize the network to accelerate the optimization, just like an attachment module.
Imitation learning Imitation learning (IL) techniques aim to mimic the hebaviour from an expert or teacher in a given task [39]. IL and reinforcement learning (RL) both work for the Markov decision processes (MDP). RL tends to have the agent learn from scratch through its exploration with a specified reward function, however, the agent of IL does not receive task reward but learn by observing and mimicing [40]. Similar to traditional supervised learning (SL) where the samples represent pairs of features and ground-truth labels, IL has the samples demonstrating pairs of states and actions. One fundamental difference between SL and IL is that: SL follows the assumption that the training and test data are independent and identically distributed (IID), while those of IL are Non-IID where the current state is only correlated to the previous state. Broadly speaking, research in the IL can be split into two main categories: behavioral cloning (BC) [22], and inverse reinforcement learning (IRL) [41]. In this paper, we choose BC for the training.
Early exiting and early stopping The term "early exiting" originally comes from computer vision and image recognition, which is mainly aimed at improving the computation efficiency based on specific architectures during the inference phase [18] [19]. As networks continue to get deeper and larger, these costs become more prohibitive for real-time applications. To address the issue, the proposed architecture exits the network early via additional branch classifiers with high confidence [42]. Early stopping is a form of regularization used to avoid overfitting when training a learner with an iterative method, such as gradient descent [43], [44]. When a certain criterion is satisfied, early stopping will be conducted before the ultimate convergence. Kaya et al. [45] proposes to avoiding "over-thinking" by early stopping, where the deep neural networks can reach correct predictions before the final layers to save the running time. In optimal control literature, optimal stopping [46] is a problem of choosing a time to take a given action based on sequentially observed random variables in order to maximize an expected payoff. Optimal stopping can be seen as a special case of early stopping. Becker et al. [47] and Chen et al. [48] use deep reinforcement learning to learn the optimal stopping policy. Besides, Chen et al. [48] provide a variational Bayes perspective to combine learning to predict with learning to stop. In this paper, we propose a novel early fixing framework for accelerating solving the generic IP problems. Whether early exiting or early stopping, the models focus on the depth of iterations, while our proposed early fixing also considers the width of variable dimensions. Fix-and-optimize Fix-and-optimize [49] is a metaheuristic, firstly proposed by Gintner et. al. for solving mixed integer linear programming (MIP), which iteratively decomposes a problem into smaller subproblems. In each iteration, a decomposition process is applied aiming at fixing most of the decision variables at their value in the current solution.
Since the resulting subproblem is composed only by a small group of free variables to be optimized, each subproblem can be solved fairly quickly by a MIP solver, when compared with the full model. The solution obtained in each iteration becomes the current solution when it improves the objective value. In further iterations, a different group of variables is selected to be optimized. This process is repeated until a termination condition is satisfied. The fix-and-optimize algorithm has wide applications in lot sizing problem [50], timetabling problem [51], and etc. Different from the fix-andoptimize algorithm where the fixed variables in previous iteration will be released in the next iteration, our early fixing framework requires that the fixed variables will stay fixed and not appear in the following iterations. Variable fixing The strategy of fixing variables [52] within optimization algorithms often proves useful for enhancing the performance of methods for solving constraint satisfaction and optimization problems. Such a strategy has come to be one of the basic strategies associated with Tabu search [53]. Two of the most important features in Tabu search are how to score the variables (variable scoring) and which variables should be fixed (variable fixing). Similar to fix-and-optimize algorithm, the fixed variables in Tabu search could possibly be freed, while those in our early fixing framework will keep fixed and not released in the next iterations.

Problem definition
Throughout this paper, we focus on the problem of generic IP problems, which can be generally formulated as a binary mathematical optimization problem as follows: arg max where C ∈ R m is the set of constraints, and x ∈ R n is the set of binary variables. n, m denotes the number of variables and constraints, respectively. In this paper, we mainly focus on the linear and quadratic IP problems.

Approximate methods
The approximate methods for solving IP problems are based on a bunch of iterations, which is a mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions until the convergence. In recent year, there have been a great deal of works utilizing ADMM to solve the IP problems [14], [15], [16], [17], [23], [26]. Therein, in this paper we propose the early fixing framework, aiming to accelerate these ADMM-based approximate methods.

EARLY FIXING FRAMEWORK
In this section, we give an overview of how our proposed early fixing framework is utilized to accelerate the iterative approximate methods for solving generic IP problems. We firstly formulate the early fixing process as a Markov decision process (MDP), as described in subsection 4.1. We present the overview of the policy network in subsection 4.2. We then present how to train the policy network with the weighted binary cross-entropy loss in a imitation learning method in subsection 4.3. Last but not least, we exhibit how to do the inference with our early fixing framework in subsection 4.4, some mathematical propositions and proofs are given as regard to the problem reformulations.

Markov decision process formulations
The sequential decisions made in each early-fixing process actually construct a Markov decision process [21], as shown in Fig. 3. Considering the approximate method M to be accelerated as the environment, we define the states, actions, and policy for early fixing as following: • States: state s t (t ∈ {0, ..., T'}) denotes the state at the iteration t, which is a state set of all variables. The state of each variable s t,i could be anyone out of the five possible states: being fixed/converged to 1, being fixed/converged to 0, or staying free. We denote  represents that all the variables are fixed/converged, no matter to 0 or 1.
• Actions: the action a t (t ∈ {1, ..., T'}) denotes the transitions from one state to the next state. Since our early fixing process is carried out once every β iterations, then the action is also conducted once every β iterations. The terminate iteration could trigger the actions because the variables converge. a t is also a set of actions of each variable: a t = {a t,i } n−1 i=0 .
• Policy: the policy π(a t |s t ), is given by the policy network as described in subsection 4.2, which inputs the past β iteration values of all the currently free variables, and outputs the probabilities of these free variables whether to fix them or not. We use p to denote the output: p = π(a t |s t ) where p i ∈ [0, 1], i ∈ {1, ..., u}, u is the number of free variables. We set a fixing threshold δ ∈ [0.5, 1]. If p i > δ, early fix this variable to 1; If p i < (1 − δ), early fix this variable to 0; Otherwise, do not conduct early fixing and this variable stays free.
According to the policy π(a t |s t ), we may update the variable states, converting some variables from free to fixed. The iteration will terminate when the stopping criterion reaches convergence, or all the variables have been fixed. As a Markov decision process, this early fixing process is episodic, where each episode amounts to solving the IP problem. An ideal approach to find an early-fixing policy is reinforcement learning, here we adopt an imitation learning scheme to train the network. Instead of training the network from scratch, we learn the features of early iterations and directly map to the converged solutions in order to achieve the purpose of acceleration.

Policy network with attention
The policy network provides with the probability for determining whether to fix the input variable or not at current state. The input of the policy network is the past β iterative values of the given variable, and the output is a probability p ∈ [0, 1]. Taking one variable y as an example, we firstly collect the past β continuously iterative values of the variable, which are sequential according to the time series. At this point, the dimension is β × 1. Inspired by the sequential model [54], we use the sliding window to convert the y ∈ R β×1 to z ∈ R α×d h , where z is the iteration embedding of y, α denotes the node number, and d h is the node dimension.
Positional encoding There is no recurrence and no convolution in the attention models, so we need positional encoding. Before feeding z into the attention layers, we inject some information about the relative position of the tokens in the sequence of z, so as to make the most use of the order of the sequence. We follow the setup in Vaswani et al. [20] and add the positional encodings to the iteration embeddings. Let k be the node number, d h be the embedding dimension. Then the positional encodings have the same dimensions d h as the embeddings. We use sine and cosine functions of different frequencies: where k is the position, k∈{1, ..., α} and j is the dimension, 2j ≤ d h . The wavelengths form a geometric progression from 2π to 10000×2π. After adding the positional encoding, the iteration embedding turns from z ∈ R α×d h toẑ ∈ R α×2d h . Attention layers Then we apply the encoder part of Transformer-alike attention architecture [35] to our network to extract better iteration embeddings. First of all, to make it consistent with the dimensions, through a learned linear projection, one node inputẑ k is projected to one node embedding h k , whereẑ k ∈ R 2d h and h k ∈ R dn , and the dimension d n =128. Then all the node embeddings go through L attention layers. Each layer consists of two sublayers: a multi-head attention (MHA) layer that executes message passing between the nodes, and a node-wise fully connected feed-forward (FF) layer. Each sublayer adds a skip-connection [55] and a batch normalization (BN) [56]: Any two layers do not share their parameters. Layer index ∈ {1, ..L}, node index k ∈ {1, ..., α}. The MHA sublayer uses H = 8 heads, each with dimension dn H = 16. Moreover, the fully connected FF sublayer, which is applied to each node embedding separately and identically, consists of two linear transformations with a ReLU activation function in between: it first maps the node embedding from dimension d n to hidden dimension d n = 512, then transforms from d n back to d n . After L attentions layers, we get α node embeddings, each with dimension d n . At this point, we do the concatenation and get embedded variable z with dimension (α·d n ) × 1. MLP layers After the attention layers, the variable y obtains a new embedding z ∈ R (α·dn)×1 , which will be fed into another multi-layer perceptron (MLP). At this stage, we utilize three fully connected FF sublayers along with decreasing dimensions (256 − 128 − 16) with the ReLU activation functions between the hidden layers. Finally, in the last layer through a sigmoid function, we obtain a probability p y ∈ [0, 1], determining whether to fix the input variable y or not. If the probability is greater than the fixing threshold δ, then the action of fixing this variable to 1 will be conducted. we can interpret this fixing threshold as a symmetric fixing confidence, i.e., if the probability is less than 1 − δ, then the action of fixing this variable to 0 will be conducted. Otherwise, no fixing action will be conducted and this variable will be further updated. The early fixing process is given in the Algorithm 1.

Training: imitation learning
We train the policy network π(θ) as shown in Fig. 5. Specifically, our policy network is trained by behavioral cloning [22] as a method of expert-driven imitation learning, and here we use the approximate method to be accelerated M itself as the expert rule. Subsection 4.1 has explained the meaning for states and actions. Then mathematically, for those free variables, we assign s as the past β iterative values, and assign a * as the ultimately converged discrete solutions of the approximate method M, i.e., the expert solutions. We first run the expert on a collection of N training instances, and pick the dataset of expert state-action pairs D={(s e,r,i , a * e,r,i )| n−1 i=0 | γ−1 r=0 | N −1 e=0 }. And the policy is learned by minimizing the weighted binary cross-entropy (WBCE) loss: q e,r,i = a * log π θ (a|s) + (1−a * ) log(1−π θ (a|s)), (5) where for a * , a, s, we hide the subscripts e,r,i for readability. w e,r,i is the weight, w e,r,i = 1 r+1 . Mathematically, s e,r,i = x (r,e) (r−1)β:rβ . a * e,r,i = x (r,e) T −1 . We call one problem shown as in Formulation (1), as one instance. N is the number of training instances.

Inference with early fixing
The general inference stage of early fixing framework is given in the Algorithm 1, and we also present the process as a MDP in Fig. 3. Our early fixing framework takes each variable independently, and decisions on whether to early fix are once every block of iterations. In each block of iterations, given the iterative values of the variables within the past β iterations, the policy network will evaluate the posterior probability of each variable concerning all discrete candidate states (0 or 1). If the posterior probability with respect to one state exceeds a threshold, namely the fixing threshold δ, then the action of fixing this variable to that discrete state will be conducted, and this variable will not be updated in later iterations; otherwise, no fixing action will be conducted and this variable will be further updated.
When a certain number of variables are fixed in previous iterations, then how to update the problem into a smallersized one will be discussed in this subsection. Our early fixing framework is available for both linear programming and quadratic programming, no matter constrained or unconstrained. We will give the mathematical assumptions and propositions based on a constrained quadratic programming problem: arg max Notations. We denote the matrices and vectors in formulation (6) as: where vectors x 1 refers to the set of free variables and x 2 refers to the set of fixed variables, and the same around for other vectors and matrices. Let u, v be the number of free and fixed variables, then b 1 , denotes any relational symbol such as <, >, =, ≥ or ≤. Proposition 1. Problem reformulation: when doing the early fixing once every β iterations, let r be the rounds for conducting early fixing, then we can propose that: if t%β == 0 then 4: x t−β:t ← M(I) 5: s t ← x t−β:t

6:
p ← π θ (a t |s t ) 7: for i = 1 to u do 8: if p i > δ then 9: Early fix variable x i to 1, v ← v+1 10: end if 11: if p i < 1−δ then 12: Early fix variable x i to 0, v ← v+1 13: end if 14: end for 15: Update the instance I as Subsection 4.4. 16: (i) For the objective function: thus: 1 . Since previously fixed variables can be seen as the constants in the following iterations, (ii) For the constraints: thus: Proof ends. Remark 1. As regard to the updating for b, if A is a symmetric matrix, then A 2 = A 3 . At that point, the updating can be simplified as:

Accelerated method and datasets
In this section, we will accelerate the approximate method: p -box ADMM [17] for solving constrained linear integer programming. For the datasets, we choose the combinatorial auction problems [30] with the following formulation: arg max where C ∈ R m×n , m, n refer to the number of constraints and variables. We follow the experimental setup of Gasse et al. [30], and generate two sets of instances in difference sizes.
We generate the instances, namely, b,C,d, according to the generator G. The instance size is determined by two key parameters, bid and item. The bid number is equivalent to variable number n, while the item number is not equivalent but directly proportional to the constraint number m. ξ is a constant. In order to ensure the feasibility and optimality of the instance, the constraint number m could be different for different instances, given the same item number. We generate two sets of instances. For datasets I, there are regular-sized instances: (bid=500, item=100), (bid=1000, item=200), (bid=1500, item=300), (bid=4000, item=800). For datasets II, there are extra large scale instances: (bid=1e4, item=100), (bid=5e4, item=500), (bid=1e5, item=1000), (bid=2e5, item=2000). Training details We train our model only on the smallest sized instances with n=500, and generalize to all other largersized instances. We train on N = 100 instances, and do the inference on N = 20 instances for all the datasets. γ, β, δ, L are set to 10, 100, 0.9, 2, respectively. We train for 10 epochs. The learning rate is set to 1e−4. For our learning-based early fixing methods, training without attention for one epoch costs 77s, while training with attention costs 89s. We implement the functions of the accelerated methods in C++ and call the functions in Python via Cython interfaces. All the learning modules are implemented in Python.

Evaluations
We evaluate all the different sizes, each with 20 instances. We set the time limit to 1 hour. For all datasets, we evaluate the objective, the objective gap and runtime, and we record the mean value of all instances. The objective gap is used to exhibit the gap between the p -box ADMM with learning-based early fixing (LEF) and the p -box ADMM without early fixing, given as: obj1−obj2 obj1 , where obj 1 , obj 2 refer to the objective obtained by p -box ADMM, p -box ADMM + LEF, respectively. A negative objective gap means achieving a better objective with early fixing. Specifically, for datasets II, we also evaluate the Speedup, the number of solution difference (#Sol. Diff.) and the accuracy. The speedup is the time speedup, simply dividing the runtime of p -box ADMM by that of p -box ADMM + LEF. #Sol. Diff is the number of solution difference where the variable solution by p -box ADMM is different from that by p -box ADMM + LEF, the maximum number should be the total variable number n. The accuracy is to evaluate the correct solution accuracy, given as: n−n d n × 100%, n d refers to (#Sol. Diff.). In the hyperparameter study, we also evaluate the number of infeasible constraints.
Baselines For datasets I, we compare against three exact methods based on the branch-and-bound algorithm. Then for Datasets II, since the size is too large for them to obtain a solution, we only compare with the approximate methods. Reliability pseudocost branching (RPB) [57] is a variant of hybrid branching which is used by default in SCIP, and we choose SCIP 6.0.1 [58] as the backend solver. Graph convolutional neural networks (GCNN) [30] are applied to learning branch-and-bound variable selection policies. Feature-wise Linear Modulation (FiLM) [31] [59] layers are used to construct the neural network for learning to branch which is purely CPU-based, but shows competitive performances against GPU-based neural networks.
zoom in 100× zoom in 10× Fig. 6. Convergence on different methods for constrained linear programming: how the objective changes with respect to the iterations during the inference stages for four different sized instances. LEF method leads to much faster convergence, and LEF with attention layers achieves better objective.

Experimental results
Comparative study As shown in Table 2 and Table 3, we firstly compare against three exact methods: RPB, FiLM and GCNN. GCNN generally outperforms RPB and FiLM with higher efficiency in runtime. The three exact methods have one obvious shortcoming in common: time-consuming, especially when the problem size increases, which is unacceptable in real life and large scale applications. Then, we compare our proposed LEF with the base method p -box ADMM. The results turn out that the LEF outperforms the base method regarding objective gaps, which reveals the effectiveness of our early fixing framework. In Fig. 6, we record how the objective changes with respect to the iterations during the inference stages for different sized instances. From the figure, we can see that our LEF method leads to much faster convergence. When zooming in 10× in the left two figure, we obtain a general view about the LEF fluctuations. When zooming in 100× in the right two figure, we can even clearly see that our LEF with attention layers achieves better objective. Ablation study We also compare our LEF with or without attention layers. From the experiments, we can see that the extra attention layers will costs more runtime, while obviously achieving a better objective. The negative objective gaps refer to a better objective. Interestingly, for all the largesized Datasets II, we could even achieve a better objective than the expert method, p -box ADMM itself. And with the problem size n increases, the runtime speedup is also increasing. And with our attention layers, the accuracy of datasets II can be greater than 99.8%, which is impressive. These results exhibit the efficiency of attention layers within our early fixing framework. We also evaluate the efficiency of weighted loss in training, as shown in Fig. 7(b). We set the fixing threshold to 0.9, where all the constraints are feasible. From the figures, we can tell that the weighted loss generally achieves a smaller objective gap and a larger runtime speedup, compared to the no weighted loss.
Hyperparameter study We analyze one of the most important hyperparameters in our early fixing framework: the fixing threshold θ, as shown in Fig. 7(a). We evaluate how the number of infeasible constraints go with the fixing threshold, for different problem sizes in dataset II. We set fixing threshold from 0.5 to 0.9. When θ is 0.5, all the variables are fixed after the first block of iterations. When θ is 1, no variable is early fixed at all. From the results, only when θ is greater than 0.9, the number of infeasible constraints is 0, which means that the solution with early fixing is feasible.

Formulations
We consider the pairwise Markov Random Field (MRF) energy minimization problem based on a graph, which can be generally formulated as [63]: arg min where x is a concatenation of all indicator vectors for the states κ ∈ {1, ..., K} and all n nodes. If x i κ = 1, then node i is on the state κ; otherwise, x i κ = 0. Each node can only take on one state, therefore we ensure that K κ=1 x i κ = 1 for ∀i, i ∈ {1, ..., n}. Thus we have the constraint set as in Formulation 16. As for the objective function, A is the un-normalized Laplacian of the graph, A = D − W, W is the matrix of node-to-node similarities. When K = 2, the problem turns to a submodular minimization problem and it can be globally optimized using the min-cut algorithm [60] in polynomial time, however, it cannot be guaranteed when K > 2.

Experiments for Image segmentation
Accelerated method and datasets p -Box ADMM [17] has been proved to be efficient in image segmentation when K = 2. Thus in our experiment, we choose p -Box ADMM to be accelerated. We also regard the min-cut [60] as the groundtruth algorithm (K=2) for comparisons. The PASCAL Visual Object Classes Challenge 2012 (VOC2012) dataset [64] has been widely used in computer vision tasks, such as object classification, object detection and object segmentation. We thus choose VOC2012 for our experiments, where 2913 images are available for segmentation. We then randomly select 100, 20, 20 images for the training, validation and testing, respectively. We resize the testing images to different sizes and do the testing, including n = 1e4, 5e4, 1e5, 5e5, 1e6, 5e6, 1e7 and 5e7. Training details We train our model only on the smallest sized images with n = 1e4, and generalize to all other larger-sized instances. γ, β, δ, L are set to 5, 10, 0.9, 2, respectively. The learning rate is set to 1e−4. We train for 20 epochs. For our learning-based early fixing methods, training without attention for one epoch costs 122s, while training with attention costs 129s. We implement the functions of the accelerated methods in C++ and call the functions in Python via Cython interfaces. All the learning modules are implemented in Python. Baselines We compare our method against two generic IP solvers, namely linear relaxation [62] and spectral relaxation [61], and a state-of-the-art and widely used min-cut algorithm [60]. The linear relaxation is implemented using the built-in function quadprog in MATLAB. The closed-form solution based on eigen-decomposition is implemented for spectral relaxation. We also compare against the p -box ADMM in both MATLAB and C++. We then apply our learning-based early fixing framework to p -box ADMM, with or without attention layers. We implement the functions of the accelerated methods in C++ and call the functions in Python via Cython interfaces. Evaluations We evaluate all the different sizes, each with 20 instances. We evaluate the energy and the runtime for MATLAB implementations, and for our early fixing we also evaluate the energy gap towards the accelerated method itself. We report the mean values for all the 20 instances of different sizes. The time limit is set to 1 hour.

Comparison study
The experimental results are shown in Table 4. We compare all methods in terms of their final energy value and runtime in the case of binary submodular MRF (K=2). From the results, we can see that min-cut achieves the lowest energy, regarded as the ground-truth methods for the K=2 image segmentation task. Among all the methods, spectral relaxation achieves the worst performance, though it is fast in computation. Linear relaxation runs fast in small sized instances, while running slow for large scale instances. Linear relaxation obtains smaller energy than spectral relaxation, while it is much worse than p -box ADMM. The C++ implementation of p -box ADMM runs much faster than MATLAB version with significant speedup. Compared to the accelerated p -box ADMM, our early fixing framework generally achieves from 3× to 5× speedup in runtime. Especially for the smallest sized instances with n = 1e4, the runtime speedup is even greater than 10×. In Fig. 9, we record how the energy changes with respect to the iterations during the inference stages for one image in different sizes. From the figure, we can see that our LEF method leads to much faster convergence, and LEF with attention layers achieves lower energy. Ablation study We also show the ablation study of our learning-based early fixing. We compare the results with or without attention layers. Equipping with the attention layers will cost a little bit more runtime, however, the energy will decrease a bit more. For LEF without attention layers, the average energy gap of all different sizes is 5.7%, while the average energy gap with attention layers is only 2.8%. The gap is overall decreased by 2.9%. Performance exhibition We exhibit some segmented images of different shapes by the optimal min-cut algorithm, p -box ADMM as well as our learning-based early fixing with or without attention layers. From Figure 8, we can see that p -box ADMM generally achieves a great segmentation performance. And with our early fixing framework, the segmentation efficiency is also excellent.

Background
We consider the sparse adversarial attack [24], which generates adversarial perturbations onto partial positions of the clean image, where the perturbed image is incorrectly predicted by the deep model. There are two challenges lying in the sparse adversarial attack. One is where to perturb and the other is how to determine the perturbation magnitude. Some works manually or heuristically determined the perturbed positions, and optimized the magnitude using an appropriate algorithm designed for the dense adversarial attack. However, Fan et. al. [24] proposed to factorize the perturbation at each pixel to the product of two variables, including the perturbation magnitude and one binary selection factor (i.e., 0 or 1). One pixel is perturbed if its selection factor is 1, otherwise not perturbed. The perturbation can be factorized as: where ζ ∈ R n denotes the vector of perturbation magnitudes, and η ∈ {0, 1} n denotes the vector of perturbed positions.
represents the element-wise product. Then the sparse attack problem can be formulated as a mixed integer programming (MIP) by jointly optimizing the continuous perturbation magnitudes ζ and the binary selection factors η of all pixels. Inspired by p -box ADMM [17], they proposed to reformulate the MIP problem to an equivalent continuous optimization problem. They update the ζ by gradient descent, and update the η by ADMM. At this point, we are going to accelerate the η updating parts with our early fixing framework.

Adversarial attack experiments
Datasets and models We follow the setup in SAPF (Sparse adversarial Attack via Perturbation Factorization) [24], and use the CIFAR-10 [65] and ImageNet [66] for the experiments. There are 50k training images and 10k validation images covering 10 classes for CIFAR-10. We randomly select 1000 images from the validation set for our experiments. Each image has 9 target classes except its ground-truth class. Thus there are totally 9000 adversarial examples for the adversarial attack method. ImageNet contains 1000 classes, with 1.28 million images for training and 50k images for validation. We randomly choose 100 images covering 100 different classes from the validation set. To reduce the time complexity, we randomly select 9 target classes for each image in ImageNet, resulting in 900 adversarial examples. As regard to the classification model, on CIFAR-10, we follow  the setting of C&W [67] and train a network that consists of four convolution layers, three fully-connected layers, and two max-pooling layers. The input size of the network is 32 x 32 x 3. On ImageNet, we use a pre-trained Inception-v3 network [68]. The input size of the network is 299 x 299 x 3. All other experimental hyper-parameters for SAPF are set to default [24]. Training details As regard to our early fixing framework, we randomly pick 20 images from CIFAR-10. And each image corresponds to one MIP problem. By default, solving one MIP problem for adversarial attack is with 6 search loops for G updating. Thus we record these 20*6=120 instances for early fixing training. γ, β, δ, L are set to 3, 50, 0.9, 2, respectively. The learning rate is set to 1e−4. We train for 20 epochs. For our learning-based early fixing methods, training without attention for one epoch costs 4min 28s, while training with attention costs 4min 20s. All the implementations are based on Python. We use the pre-trained model on CIFAR-10 to test on both CIFAR-10 and ImageNet.

Baselines and evaluations
We compare whether to use our learning-based early fixing (LEF) on SAPF or not.
We also compare whether to use attention layers or not. Besides, we also record the results by other attack paradigms, including one-pixel [69], corner search [70], PGD 0 + ∞ [70], SparseFool [71], C&W-0 [67], StrAttack [72]. Those results of other attacks are from the SAPF paper [24]. As regard to the evaluations, the p -norm (p = 0, 1, 2, ∞) of perturbations and the attack success rate (ASR) are utilized to evaluate the attack performance of different methods. We CIFAR-10 ImageNet Fig. 11. Convergence on different methods for sparse adversarial attack: how the objective (loss) changes with respect to the iterations during the inference stages for one image in CIFAR-10 (left) and ImageNet (right).
follow the same setting in [24]. We keep increasing the upper bound of p -norm of perturbations until the attack is success. We compare different attack algorithms in terms of the pnorm of perturbations under 100% ASR, though some sparse attack methods fail to generate 100% ASR. Moreover, for each image, we evaluate three different cases, i.e., the average case: the average performance of all 9 target classes; the best case: the performance w.r.t. the target class that is the easiest to attack; and the worst case: the performance w.r.t. the target class that is the most difficult to attack.

Results analysis
We exhibit the attack performances of best/average/worst cases with p -norm and ASR in Table 5.
We present the runtime comparisons whether to use LEF or not on SAPF in Table 6. We show the examples of generated perturbations by different methods in Figure 10. From the tables, we see that SAPF method achieve 100% attack success rate under all three cases, in both CIFAR-10 and ImageNet datasets. And with our LEF, the ASR still remains 100% in different cases, no matter with attention layers or not. The ∞ -norm of the one-Pixel-Attack is the largest among all algorithms and it achieves the lowest attack success rate. It is difficult to perform targeted adversarial attacks by only perturbing one pixel (the 0 = 3 relates to three channels), even on the tiny database CIFAR-10. The CornerSearch and PGD 0 + ∞ also fails to generate 100% success attack rate. Comparing to all adversarial attack algorithms except one-Pixel-Attack, SAPF method achieves the best 1 -norm and 2 -norm under all three cases. On CIFAR-10, with our LEF with attention layers, it achieves the better 1 -norm and 2norm under all cases compared to SAPF. On ImageNet, it achieves the better 1 -norm under all cases.
More importantly, with the aim of algorithmic acceleration, we can see the obvious time speedup on the η updating part, by Table 6. On CIFAR-10 dataset, the time speedup is more than 5×, while on ImageNet dataset, the time speedup is more than 2×. Those results demonstrate the efficiency and effectiveness of the proposed LEF method. In Fig. 11, we record the first loop out of the 6 search loops for η Updating. The figure reveals that our LEF method leads to faster convergence than the SAPF itself, when they all have quite similar objective (loss).