Stack Overflow
Stack Overflow

Questions tagged [integer-programming]

Solving systems of linear equations where variables are integers.

An integer program is a problem where, in addition to the linear inequalities constraints, the variables are also constraint to be integers only.

While can be solved in polynomail time, integer-programming is NP-hard.

A good solver for such optimization problems is lp_solve. See also GLPK (http://www.gnu.org/software/glpk/) and CBC (https://projects.coin-or.org/Cbc)

However, for large or hard instances you may need a commercial solver such as CPLEX or Gurobi.

For more information see wikipedia.

307 questions
95
votes
3 answers

Python Mixed Integer Linear Programming

Are there any Mixed Integer Linear Programming(MILP) solver for Python? Can GLPK python solve MILP problem? I read that it can solve Mixed integer problem. I am very new to linear programming problem. So i am rather confused and cant really…
asun
  • 1,085
  • 1
  • 8
  • 6
28
votes
5 answers

Minimum exact cover of grid with squares; extra cuts

This problem appeared in a challenge, but since it is now closed it should be OK to ask about it. The problem (not this question itself, this is just background information) can be visually described like this, borrowing their own image: I chose to…
harold
  • 61,398
  • 6
  • 86
  • 164
17
votes
1 answer

How to convert quadratic to linear program?

I have an optimization problem that has in the objective function 2 multiplied variables, making the model quadratic. I am currently using zimpl, to parse the model, and glpk to solve it. As they don't support quadratic programming, I would need to…
user4233758
12
votes
2 answers

Solving an integer linear program: why are solvers claiming a solvable instance is infeasible?

I'm trying to solve integer programming problems. I've tried both use SCIP and LPSolve For example, given the final values of A and B, I want to solve for valA in the following C# code: Int32 a = 0, b = 0; a = a*-6 + b + 0x74FA - valA; b = b/3 + a +…
Craig Gidney
  • 17,763
  • 5
  • 68
  • 136
9
votes
4 answers

How to solve a system of linear equations over the nonnegative integers?

Given a linear system Ax = b, where matrix A and vector b have integer values, I want to find all nonnegative integer vectors x that solve this equation. So far, I have found some techniques such as the Smith normal form or the Hermite normal form…
while1fork
  • 374
  • 4
  • 15
9
votes
1 answer

How to implement a constraint solver for 2-D geometry?

I have a set of metallic sliding pieces which are constrained to the x and y axis in following way: I would need to maximize the horizontal distance among all pieces constrained by the same slider and the vertical distance among the sliding pieces…
deblocker
  • 7,629
  • 2
  • 24
  • 59
8
votes
3 answers

From expensive search to Integer Programming or Constraint Programming?

Consider m by n matrices M, all of whose entries are 0 or 1. For a given M, the question is whether there exists a non zero vector v, all of whose entries are -1, 0 or 1 for which Mv = 0. For example, [0 1 1 1] M_1 = [1 0 1 1] [1 1 0…
Simd
  • 19,447
  • 42
  • 136
  • 271
7
votes
2 answers

Determine allocation of values - Python

I am trying to create an optimal shift schedule where employees are assigned to shift times. The output should aim to spend the least amount of money. The tricky part is I need to account for specific constraints. These being: 1) At any given time…
jonboy
  • 415
  • 4
  • 14
  • 45
7
votes
0 answers

GUROBI: 'Missing constraint index' when adding constraint in Python

Trying to add the following constraint in Gurobi/Python: Code N_SERVERS = 5 #number of servers C_SERVER = [1]*N_SERVERS N_NODES = 3 #number of nodes C_NODES = [2]*N_NODES #create…
cherryp
  • 79
  • 1
  • 2
7
votes
2 answers

How to set MIP start (initial solution) with Gurobi solver from PuLP?

I'm using the PuLP module in Python to formulate a mixed integer program. I am trying to work out how to set a MIP start (i.e. a feasible solution for the program to start from) via the PuLP interface. Details on how to set MIP start are given…
kabdulla
  • 5,199
  • 3
  • 17
  • 30
6
votes
2 answers

How can I get R to use more CPU usage?

I noticed that R doesn't use all of my CPU, and I want to increase that tremendously (upwards to 100%). I don't want it to just parallelize a few functions; I want R to use more of my CPU resources. I am trying to run a pure IP set packing program…
Johnson
  • 69
  • 1
  • 3
6
votes
1 answer

How to use R to solve/pick the best people for a job - with restraints?

I'm fairly new to R and I'm trying to write a script for what I used to do with Solver in Excel. In my data below, I have a list of workers with job types A-E. Each worker has a salary and a production rate. What I want R to do is find the…
Derek Pierson
  • 87
  • 7
5
votes
1 answer

Obtain list of SAT solutions from ortools

I'm trying to figure out how to get the complete list of possible solutions from the ortools.sat.python.cp_model. I understand I can print them, as in the example below, but it is not clear to me how to get the values, e.g. as a nested list or list…
mcsoini
  • 6,280
  • 2
  • 15
  • 38
5
votes
2 answers

Find optimal points to cut a set of intervals

Given a set of intervals on the real line and some parameter d > 0. Find a sequence of points with gaps between neighbors less or equal to d, such that the number of intervals that contain any of the points is minimized. To prevent trivial…
Arkadi
  • 198
  • 5
5
votes
1 answer

Solving Assignment Problem with conditional minimum group sizes using CVXPY

I'm using cvxpy within python to solve a particular type of assignment problem. I'd like to assign M people to N groups in a way that minimizes cost, with the following constraints on groups: Groups cannot have more than J members If a group is…
profj
  • 311
  • 3
  • 10
1
2 3
…
20 21