What is Integer programming: Definition and 13 Discussions

An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints (other than the integer constraints) are linear.
Integer programming is NP-complete. In particular, the special case of 0-1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of Karp's 21 NP-complete problems.
If some decision variables are not discrete the problem is known as a mixed-integer programming problem.

View More On Wikipedia.org
Recent contents Top users
  1. bagasme

    B Solving a Linear Programming Problem which Requires Integer Solutions

    Hello, In grade 11 of high school, I encountered this linear programming problem on my textbook: The "alternative solution" described in the textbook as follows: Let: - ##x## : amount of plant A - ##y## : amount of plant S - ##L## : garden area - ##L_x## : area of garden for one plant A -...
  2. Aleoa

    Stuck on an Integer Programming problem

    Homework Statement I've tried hours and hours to model this problem but i didn't succeed. Can you help me ? We want to realize n projects in the next T years. For each project, a profitability index pi is known, which expresses the expected final gain (in Euro) and a cost profile ai =...
  3. A

    I Open source software for integer programming

    I don't usually need help in locating software, but I'm having a heck of a time tracking down a good open-source bit of software which solves integer programming problems using arbitrary precision! If I don't find one soon, I'll need to write it myself. Which I don't mind, but it's silly to...
  4. S

    I Linear mapping of a binary vector based on its decimal value

    Given an ##N## dimensional binary vector ##\mathbf{v}## whose conversion to decimal is equal to ##j##, is there a way to linearly map the vector ##\mathbf{v}## to an ##{2^N}## dimensional binary vector ##\mathbf{e}## whose ##(j+1)##-th element is equal to ##1## (assuming the index starts...
  5. F

    Integer programming model (alternating constraints)

    Homework Statement Formulate as a mixed integer programming problem but do not solve. Maximize ##x_1 + x_2## subject to ##2x_1 + 3x_2 \le 12## or {##3x_1 + 4x_2 \le 24## and ##-x_1 + x_2 \ge 1##} ##x_1, x_2 \ge 0## Homework EquationsThe Attempt at a Solution if the first constraint is met, we...
  6. B

    Producing a Family of 0,1 Knapsack Sets

    Dear Physics Forum friends, I am currently stuck with the following question about the integer optimization: "Produce a family of 0,1 knapsack sets (having an increasing number n of variables) whose associated family of minimal covers grows exponentially with n." My thought is that I need to...
  7. S

    A Can this optimization problem be solved?

    Hello, I am working on an optimization problem but I am not sure if the problem can be formulated and solved with conventional solvers. Assume the minimization problem for a set of elements ##\mathcal{N} =\{ 1,\dots, h, \dots, i,\dots, N \}## $$ \mathrm{minimize}\quad C = \sum_{i=1}^{N}...
  8. rumborak

    Is this an integer programming problem?

    At work I am writing a somewhat complex piece of software, and inside it at some point I have to solve the following problem: I have several "streams", each of which has equally spaced points according to a proportionality factor 'a', i.e. X=a*n. Each stream has a different 'a'. As an example...
  9. C

    MHB Help on Fuzzy Integer Programming

    so our thesis is about fuzzy integer programming and even if I am searching what it is or what does it normally solve or how can it be solved the only results appearing are thesis which are difficult to understand. can someone explain what it is or suggest sites where I can have an idea? Thank you!
  10. C

    MHB How Can Binary Integer Programming Optimize Subject Distribution in Schools?

    I am about to do a paper about distributing subjects to students with the constraints on: number of subjects that the student need, number of students whom these subjects will be distributed to, and the number of students that every subject can handle (for example, 50 for math 1 and so on)...
  11. T

    Optimizing Knights on 8x8 Chess Board with Integer Programming

    Homework Statement On a 8x8 chess board format an Integer program to optimize the amount of knights required such that every square is covered by at least one knight. Homework Equations I know of a similar problem where we use duality for the placing 5 queens such that the maximum...
  12. I

    Formulating a Mixed Integer Programming Problem

    Homework Statement Not sure if this type of math goes in this section, but I have a quick question regarding a MIP problem. It's simple to grasp, but I'm not sure whether or not I am formulating this problem correctly. A city needs to hire workers to clean the snow. The city is divided into j...
  13. A

    Integer Programming help please T__T

    Homework Statement Paulette Smith and Maureen Becker are senior in engineering and business, respectively, at State University. They have set up a company, PM Computer Services, to assemble and see their own brand of personal computers. They buy component parts on the open market from a variety...
Back
Top