This page is for an old version of Hexaly Optimizer.
We recommend that you update your version and read the documentation for the
latest stable release.
Smallest circle¶
Principles learned¶
- Add float decision variables
- Define the float bounds from the data
- Define the actual set of decision variables
- Create a non-linear expression with operators “sqrt” and “pow”
Problem¶
Given a set of points in the plane, find the circle with mimimal radius which contains all of them.
For more details, see : problem.html.
Download the exampleProgram¶
The decision variables in the model are x and y, respectively equal to the abscissa and the ordinate of the origin of the circle. The radius to minimize is deduced as the maximum distance between the origin and each point.
- Execution:
- localsolver smallest_circle.lsp inFileName=instances/10points.txt [lsTimeLimit=] [solFileName=]
/********** smallest_circle.lsp **********/
use io;
/* Reads instance data */
function input(){
usage = "\nUsage: localsolver smallest_circle.lsp "
+ "inFileName=inputFile [solFileName=outputFile] [lsTimeLimit=timeLimit]\n";
if (inFileName == nil) throw usage;
local instance = io.openRead(inFileName);
nbPoints = instance.readInt();
for [i in 1..nbPoints]{
coordX[i] = instance.readInt();
coordY[i] = instance.readInt();
}
minX = min[i in 1..nbPoints](coordX[i]);
minY = min[i in 1..nbPoints](coordY[i]);
maxX = max[i in 1..nbPoints](coordX[i]);
maxY = max[i in 1..nbPoints](coordY[i]);
}
/* Declares the optimization model. */
function model() {
// x, y are respectively the abscissa and the ordinate of the origin of the circle
x <- float(minX,maxX);
y <- float(minY,maxY);
// Minimize the radius
r <- sqrt(max[i in 1..nbPoints](pow(x - coordX[i], 2) + pow(y - coordY[i], 2)));
minimize r;
}
/* Parameterizes the solver. */
function param() {
if(lsTimeLimit == nil) lsTimeLimit = 6;
}
/* Writes the solution in a file */
function output() {
if (solFileName != nil) // write solution file if needed
{
println("Write solution into file '" + solFileName + "'");
local solFile = io.openWrite(solFileName);
solFile.println("x=", x.value);
solFile.println("y=", y.value);
solFile.println("r=", r.value);
}
}
- Execution (Windows)
- set PYTHONPATH=%LS_HOME%\bin\python27\python smallest_circle.py instances\10points.txt
- Execution (Linux)
- export PYTHONPATH=/opt/localsolver_XXX/bin/python27/python smallest_circle.py instances/10points.txt
########## smallest_circle.py ##########
import localsolver
import sys
if len(sys.argv) < 2:
print ("Usage: python smallest_circle.py inputFile [outputFile] [timeLimit]")
sys.exit(1)
def read_integers(filename):
with open(filename) as f:
return [int(elem) for elem in f.read().split()]
with localsolver.LocalSolver() as ls:
#
# Reads instance data
#
file_it = iter(read_integers(sys.argv[1]))
# Number of points
nb_points = file_it.next()
# Point coordinates
coord_x = [None]*nb_points
coord_y = [None]*nb_points
coord_x[0] = file_it.next()
coord_y[0] = file_it.next()
# Minimum and maximum value of the coordinates of the points
min_x = coord_x[0]
max_x = coord_x[0]
min_y = coord_y[0]
max_y = coord_y[0]
for i in range(1,nb_points):
coord_x[i] = file_it.next()
coord_y[i] = file_it.next()
if (coord_x[i] < min_x):
min_x = coord_x[i]
else:
if (coord_x[i] > max_x):
max_x = coord_x[i]
if (coord_y[i] < min_y):
min_y = coord_y[i]
else:
if (coord_y[i] > max_y):
max_y = coord_y[i]
#
# Declares the optimization model
#
model = ls.model
# Numerical decisions
x = model.float(min_x, max_x)
y = model.float(min_y, max_y)
# Distance between the origin and the point i
radius = [(x - coord_x[i])**2 + (y - coord_y[i])**2 for i in range(nb_points)]
# Minimize the radius r
r = model.sqrt(model.max(radius))
model.minimize(r)
model.close()
#
# Parameterizes the solver
#
ls.param.nb_threads = 2
if len(sys.argv) >= 4: ls.create_phase().time_limit = int(sys.argv[3])
else: ls.create_phase().time_limit = 6
ls.solve()
#
# Writes the solution in a file
#
if len(sys.argv) >= 3:
with open(sys.argv[2], 'w') as f:
f.write("x=%f\n" % x.value)
f.write("y=%f\n" % y.value)
f.write("r=%f\n" % r.value)
- Compilation / Execution (Windows)
- cl /EHsc smallest_circle.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver.dll.libsmallest_circle instances\10points.txt
- Compilation / Execution (Linux)
- g++ smallest_circle.cpp -I/opt/localsolver_XXX/include -llocalsolver -lpthread -o smallest_circle./smallest_circle instances/10points.txt
/********** smallest_circle.cpp **********/
#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include "localsolver.h"
using namespace localsolver;
using namespace std;
class SmallestCircle {
public:
/* Number of points */
int nbPoints;
/* Point coordinates */
vector<lsint> coordX;
vector<lsint> coordY;
/* Minimum and maximum value of the coordinates of the points */
lsdouble minX;
lsdouble minY;
lsdouble maxX;
lsdouble maxY;
/* Solver. */
LocalSolver localsolver;
/* LS Program variables */
LSExpression x;
LSExpression y;
/* Objective */
LSExpression r;
/* Reads instance data */
void readInstance(const string& fileName){
ifstream infile(fileName.c_str());
if (!infile.is_open()) {
cerr << "File " << fileName << " cannot be opened." << endl;
exit(1);
}
infile >> nbPoints;
coordX.resize(nbPoints);
coordY.resize(nbPoints);
infile >> coordX[0];
infile >> coordY[0];
minX = coordX[0];
maxX = coordX[0];
minY = coordY[0];
maxY = coordY[0];
for (int i = 1; i < nbPoints; i++){
infile >> coordX[i];
infile >> coordY[i];
if (coordX[i] < minX)
minX = coordX[i];
else
if (coordX[i] > maxX)
maxX = coordX[i];
if (coordY[i] < minY)
minY = coordY[i];
else
if (coordY[i] > maxY)
maxY = coordY[i];
}
infile.close();
}
void solve(int limit) {
try {
/* Declares the optimization model. */
LSModel model = localsolver.getModel();
// Numerical decisions
x = model.floatVar(minX, maxX);
y = model.floatVar(minY, maxY);
// Distance between the origin and the point i
vector<LSExpression> radius(nbPoints);
for (int i = 0; i < nbPoints; i++){
radius[i] = model.pow(x - coordX[i], 2) + model.pow(y - coordY[i], 2);
}
// Minimize the radius r
r = model.sqrt(model.max(radius.begin(), radius.end()));
model.minimize(r);
model.close();
/* Parameterizes the solver. */
LSPhase phase = localsolver.createPhase();
phase.setTimeLimit(limit);
localsolver.solve();
} catch (const LSException& e) {
cout << "LSException:" << e.getMessage() << endl;
exit(1);
}
}
/* Writes the solution in a file */
void writeSolution(const string& fileName){
ofstream outfile(fileName.c_str());
if (!outfile.is_open()) {
cerr << "File " << fileName << " cannot be opened." << endl;
exit(1);
}
outfile << "x=" << x.getDoubleValue() << endl;
outfile << "y=" << y.getDoubleValue() << endl;
outfile << "r=" << r.getDoubleValue() << endl;
outfile.close();
}
};
int main(int argc, char** argv) {
if (argc < 2) {
cout << "Usage: smallest_circle inputFile [outputFile] [timeLimit]" << endl;
exit(1);
}
const char* instanceFile = argv[1];
const char* solFile = argc > 2 ? argv[2] : NULL;
const char* strTimeLimit = argc > 3 ? argv[3] : "6";
SmallestCircle model;
model.readInstance(instanceFile);
model.solve(atoi(strTimeLimit));
if(solFile != NULL)
model.writeSolution(solFile);
return 0;
}
- Compilation / Execution (Windows)
- javac SmallestCircle.java -cp %LS_HOME%\bin\localsolver.jarjava -cp %LS_HOME%\bin\localsolver.jar;. SmallestCircle instances\10points.txt
- Compilation/Execution (Linux)
- javac SmallestCircle.java -cp /opt/localsolver_XXX/bin/localsolver.jarjava -cp /opt/localsolver_XXX/bin/localsolver.jar:. SmallestCircle instances/10points.txt
/********** SmallesrCircle.java **********/
import java.util.*;
import java.io.*;
import localsolver.*;
public class SmallestCircle {
/* Number of points */
int nbPoints;
/* Point coordinates */
int[] coordX;
int[] coordY;
/* Minimum and maximum value of the coordinates of the points */
int minX;
int minY;
int maxX;
int maxY;
/* Solver. */
LocalSolver localsolver;
/* LS Program variables */
LSExpression x;
LSExpression y;
/* Objective i */
LSExpression r;
/* Reads instance data */
void readInstance(String fileName){
try {
Scanner input = new Scanner(new File(fileName));
nbPoints = input.nextInt();
coordX = new int[nbPoints];
coordY = new int[nbPoints];
coordX[0] = input.nextInt();
coordY[0] = input.nextInt();
minX = coordX[0];
maxX = coordX[0];
minY = coordY[0];
maxY = coordY[0];
for (int i = 1; i < nbPoints; i++) {
coordX[i] = input.nextInt();
coordY[i] = input.nextInt();
if (coordX[i] < minX)
minX = coordX[i];
else
if (coordX[i] > maxX)
maxX = coordX[i];
if (coordY[i] < minY)
minY = coordY[i];
else
if (coordY[i] > maxY)
maxY = coordY[i];
}
input.close();
} catch (IOException ex) {
ex.printStackTrace();
}
}
void solve(int limit) {
try {
localsolver = new LocalSolver();
/* Declares the optimization model. */
LSModel model = localsolver.getModel();
// Numerical decisions
x = model.floatVar(minX, maxX);
y = model.floatVar(minY, maxY);
// Distance between the origin and the point i
LSExpression[] radius = new LSExpression[nbPoints];
for (int i = 0; i<nbPoints; i++){
radius[i] = model.sum();
radius[i].addOperand(model.pow(model.sub(x, coordX[i]), 2));
radius[i].addOperand(model.pow(model.sub(y, coordY[i]), 2));
}
// Minimize the radius r
r = model.sqrt(model.max(radius));
model.minimize(r);
model.close();
/* Parameterizes the solver. */
LSPhase phase = localsolver.createPhase();
phase.setTimeLimit(limit);
localsolver.solve();
} catch (LSException e) {
System.out.println("LSException:" + e.getMessage());
System.exit(1);
}
}
/* Writes the solution in a file */
void writeSolution(String fileName) {
try{
BufferedWriter output = new BufferedWriter(new FileWriter(fileName));
output.write("x="+ x.getDoubleValue() + "\n");
output.write("y="+ y.getDoubleValue() + "\n");
output.write("r="+ r.getDoubleValue() + "\n");
output.close();
} catch (IOException ex) {
ex.printStackTrace();
}
}
public static void main(String[] args) {
if (args.length < 1) {
System.out.println("Usage: java SmallestCircle inputFile [outputFile] [timeLimit]");
System.exit(1);
}
String instanceFile = args[0];
String outputFile = args.length > 1 ? args[1] : null;
String strTimeLimit = args.length > 2 ? args[2] : "6";
SmallestCircle model = new SmallestCircle();
model.readInstance(instanceFile);
model.solve(Integer.parseInt(strTimeLimit));
if(outputFile != null) {
model.writeSolution(outputFile);
}
}
}
- Compilation/Execution (Windows)
- copy %LS_HOME%\bin\*net.dll .csc SmallestCircle.cs /reference:localsolvernet.dllSmallestCircle instances\10points.txt
/********** SmallestCircle.cs **********/
using System;
using System.IO;
using System.Collections.Generic;
using localsolver;
public class SmallestCircle : IDisposable
{
// Number of points
int nbPoints;
// Point coordinates
double[] coordX;
double[] coordY;
// Minimum and maximum value of the coordinates of the points
double minX;
double minY;
double maxX;
double maxY;
// Solver
LocalSolver localsolver;
// LS Program variables
LSExpression x;
LSExpression y;
// Objective
LSExpression r;
public SmallestCircle ()
{
localsolver = new LocalSolver();
}
/* Reads instance data */
public void ReadInstance(string fileName)
{
using (StreamReader input = new StreamReader(fileName))
{
nbPoints = int.Parse(input.ReadLine());
coordX = new double[nbPoints];
coordY = new double[nbPoints];
string[] splittedCoord = input.ReadLine().Split(' ');
coordX[0] = int.Parse(splittedCoord[0]);
coordY[0] = int.Parse(splittedCoord[1]);
minX = coordX[0];
maxX = coordX[0];
minY = coordY[0];
maxY = coordY[0];
for (int i = 1; i < nbPoints; i++)
{
splittedCoord = input.ReadLine().Split(' ');
coordX[i] = int.Parse(splittedCoord[0]);
coordY[i] = int.Parse(splittedCoord[1]);
if (coordX[i] < minX)
minX = coordX[i];
else
if (coordX[i] > maxX)
maxX = coordX[i];
if (coordY[i] < minY)
minY = coordY[i];
else
if (coordY[i] > maxY)
maxY = coordY[i];
}
}
}
public void Dispose ()
{
localsolver.Dispose();
}
public void Solve(int limit)
{
/* Declares the optimization model. */
LSModel model = localsolver.GetModel();
// Numerical decisions
x = model.Float(minX, maxX);
y = model.Float(minY, maxY);
// Distance between the origin and the point i
LSExpression[] radius = new LSExpression[nbPoints];
for (int i = 0; i < nbPoints; i++)
{
radius[i] = model.Pow(x - coordX[i], 2) + model.Pow(y - coordY[i], 2);
}
// Minimize the radius r
r = model.Sqrt(model.Max(radius));
model.Minimize(r);
model.Close();
/* Parameterizes the solver. */
LSPhase phase = localsolver.CreatePhase();
phase.SetTimeLimit(limit);
localsolver.Solve();
}
/* Writes the solution in a file */
public void WriteSolution(string fileName)
{
using (StreamWriter output = new StreamWriter(fileName))
{
output.WriteLine("x=" + x.GetDoubleValue());
output.WriteLine("y=" + y.GetDoubleValue());
output.WriteLine("r=" + r.GetDoubleValue());
}
}
public static void Main (string[] args)
{
if (args.Length < 1)
{
Console.WriteLine ("Usage: SmallestCircle inputFile [outputFile] [timeLimit]");
System.Environment.Exit(1);
}
string instanceFile = args[0];
string outputFile = args.Length > 1 ? args[1] : null;
string strTimeLimit = args.Length > 2 ? args[2] : "6";
using (SmallestCircle model = new SmallestCircle())
{
model.ReadInstance(instanceFile);
model.Solve (int.Parse(strTimeLimit));
if (outputFile != null)
model.WriteSolution(outputFile);
}
}
}