This paper introduces a framework for solving combinatorial optimization problems by learning from input-output examples of optimization problems. We introduce a new memory augmented neural model in which the memory is not resettable (i.e the information stored in the memory after processing an input example is kept for the next seen examples). We used deep reinforcement learning to train a memory controller agent to store useful memories. Our model was able to outperform hand-crafted solver on Binary Linear Programming (Binary LP). The proposed model is tested on different Binary LP instances with large number of variables (up to 1000 variables) and constrains (up to 700 constrains). An intelligent agent with a long-term memory processes raw data (as images, speech and natural language sentences) and then transfer these data streams into knowledge. The knowledge stored in the long-term memory can be used later in inference either by retrieving segments of memory during recalling, matching stored concepts with new raw data (e.g. image classification tasks) or solving more complex mathematical problems that require memorizing either the method of solving a problem or simple steps during solving. For example, the addition of long-digit numbers requires memorizing both the addition algorithm and the carries produced from the addition operations BID28 .In neural models, the weights connecting the layers are considered long term memories encoding the algorithm that transform inputs to outputs. Other neural models as recurrent neural networks (RNNs) introduce a short-term memory encoded as hidden states of previous inputs BID12 BID7 .In memory augmented neural networks (MANNs), a controller writes memories projected from its hidden state to a memory bank (usually in the form of a matrix), the controller then reads from the memory using some addressing mechanisms and generates a read vector which will be fed to the controller in the next time step BID6 . The memory will contain information about each of the input sequence tokens and the controller enriches its memory capacity by using the read vector form the previous time step.Unfortunately, In MANNs the memory is not a long-term memory and is re-settable when new examples are processed, making it unable to capture general knowledge about the inputs domain. In context of natural language processing, one will need general knowledge to answer open-ended questions that do not rely on temporal information only but also on general knowledge from previous input streams. In long-digits multiplication, it will be easier to store some intermediate multiplication steps as digit by digit multiplications and use them later when solving other instances than doing the entire multiplication digit by digit each time from scratch.Neural networks have a large capacity of memorizing, a long-term persistent memory will even increase the network capacity to memorize but will decrease the need for learning coarse features of the inputs that requires more depth.Storing features of the inputs will create shortcut paths for the network to learn the correct targets. Such a network will no longer need to depend on depth to learn good features of the inputs but instead will depend on stored memory features. In other words a long-term memory can provide intermediate answers to the network. Unlike regular MANNs and RNNs, a long-term memory can provide shortcut connections to both inputs features and previous time steps inputs.Consider when the memory contains the output of previous examples, the network would cheat from the memory to provide answers. Training such a network will focus on two stages: (1) Learning to find similarities between memory vectors and current input data, (2) learning to transform memory vectors into meaningful representations for producing the final output.The No Free Lunch Theorem of optimization BID25 states that: any two algorithms are equivalent when their performance is averaged across all possible problems, this means that an algorithm that solve certain classes of problems efficiently will be incompetent in other problems. In the setting of combinatorial optimization, there is no algorithm able to do better than a random strategy in expectation. The only way an algorithm outperforms another is to be specialized to a certain class of optimization problems BID0 . Learning optimization algorithms from scratch using pairs of input-output examples is a way to outperform other algorithms on certain classes. It is further interesting to investigate the ability of learned models to generate better solutions than hand crafted solvers.The focus of this paper is on designing neural models to solve Binary Linear Programming (or 0-1 Integer Programming) which is a special case of Integer Linear Programming problems where all decision variables are binary. The 0-1 integer programming is one of Krap's 21 NP-complete problems introduced in BID9 . The goal of Binary LP is to optimize a linear function under certain constrains. It is proved by BID3 that Binary LP expresses the complexity class NP (i.e any problem in the complexity class NP can be modeled as Binary LP instance).The standard form of a Binary LP problem is: DISPLAYFORM0 where c and b are vectors and A is a matrix.We propose a general framework for long-term memory neural models that uses reinforcement learning to store memories from a neural network. A long-term memory is not resettable and may or may not store hidden states from individual time steps. Instead a long term memory stores information that is considered to be useful for solving similar instances. The controller that decides to write memories follows a policy function that properly constructs the memory contents. We train and test this framework on synthetic data set of Binary LP instances. We analyze the model capability of generalization to more complex instances beyond the training data set. This paper introduced a long term memory coupled with a neural network, that is able to memorize useful input features to solve similar instances. We applied LTMN model to solve Binary LP instances. The LTMN was able to learn from supervised targets provided by a handcrafted solver, and generate better solutions than the solver. The LTMN model was able to generalize to more complex instances beyond those in the training set.
We propose a memory network model to solve Binary LP instances where the memory information is perseved for long-term use. 
{"src": "scitldr-AIC_train", "paper_id": "Bk_fs6gA-"}